Kirsten Hildrum, John Kubiatowicz and Satish Rao

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-03-1267
August 2003

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/CSD-03-1267.pdf

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.

BibTeX citation:

@techreport{Hildrum:CSD-03-1267,
    Author = {Hildrum, Kirsten and Kubiatowicz, John and Rao, Satish},
    Title = {Another Way to Find the Nearest Neighbor in Growth-Restricted Metrics},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2003},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5253.html},
    Number = {UCB/CSD-03-1267},
    Abstract = {In this paper, we give sequential and distributed dynamic data structures for finding nearest neighbors in certain growth restricted metrics. <p>In particular, we give a sequential data structure that uses linear space, and requires <i>O</i>(log <i>n</i>) expected time and <i>O</i>(log <i>n</i>) time for lookups with high probability. This improved the results of Karger and Ruhl, whose data structure takes <i>O</i>(<i>n</i> log <i>n</i>) space with comparable expected time bounds. <p>Also, we describe a dynamic, load-balanced data structure using <i>O</i>(log <i>n</i>) space per node, matching the bound of Karger and Ruhl. <p>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.}
}

EndNote citation:

%0 Report
%A Hildrum, Kirsten
%A Kubiatowicz, John
%A Rao, Satish
%T Another Way to Find the Nearest Neighbor in Growth-Restricted Metrics
%I EECS Department, University of California, Berkeley
%D 2003
%@ UCB/CSD-03-1267
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2003/5253.html
%F Hildrum:CSD-03-1267