Triangulation and embedding using small sets of beacons

ABSTRACT

Concurrent with recent theoretical interest in the problem of metric embedding, 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. There is a fundamental distinction, however, between the theoretical approaches to the embedding problem and this recent Internet-related work: in addition to computational limitations, Internet measurement algorithms operate under the constraint that it is only feasible to measure distances for a linear (or near-linear) number of node pairs, and typically in a highly structured way. Indeed, the most common framework for Internet measurements of this type is a beacon-based approach one chooses uniformly at random a constant number of nodes (“beacons”) in the network, each node measures its distance to all beacons, and one then has access to only these measurements for the remainder of the algorithm. Moreover, beacon-based algorithms are often designed not for embedding but for the more basic problem of triangulation, in which one uses the triangle inequality to infer the distances that have not been measured.

Here we give algorithms with provable performance guarantees for beacon-based 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 metric spaces of bounded doubling dimension (which have been proposed as a reasonable abstraction of Internet latencies), we show that triangulation-based distance reconstruction with a constant number of beacons can achieve multiplicative error 1 + δ on a 1 − ε fraction of distances, for arbitrarily small constants δ and ε. For this same class of metric spaces, we give a beacon-based embedding algorithm that achieves constant distortion on a 1 − ε fraction of distances; this provides some theoretical justification for the success of the recent Global Network Positioning algorithm of Ng and Zhang [2002], and it forms an interesting contrast with lower bounds showing that it is not possible to embed all distances in a doubling metric space with constant distortion. We also give results for other classes of metric spaces, as well as distributed algorithms that require only a sparse set of distances but do not place too much measurement load on any one node.

REFERENCES

