{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,9]],"date-time":"2022-11-09T14:51:50Z","timestamp":1668005510176},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","award":["81334"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["311333"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,9]]},"abstract":"\n 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\n beacon-based approach<\/jats:italic>\n one chooses uniformly at random a constant number of nodes (\u201cbeacons\u201d) 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\n triangulation<\/jats:italic>\n , in which one uses the triangle inequality to infer the distances that have not been measured.\n <\/jats:p>\n \n 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\n slack<\/jats:italic>\n \u2014a 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 + \u03b4 on a 1 \u2212 \u03f5 fraction of distances, for arbitrarily small constants \u03b4 and \u03f5. For this same class of metric spaces, we give a beacon-based embedding algorithm that achieves constant distortion on a 1 \u2212 \u03f5 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\n all<\/jats:italic>\n 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.\n <\/jats:p>","DOI":"10.1145\/1568318.1568322","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T12:53:03Z","timestamp":1252414383000},"page":"1-37","source":"Crossref","is-referenced-by-count":31,"title":["Triangulation and embedding using small sets of beacons"],"prefix":"10.1145","volume":"56","author":[{"given":"Jon","family":"Kleinberg","sequence":"first","affiliation":[{"name":"Cornell University, Ithaca, New York"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[{"name":"Microsoft Research, Mountain View, California"}]},{"given":"Tom","family":"Wexler","sequence":"additional","affiliation":[{"name":"Denison University, Granville, Ohio"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.51"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132557"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073970.1073978"},{"key":"e_1_2_1_4_1","unstructured":"Alon N. and Spencer J. 2000. The Probabilistic Method 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley New York. Alon N. and Spencer J. 2000. The Probabilistic Method 2nd ed. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley New York."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780610"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Bartal Y."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.51"},{"key":"e_1_2_1_10_1","unstructured":"Crippen G. and Havel T. 1988. Distance Geometry and Molecular Conformation. Wiley New York. Crippen G. and Havel T. 1988. Distance Geometry and Molecular Conformation. Wiley New York."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015471"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02589549"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392234"},{"key":"e_1_2_1_14_1","unstructured":"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. 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."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.958323"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/637201.637203"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press","author":"Gupta A."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/217382.217463"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Hildrum K."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IEEE International Telecommunications Symposium (ITS). IEEE Computer Society Press","author":"Huffaker B."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875596"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Indyk P. and Matou\u0161ek 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. Indyk P. and Matou\u0161ek 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.","DOI":"10.1201\/9781420035315.ch8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039491"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.70"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 12th IEEE International Conference on Network Protocols (ICNP). IEEE Computer Society Press","author":"Kommareddy C."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.41"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780607"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Krauthgamer R."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Krauthgamer R."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609302001200"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012093209450"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Linial N.","year":"2002"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365733"},{"key":"e_1_2_1_39_1","unstructured":"Linial N. and Wigderson A. 2002. Course notes: Expander graphs and their applications. http:\/\/www.math.ias.edu\/boaz\/ExpanderCourse\/. Linial N. and Wigderson A. 2002. Course notes: Expander graphs and their applications. http:\/\/www.math.ias.edu\/boaz\/ExpanderCourse\/."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773799"},{"key":"e_1_2_1_41_1","volume-title":"Graduate Texts in Mathematics","volume":"212","author":"Matou\u0161ek J.","year":"2002"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064117"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized algorithms. Cambridge University Press Cambridge MA. Motwani R. and Raghavan P. 1995. Randomized algorithms. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the IEEE INFOCOM. IEEE Computer Society Press","author":"Ng T. E."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00160-3"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjb\/e2003-00123-6"},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the 2nd International Workshop on Peer-to-Peer Systems (IPTPS).","author":"Pias M."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0147013"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/258492.258523"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4171\/RMI\/201"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the IEEE INFOCOM. IEEE Computer Society Press","author":"Shavitt Y."},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA). ACM","author":"Slivkins A.","year":"2005"},{"key":"e_1_2_1_53_1","unstructured":"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.) 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.)"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073814.1073823"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281116"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.066130"},{"key":"e_1_2_1_58_1","unstructured":"Xiao D. Y. 2003. The evolution of expander graphs. BA dissertation Harvard University. (Available from http:\/\/www.cs.princeton.edu\/dxiao.) Xiao D. Y. 2003. The evolution of expander graphs. BA dissertation Harvard University. (Available from http:\/\/www.cs.princeton.edu\/dxiao.)"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2003.818784"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1568318.1568322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T20:02:00Z","timestamp":1613937720000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1568318.1568322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":59,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["10.1145\/1568318.1568322"],"URL":"http:\/\/dx.doi.org\/10.1145\/1568318.1568322","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2009,9]]}}}