Yakov Nekrich

Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing

2020 · arXiv (Cornell University)

Under the word RAM model, we design three data structures that can be constructed in $O(n\sqrt{\lg n})$ time over $n$ points in an $n \times n$ grid. The first data structure is an $O(n\lg^ε n)$-word …

External-memory dictionaries with worst-case update cost

2022 · arXiv (Cornell University)

The $B^ε$-tree [Brodal and Fagerberg 2003] is a simple I/O-efficient external-memory-model data structure that supports updates orders of magnitude faster than B-tree with a query performance comparable to the B-tree: for any positive constant $ε<1$ …