"Distance Estimation and Object Location via Rings of Neighbors"
No Access Until
Permanent Link(s)
Other Titles
Author(s)
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