Show simple item record

dc.contributor.authorSlivkins, Aleksandrsen_US
dc.description.abstractWe 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.en_US
dc.format.extent262777 bytes
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleDistance Estimation and Object Location via Rings of Neighborsen_US
dc.typetechnical reporten_US

Files in this item


This item appears in the following Collection(s)

Show simple item record