• 1: Abraham, I., Bartal, Y., Chan, H. T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J., Neiman, O., and Slivkins, A. 2005. Metric embeddings with relaxed guarantees. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 83--100.
• 2: Abraham, I., Bartal, Y., and Neiman, O. 2006. Advances in metric embedding theory. In Proceedings of the 38th ACM Symposium on Theory of Computing (STOC). ACM, New York.
• 3: Abraham, I., and Malkhi, D. 2005. Name independent routing for growth bounded networks. In Proceedings of the 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA). ACM, New York, 49--55.
• 4: Alon, N., and Spencer, J. 2000. The Probabilistic Method, 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York.
• 5: Assouad, P. 1983. Plongements lipschitziens dans Rⁿ. Bull. Soc. Math. France 111, 4, 429--448.
• 6: Bartal, Y., Linial, N., Mendel, M., and Naor, A. 2005. On metric ramsey-type phenomena. Ann. Math. 162, 2, 643--709. (Preliminary version in 35th ACM STOC, 2003.)
• 7: Bartal, Y., and Mendel, M. 2004. Dimension reduction for ultrametrics. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 664--665.
• 8: Bourgain, J. 1985. On Lipschitz embeddings of finite metric spaces in Hilbert space. Israel J. Math. 52, 1-2, 46--52.
• 9: Chan, H. T.-H., Dhamdhere, K., Gupta, A., Kleinberg, J., and Slivkins, A. 2009. Metric embeddings with relaxed guarantees. SIAM J. Comput. 38, 6 (Mar.), 2303--2329. (Preliminary version (merged with an independent effort by another research group) has appeared in 46th IEEE FOCS, 2005.)
• 10: Crippen, G., and Havel, T. 1988. Distance Geometry and Molecular Conformation. Wiley, New York.
• 11: Dabek, F., Cox, R., Kaashoek, F., and Morris, R. 2004. Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM. ACM, New York.
• 12: Enflo, P. 1969. On the nonexistence of uniform homeomorphisms between L_p-spaces. Ark. Mat. 8, 103--105.
• 13: Figiel, T., Lindenstrauss, J., and Milman, V. 1977. The dimension of almost spherical sections of convex bodies. Acta Math. 139, 53--94.
• 14: Fomenkov, M., Claffy, K., Huffaker, B., and Moore, D. 2001. Macroscopic Internet topology and performance measurements from the DNS root name servers. In Usenix LISA.
• 15: Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., and Zhang, L. 2001. IDMaps: A global Internet host distance estimation service. IEEE/ACM Trans. Netw. 9, 525--540. (Preliminary version in IEEE INFOCOM 1999.)
• 16: Gavoille, C., Peleg, D., Perennes, S., and Raz, R. 2004. Distance labeling in graphs. J. Algorithms 53, 1, 85--112. (Preliminary version in 12th ACM-SIAM SODA, 2001).
• 17: Goldreich, O., Goldwasser, S., and Ron:, D. 1998. Property testing and its connection to learning and approximation. J. ACM 45, 4, 653--750. (Preliminary version in 37th IEEE FOCS, 2006.)
• 18: Gummadi, K. P., Saroiu, S., and Gribble, S. D. 2002. King: Estimating latency between arbitrary internet end hosts. In Proceedings of the 2nd ACM SIGCOMM Internet Measurement Workshop (IMW). ACM, New York, 5--18.
• 19: Gupta, A., Krauthgamer, R., and Lee, J. R. 2003. Bounded geometries, fractals, and low--distortion embeddings. In Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 534--543.
• 20: Guyton, J., and Schwartz, M. 1995. Locating nearby copies of replicated Internet servers. In Proceedings of the ACM SIGCOMM. ACM, New York.
• 21: Hildrum, K., Kubiatowicz, J., Ma, S., and Rao, S. 2004. A note on the nearest neighbor in growth-restricted metrics. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 560--561.
• 22: Huffaker, B., Fomenkov, M., Plummer, D., Moore, D., and Claffy, K. 2002. Distance metrics in the internet. In Proceedings of the IEEE International Telecommunications Symposium (ITS). IEEE Computer Society Press, Los Alamitos, CA.
• 23: Indyk, P. 1999. Sublinear time algorithms for metric space problems. In Proceedings of the 31st ACM Symposium on Theory of Computing (STOC). ACM, New York, 428--434.
• 24: Indyk, P. 2001. Algorithmic applications of low-distortion geometric embeddings. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA. 10--33. (Invited survey).
• 25: Indyk, P., and Matoušek, J. 2004. Low-distortion embeddings of finite metric spaces. In Handbook of Discrete and Computational Geometry, Second ed., J. E. Goodman and J. O'Rourke, Eds. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, Chapter 8, xviii+1539.
• 26: Johnson, W. B., and Lindenstrauss, J. 1984. Extensions of Lipschitz maps into a Hilbert space. Contemp. Math. 26, 189--206.
• 27: Karger, D., and Ruhl, M. 2002. Finding nearest neighbors in growth-restricted metrics. In Proceedings of the 34th ACM Symposium on Theory of Computing (STOC). ACM, New York, 63--66.
• 28: Kempe, D., Kleinberg, J., and Demers, A. 2004. Spatial gossip and resource location protocols. J. ACM 51, 6, 943--967. (Preliminary version in 33rd ACM STOC, 2001.)
• 29: Kleinberg, J., Slivkins, A., and Wexler, T. 2004. Triangulation and embedding using small sets of beacons. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, Los Alamitos, CA, 444--453.
• 30: Kommareddy, C., Shankar, N., and Bhattacharjee, B. 2001. Finding close friends on the Internet. In Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP). IEEE Computer Society Press, Los Alamitos, CA.
• 31: Krauthgamer, R., Lee, J., Mendel, M., and Naor, A. 2005. Measured descent: A new embedding method for finite metrics. Geomet. Funct. Anal. (GAFA) 15, 4, 839--858. (Preliminary version in 45th IEEE FOCS, 2004.)
• 32: Krauthgamer, R., and Lee, J. R. 2003. The intrinsic dimensionality of graphs. In Proceedings of the 35th ACM Symposium on Theory of Computing (STOC). ACM, New York, 438--447.
• 33: Krauthgamer, R., and Lee, J. R. 2004. Navigating nets: Simple algorithms for proximity search. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 798--807.
• 34: Krauthgamer, R., and Sasson, O. 2003. Property testing of data dimensionality. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 18--27.
• 35: Laakso, T. J. 2002. Plane with A_&infn;-weighted metric not bi-Lipschitz embeddable to R^N. Bull. London Math. Soc. 34, 6, 667--676.
• 36: Lang, U., and Plaut, C. 2001. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87, 1-3, 285--307.
• 37: Linial, N. 2002. Finite metric spaces—combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002). Beijing, China, 573--586.
• 38: Linial, N., London, E., and Rabinovich, Y. 1995. The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 2, 215--245. (Preliminary version in 35th IEEE FOCS, 1994.)
• 39: Linial, N., and Wigderson, A. 2002. Course notes: Expander graphs and their applications. http://www.math.ias.edu/boaz/ExpanderCourse/.
• 40: Matoušek, J. 1997. On embedding expanders into l_p spaces. Israel J. Math. 102, 189--197.
• 41: Matoušek, J. 2002. Lectures on discrete geometry. Graduate Texts in Mathematics, vol. 212. Springer-Verlag, New York, Chapter 15 (Embedding Finite Metric Spaces into Normed Spaces), 323--362.
• 42: Mendel, M., and Har-Peled, S. 2005. Fast construction of nets in low dimensional metrics, and their applications. In Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG). ACM, New York, 150--158.
• 43: Motwani, R., and Raghavan, P. 1995. Randomized algorithms. Cambridge University Press, Cambridge, MA.
• 44: Ng, T. E., and Zhang, H. 2002. Predicting Internet network distance with coordinates-based approaches. In Proceedings of the IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA.
• 45: Parnas, M., and Ron, D. 2003. Testing metric properties. Info. Comput. 187, 2, 155--195. (Preliminary version in 33th ACM STOC, 2001.)
• 46: Percacci, R., and Vespignani, A. 2003. Scale-free behavior of the Internet global performance. Europ. Phys. J. B 32, 4, 411--414. (Also appeared as arXiv e-print cond-mat/0209619, September 2002.)
• 47: Pias, M., Crowcroft, J., Wilbur, S., Harris, T., and Bhatti, S. 2003. Lighthouses for scalable distributed location. In Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS).
• 48: Pittel, B. 1987. On spreading a rumor. SIAM J. Appl. Math. 47, 1, 213--223.
• 49: Plaxton, C. G., Rajaraman, R., and Richa, A. W. 1999. Accessing nearby copies of replicated objects in a distributed environment. Theory Comput. Syst. 32, 3, 241--280. (Preliminary version in 9th ACM SPAA, 1997.)
• 50: Semmes, S. 1996. On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A1-weights. Rev. Mat. Iberoamericana 12, 2, 337--410.
• 51: Shavitt, Y., and Tankel, T. 2003. Big-bang simulation for embedding network distances in euclidean space. In Proceedings of the IEEE INFOCOM. IEEE Computer Society Press, Los Alamitos, CA.
• 52: Slivkins, A. 2005. Distributed approaches to triangulation and embedding. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM, New York, 640--649.
• 53: Slivkins, A. 2006. Embedding, distance estimation and object location in networks. Ph.D. dissertation, Cornell University, Ithaca, NY 14850. (Available online at http://research.microsoft.com/en-us/people/slivkins.)
• 54: Slivkins, A. 2007a. Distance estimation and object location via rings of neighbors. Distrib. Comput. 19, 4 (Mar.), 313--333. (Special issue for 24th ACM PODC, 2005.)
• 55: Slivkins, A. 2007b. Towards fast decentralized construction of locality-aware overlay networks. In Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM, New York, 89--98. (Full version available online at http://research.microsoft.com/en-us/people/slivkins.)
• 56: Talwar, K. 2004. Bypassing the embedding: approximation schemes and compact representations for growth restricted metrics. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC). ACM, New York, 281--290.
• 57: Vazquez, A., Pastor-Satorras, R., and Vespignani, A. 2002. Large-scale topological and dynamical properties of Internet. Phys. Rev. E 65, 066130.
• 58: Xiao, D. Y. 2003. The evolution of expander graphs. BA dissertation, Harvard University. (Available from http://www.cs.princeton.edu/dxiao.)
• 59: Zhao, B., Huang, L., Rhea, S., Stribling, J., Joseph, A., and Kubiatowicz, J. 2004. Tapestry: A resilient global-scale overlay for service deployment. IEEE J. Select. Areas Commun. 22, 1, 41--53.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional 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; Geometrical problems and computations

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory

Keywords:
Distributed algorithms, doubling dimension, embeddings, metric spaces, triangulation