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)
TR2006-2041.pdf (256.62 KB)
Permanent Link(s)
https://hdl.handle.net/1813/5738
Collections
Computing and Information Science Technical Reports
Author
Slivkins, Aleksandrs
Abstract

We consider four problems on distance estimation and object location which share the common flavor of capturing global information via informative node labels: low-stretch routing schemes, distance labeling, searchable small worlds, and triangulation-based distance estimation. Focusing on metrics of low doubling dimension, we approach these problems with a common technique called "rings of neighbors", which refers to a sparse distributed data structure that underlies all our constructions. Apart from improving the previously known bounds for these problems, our contributions include extending Kleinberg's small world model to doubling metrics, and a short proof of the main result in [Chan et al., SODA 2005]. Doubling dimension is a notion of dimensionality for general metrics that has recently become a useful algorithmic concept in the theoretical computer science literature.

Date Issued
2006-08-13
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2006-2041
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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