Given a bounded universe {0,1,⋯,U-1}, we show how to perform predecessor searches in O(loglogΔ) expected time, where Δ is the difference between the element being searched for and its predecessor in the structure, while supporting updates in O(loglogΔ) expected amortized time, as well. This unifies the results of traditional bounded universe structures (which support predecessor searches in O(loglogU) time) and hashing (which supports membership queries in O(1) time). We also show how these results can be applied to approximate nearest neighbour queries and range searching.

Additional Metadata
Keywords Bounded universe, Distance sensitivity, Nearest neighbour search, Predecessor search, Range search
Persistent URL dx.doi.org/10.1016/j.comgeo.2012.01.002
Journal Computational Geometry
Citation
Bose, P, Douïeb, K. (Karim), Dujmović, V, Howat, J. (John), & Morin, P. (2013). Fast local searches and updates in bounded universes. In Computational Geometry (Vol. 46, pp. 181–189). doi:10.1016/j.comgeo.2012.01.002