Show simple item record

dc.contributor.authorSlivkins, Aleksandrs Lev
dc.description.abstractConcurrent with numerous theoretical results on metric embeddings, a growing body of research in the networking community has studied the distance matrix defined by node-to-node latencies in the Internet, resulting in a number of recent approaches that approximately embed this distance matrix into low-dimensional Euclidean space. A fundamental distinction between the theoretical approaches to embeddings and this recent Internet-related work is that the latter operates under the additional constraint that it is only feasible to measure a linear number of node pairs, and typically in a highly structured way. Indeed, the most common framework here is a "beacon-based" approach: one randomly chooses a small number of nodes ('beacons') in the network, and each node measures its distance to these beacons only. Moreover, beacon-based algorithms are also designed for the more basic problem of "triangulation", in which one uses the triangle inequality to infer the distances that have not been measured. We give algorithms with provable performance guarantees for triangulation and embedding. We show that in addition to multiplicative error in the distances, performance guarantees for beacon-based algorithms typically must include a notion of "slack" -- a certain fraction of all distances may be arbitrarily distorted. For arbitrary metrics, we give a beacon-based embedding algorithm that achieves constant distortion on a (1-epsilon)-fraction of distances; this provides some theoretical justification for the success of the recent networking algorithms, and forms an interesting contrast with lower bounds showing that it is not possible to embed all distances with constant distortion. For doubling metrics (which have been proposed as a reasonable abstraction of Internet latencies), we show that triangulation with a constant number of beacons can achieve multiplicative error (1+delta) on a (1-epsilon)-fraction of distances, for arbitrarily small constants epsilon, delta. We extend these results in a number of directions: embeddings with slack that work for all epsilon at once; distributed algorithms for triangulation and embedding with low overhead on all participating nodes; distributed triangulation with guarantees for all node pairs; node-labeling problems for graphs and metrics; systems project on location-aware node selection in a large-scale distributed network.en_US
dc.format.extent1313951 bytes
dc.relation.isformatofbibid: 6476155
dc.subjectcomputer scienceen_US
dc.subjectrouting schemesen_US
dc.subjectdistance labelingen_US
dc.subjectdistributed algorithmsen_US
dc.subjectsmall-world networksen_US
dc.subjectmetric embeddingsen_US
dc.subjectdoubling dimensionen_US
dc.subjectembeddings with slacken_US
dc.subjectdoubling metricsen_US
dc.subjectpartial embeddingsen_US
dc.subjectscaling distortionen_US
dc.subjectgracefully degrading distortionen_US
dc.subjectvirtual coordinatesen_US
dc.subjectgrowth-constrained metricsen_US
dc.subjectinternet latenciesen_US
dc.titleEmbedding, Distance Estimation and Object Location in Networksen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record