Distance estimation and object location via rings of neighbors

DOI10.1007/S00446-006-0015-8zbMath1266.68100OpenAlexW2006517766MaRDI QIDQ1954208

Aleksandrs Slivkins

Publication date: 20 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/5738

zbMATH Keywords

triangulationsmall-world networksdoubling dimensionrouting schemesdistance labeling

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Data structures (68P05) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (6)

Near isometric terminal embeddings for doubling metrics ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Greedy routing and the algorithmic small-world phenomenon ⋮ Near Isometric Terminal Embeddings for Doubling Metrics ⋮ Low-Distortion Inference of Latent Similarities from a Multiplex Social Network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed object location in a dynamic network
• Accessing nearby copies of replicated objects in a distributed environment
• Could any graph be turned into a small-world?
• Measured descent: A new embedding method for finite metrics
• The small-world phenomenon
• Improved routing strategies with succinct tables
• Triangulation and embedding using small sets of beacons
• Approximate distance oracles
• Know thy neighbor's neighbor
• Bypassing the embedding
• Plongements lipschitziens dans ${\bbfR}\sp n$
• Every complete doubling metric space carries a doubling measure
• Hausdorff dimension and doubling measures on metric spaces
• Distributed Computing: A Locality-Sensitive Approach
• A trade-off between space and efficiency for routing tables
• Distance labeling in graphs
• Compact name-independent routing with minimum stretch
• Distance estimation and object location via rings of neighbors
• Object location using path separators
• Collective dynamics of ‘small-world’ networks
• Distributed Computing
• A Doubling Dimension Threshold Θ(loglogn) for Augmented Graph Navigability
• Routing with Improved Communication-Space Trade-Off
• Automata, Languages and Programming
• Fast Construction of Nets in Low-Dimensional Metrics and Their Applications
• Algorithms – ESA 2005
• Compact routing on euclidian metrics
• Eclecticism shrinks even small worlds
• Analyzing Kleinberg's (and other) small-world Models
• Space-efficiency for routing schemes of stretch factor three

This page was built for publication: Distance estimation and object location via rings of neighbors