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