Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computing and Information Science
  4. Computing and Information Science Technical Reports
  5. "Distance Estimation and Object Location via Rings of Neighbors"

"Distance Estimation and Object Location via Rings of Neighbors"

File(s)
TR2005-1977.ps (286.79 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5677
Collections
Computing and Information Science Technical Reports
Author
Slivkins, Aleksandrs
Abstract

We approach several problems on distance estimation and object location using a common technique called \emph{rings of neighbors}. Using this technique on metrics of low doubling dimension, we obtain significant improvements for low-stretch routing schemes, distance labeling, searchable small worlds, and triangulation-based distance estimation. Apart from improving the previously known bounds for these problems, our contributions include extending Kleinberg's small world model to metrics of low doubling dimension, and a short proof of the main result in [Chan et al., SODA'05]. Doubling dimension is a combinatorial (non-geometric) notion of dimensionality that has recently become popular in theoretical CS literature. A collection of rings of neighbors is a sparse distributed data structure that captures the distances and routing information. The idea is that every node $u$ stores pointers to some nodes called 'neighbors'; these pointers are partitioned into several 'rings', so that for some increasing sequence of balls ${B_i}$ around $u$, the neighbors in the $i$-th ring lie inside $B_i$; the radii of these balls and the distribution of neighbors in a given ring depend on the specific application. For metrics of low doubling dimension it has been particularly helpful to combine the following two collections of rings: in the first collection, the cardinalities of the balls $B_i$ grow exponentially, and the neighbors are distributed randomly; in the second collection the \emph{radii} of the $B_i$'s grow exponentially, and the neighbors are distributed geographically. Although used implicitly in several contexts, rings of neighbors have not been articulated as a general proof technique.

Date Issued
2005-02-12
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2005-1977
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance