Show simple item record

dc.contributor.authorSlivkins, Aleksandrsen_US
dc.date.accessioned2007-04-04T20:37:11Z
dc.date.available2007-04-04T20:37:11Z
dc.date.issued2006-08-13en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cis/TR2006-2041en_US
dc.identifier.urihttps://hdl.handle.net/1813/5738
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.format.mimetypeapplication/pdf
dc.language.isoen_USen_US
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

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics