Distance estimation and object location via rings of neighbors

ABSTRACT

We consider four problems on distance estimation and object location: low-stretch routing schemes [37], distance labeling [14], searchable small worlds [22], and triangulation-based distance estimation [24]. Focusing on metrics of low doubling dimension, we approach these problems with a common technique called rings of neighbors. 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. [9]. Doubling dimension is a combinatorial (non-geometric) notion of dimensionality that has recently become popular in the theoretical computer science literature.A collection of rings of neighbors is a sparse distributed data structure that captures the distance and routing information. The idea is that every node u stores pointers to some nodes called 'neighbors'; these pointers are partitioned into several 'rings', so that for some increasing sequence of balls Bi around u, the neighbors in the i-th ring lie inside Bi; the radii of these balls and the distribution of neighbors in a given ring depend on the specific application. In effect, rings of neighbors represent an overlay network with a certain structure imposed by the balls Bi. Although used implicitly in several contexts, rings of neighbors have not been articulated as a general proof technique.

REFERENCES

• 1: Ittai Abraham , Dahlia Malkhi , Oren Dobzinski, LAND: stretch (1 + ε) locality-aware networks for DHTs, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 2: Ittai Abraham , Dahlia Malkhi, Compact routing on euclidian metrics, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011789]
• 3: Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007916]
• 4: I. Abraham, C. Gavoille and D. Malkhi Routing with Improved Communication-Space Trade-Off, DISC 2004
• 5: Ittai Abraham , Dahlia Malkhi, Name independent routing for growth bounded networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073978]
• 6: P. Assouad, "Plongements lipschitziens dans R n," Bull. Soc. Math. France, 111 (4), pp. 429--448, 1983.
• 7: Baruch Awerbuch , Amotz Bar Noy , Nathan Linial , David Peleg, Improved routing strategies with succinct tables, Journal of Algorithms, v.11 n.3, p.307-341, Sep. 1990 [doi>10.1016/0196-6774(90)90017-9]
• 8: B. Awerbuch and D. Peleg, "Sparse partitions," FOCS 1990.
• 9: H.T-H. Chan, A. Gupta, B.M. Maggs and S. Zhou, "On hierarchical routing in bounded-growth metrics," SODA 2005. Full and updated version available as a Carnegie Mellon University ETR CMU-PDL-04-106, 2004.
• 10: P. Dodds, R. Muhamad and D. Watts, "An experimental study of search in global social networks," Science, 301: 827--829, 2003.
• 11: Pierre Fraigniaud , Cyril Gavoille , Christophe Paul, Eclecticism shrinks even small worlds, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011793]
• 12: Paul Francis , Sugih Jamin , Cheng Jin , Yixin Jin , Danny Raz , Yuval Shavitt , Lixia Zhang, IDMaps: a global internet host distance estimation service, IEEE/ACM Transactions on Networking (TON), v.9 n.5, p.525-540, October 2001 [doi>10.1109/90.958323]
• 13: Cyril Gavoille , Marc Gengler, Space-efficiency for routing schemes of stretch factor three, Journal of Parallel and Distributed Computing, v.61 n.5, p.679-687, May 2001 [doi>10.1006/jpdc.2000.1705]
• 14: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Journal of Algorithms, v.53 n.1, p.85-112, October 2004 [doi>10.1016/j.jalgor.2004.05.002]
• 15: Cyril Gavoille , Michal Katz , Nir A. Katz , Christophe Paul , David Peleg, Approximate Distance Labeling Schemes, Proceedings of the 9th Annual European Symposium on Algorithms, p.476-487, August 28-31, 2001
• 16: Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003 [doi>10.1007/s00446-002-0073-5]
• 17: J. Heinonen, Lectures on analysis on metric spaces, Springer Verlag, Universitext 2001.
• 18: Kirsten Hildrum , Robert Krauthgamer , John Kubiatowicz, Object location in realistic networks, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007918]
• 19: S. Hotz, "Routing information organization to support scalable interdomain routing with heterogeneous path requirements," Ph.D. Thesis, Univ. of Southern California, 1994.
• 20: James D. Guyton , Michael F. Schwartz, Locating nearby copies of replicated Internet servers, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.288-298, August 28-September 01, 1995, Cambridge, Massachusetts, United States
• 21: Anupam Gupta , Robert Krauthgamer , James R. Lee, Bounded Geometries, Fractals, and Low-Distortion Embeddings, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.534, October 11-14, 2003
• 22: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 23: J. Kleinberg, "Small-world phenomena and the dynamics of information," NIPS 2001.
• 24: Jon Kleinberg , Aleksandrs Slivkins , Tom Wexler, Triangulation and Embedding Using Small Sets of Beacons, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.444-453, October 17-19, 2004 [doi>10.1109/FOCS.2004.70]
• 25: C. Kommareddy , B. Bhattacharjee, Finding Close Friends on the Internet, Proceedings of the Ninth International Conference on Network Protocols, p.301, November 11-14, 2001
• 26: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 27: Robert Krauthgamer , James R. Lee , Manor Mendel , Assaf Naor, Measured Descent: A New Embedding Method for Finite Metrics, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.434-443, October 17-19, 2004 [doi>10.1109/FOCS.2004.41]
• 28: J.R. Lee, M. Mendel and A. Naor, "Metric structures in L1: Dimension, snowflakes, and average distortion," LATIN 2004.
• 29: D. Malkhi, personal communication, 2005.
• 30: Gurmeet Singh Manku , Moni Naor , Udi Wieder, Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007368]
• 31: Chip Martel , Van Nguyen, Analyzing Kleinberg's (and other) small-world Models, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011794]
• 32: Ch. Martel and V. Nguyen, "Analyzing and characterizing small-world graphs," SODA 2005.
• 33: Sariel Har-Peled , Manor Mendel, Fast construction of nets in low dimensional metrics, and their applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064117]
• 34: S. Milgram, "The small world problem," Psychology Today, 1, 61 (1967).
• 35: David Peleg, Proximity-Preserving Labeling Schemes and Their Applications, Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science, p.30-41, June 17-19, 1999
• 36: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 37: David Peleg , Eli Upfal, A trade-off between space and efficiency for routing tables, Journal of the ACM (JACM), v.36 n.3, p.510-530, July 1989 [doi>10.1145/65950.65953]
• 38: C.G. Plaxton, R. Rajaraman and A. W. Richa, "Accessing nearby copies of replicated objects in a distributed environment," Theory Comput. Syst., 32 (3), pp. 241--280, 1999.
• 39: Aleksandrs Slivkins, Distributed approaches to triangulation and embedding, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 40: A. Slivkins, "Distance Estimation and Object Location via Rings of Neighbors," full version: invited to the special issue of Distributed Computing, available from the author's webpage at www.cs.cornell.edu/people/slivkins/research.
• 41: K. Talwar, "Bypassing the embedding: approximation schemes and compact representations for growth restricted metrics," STOC 2004.
• 42: Mikkel Thorup , Uri Zwick, Approximate distance oracles, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.183-192, July 2001, Hersonissos, Greece [doi>10.1145/380752.380798]
• 43: Mikkel Thorup , Uri Zwick, Compact routing schemes, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.1-10, July 2001, Crete Island, Greece [doi>10.1145/378580.378581]
• 44: D.J. Watts, S.H. Strogatz, "Collective dynamics of 'small-world' networks," Nature, 393:440-42, 1998.
• 45: Bernard Wong , Aleksandrs Slivkins , Emin Gün Sirer, Meridian: a lightweight network location service without virtual coordinates, ACM SIGCOMM Computer Communication Review, v.35 n.4, October 2005

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems; Graph labeling

General Terms:
Algorithms, Performance, Theory