PDF

Description

In this paper, we give sequential and distributed dynamic data structures for finding nearest neighbors in certain growth restricted metrics.

In particular, we give a sequential data structure that uses linear space, and requires O(log n) expected time and O(log n) time for lookups with high probability. This improved the results of Karger and Ruhl, whose data structure takes O(n log n) space with comparable expected time bounds.

Also, we describe a dynamic, load-balanced data structure using O(log n) space per node, matching the bound of Karger and Ruhl.

We note that our algorithm is significantly different in structure from those of Karger and Ruhl, and perhaps substantially simpler. It is based on a technique used for object location developed by Plaxton, Rajaraman and Richa, which gives it an application to peer-to-peer networks.

Details

Files

Statistics

from
to
Export
Download Full History