Kirsten Hildrum and John Kubiatowicz and Satish Rao

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-03-1267

, 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. <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.

---

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},
    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