Given a bounded universe {0,1,....,U-1}, we show how to perform (successor) searches in O(log log δ) expected time and updates in O(log log δ) expected amortized time, where δ is the rank dierence between the element being searched for and its successor in the structure. This unies the results of traditional bounded universe structures (which support successor searches in O(log log U) time) and hashing (which supports exact searches in O(1) time). We also show how these results can be extended to answer approximate nearest neighbour queries in low dimensions.

Additional Metadata
Conference 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010
Citation
Bose, P, Douieb, K. (Karim), Dujmović, V, Howat, J. (John), & Morin, P. (2010). Fast local searches and updates in bounded universes. Presented at the 22nd Annual Canadian Conference on Computational Geometry, CCCG 2010.