Delta-Fast Tries: Local Searches in Bounded Universes with Linear Space

摘要

Let w ∈ N and U = {0,1,..., 2~w - 1} be a bounded universe of w-bit integers. We present a dynamic data structure for predecessor searching in U. Our structure needs O(log log ∆) time for queries and O(log log ∆) expected time for updates, where ∆ is the difference between the query element and its nearest neighbor in the structure. Our data structure requires linear space. This improves a result by Bose et al. [CGTA, 46(2), pp. 181-189]. The structure can be applied for answering approximate nearest neighbor queries in low dimensions and for dominance queries on a grid.