A note on the nearest neighbor in growth-restricted metrics
Kirsten W. Hildrum, John D. Kubiatowicz, Sean Ma, Satish B. Rao · 2004
In this paper, we give results relevant to sequential and distributed dynamic data structures for finding nearest neighbors in growth-restricted metrics. Our sequential data structure uses linear space, and requires O(log n) queries in expecation and O(log n) queries for lookups with high probability. This improves the results of Karger and Ruhl [4], whose data structure uses O(n log n) space with comparable expected time bounds. This also improves on the time bound of a load-balanced version of algorithm (for dynamic networks) presented in [3].