2005/05/22 by Christian Worm Mortensen, Rasmus Pagh, Mihai Pǎtraçcu · 2 citations
Computer Science · Mathematics · #Algorithms and Data Compression #Network Packet Processing and Optimization #Advanced Image and Video Retrieval Techniques #Recursion (computer science) #Sublinear function #Dimension (graph theory) #Trie #Computer science #Range query (database) #Range (aeronautics) #Simple (philosophy) #Integer (computer science) #Set (abstract data type) #Interval (graph theory) #Hash function #Path (computing) #Space (punctuation) #Heuristic #Data structure #Tree (set theory) #Mathematics #Discrete mathematics #Combinatorics #Algorithm #Mathematical optimization
paper · doi:10.1145/1060590.1060606
openalex publication_date 2005/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. Range searching is a natural and fundamental variant of integer search, and can be solved using predecessor search. However, for a RAM with w-bit words, we show how to perform updates in O(lg w) time and answer queries in O(lg lg w) time. The update time is identical to the van Emde Boas structure, but the query time is exponentially faster. Existing lower bounds show that achieving our query time for predecessor search requires doubly-exponentially slower updates. We present some arguments supporting the conjecture that our solution is optimal.Our solution is based on a new and interesting recursion idea which is "more extreme" that the van Emde Boas recursion. Whereas van Emde Boas uses a simple recursion (repeated halving) on each path in a trie, we use a nontrivial, van Emde Boas-like recursion on every such path. Despite this, our algorithm is quite clean when seen from the right angle. To achieve linear space for our data structure, we solve a problem which is of independent interest. We develop the first scheme for dynamic perfect hashing requiring sublinear space. This gives a dynamic Bloomier filter (a storage scheme for sparse vectors) which uses low space. We strengthen previous lower bounds to show that these results are optimal.