{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T20:51:23Z","timestamp":1777668683323,"version":"3.51.4"},"reference-count":57,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,12,16]],"date-time":"2006-12-16T00:00:00Z","timestamp":1166227200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2007,2,21]]},"DOI":"10.1007\/s00446-006-0015-8","type":"journal-article","created":{"date-parts":[[2006,12,15]],"date-time":"2006-12-15T13:13:50Z","timestamp":1166188430000},"page":"313-333","source":"Crossref","is-referenced-by-count":10,"title":["Distance estimation and object location via rings of neighbors"],"prefix":"10.1007","volume":"19","author":[{"given":"Aleksandrs","family":"Slivkins","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,12,16]]},"reference":[{"key":"15_CR1","unstructured":"Volberg, A.L., Konyagin, S.V.: On measures with the doubling condition. Izv. Acad. Nauk SSSR 51, 666\u2013675 (1987) In Russian; English transl. Math. USSR Izv. 30, 629\u2013638 (1988)"},{"key":"15_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Chan, H.T.H., Dhamdhere, K., Gupta, A., Kleinberg, J., Neiman, O., Slivkins, A.: Metric embeddings with relaxed guarantees. In: 46th Symposium on Foundations of Computer Science (FOCS), pp. 83\u2013100 (2005)","DOI":"10.1109\/SFCS.2005.51"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C.: Object location using path separators. In: 25th Annual ACM SIGACT-SIGOPS Symp. on Principles Of Distributed Computing (PODC) (2006)","DOI":"10.1145\/1146381.1146411"},{"key":"15_CR4","unstructured":"Abraham, I., Gavoille, C., Goldberg, A., Malkhi, D.: Routing in networks with low doubling dimension. In: 26th IEEE International Conference on Distributed Computing Systems (ICDCS) (2006)"},{"key":"15_CR5","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: Routing with improved communication-space trade-off. In: 18th Annual Conference on Distributed Computing (DISC), pp. 305\u2013319 (2004)","DOI":"10.1007\/978-3-540-30186-8_22"},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D.: Compact routing for graphs excluding a fixed minor. In: 19th Annual Conference on Distributed Computing (DISC), pp. 442\u2013456 (2005)","DOI":"10.1007\/11561927_32"},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"Abraham, I., Gavoille, C., Malkhi, D., Nisan, N., Thorup, M.: Compact name-independent routing with minimum stretch. In: 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 20\u201324 (2004)","DOI":"10.1145\/1007912.1007916"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Abraham, I., Malkhi, D.: Compact routing on Euclidean metrics. In: 23rd Annual ACM SIGACT-SIGOPS Symp. on Principles Of Distributed Computing (PODC), pp. 141\u2013149 (2004)","DOI":"10.1145\/1011767.1011789"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Abraham, I., Malkhi, D.: Name independent routing for growth bounded networks. In: 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 49\u201355 (2005)","DOI":"10.1145\/1073970.1073978"},{"key":"15_CR10","unstructured":"Abraham, I., Malkhi, D., Dobzinski, O.: LAND: Stretch (1 +\u00a0 \u03b5) locality-aware networks for DHTs. In: 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 550\u2013559 (2004)"},{"issue":"4","key":"15_CR11","doi-asserted-by":"crossref","first-page":"429","DOI":"10.24033\/bsmf.1997","volume":"111","author":"P. Assouad","year":"1983","unstructured":"Assouad P. (1983) Plongements lipschitziens dans R n . Bull. Soc. Math. France 111(4): 429\u2013448","journal-title":"Bull. Soc. Math. France"},{"issue":"3","key":"15_CR12","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1016\/0196-6774(90)90017-9","volume":"11","author":"B. Awerbuch","year":"1990","unstructured":"Awerbuch B., Bar-Noy A., Linial N., Peleg D. (1990) Improved routing strategies with succinct tables. J. Algorithms 11(3): 307\u2013341","journal-title":"J. Algorithms"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: 30th Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Peleg, D.: Sparse partitions. In: 31st Symposium on Foundations of Computer Science (FOCS), pp. 503\u2013513 (1990)","DOI":"10.1109\/FSCS.1990.89571"},{"key":"15_CR15","unstructured":"Chan, H.T.H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in bounded-growth metrics. In: 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 762\u2013771 (2005). Full and updated version available as a Carnegie Mellon University ETR CMU-PDL-04-106"},{"key":"15_CR16","doi-asserted-by":"crossref","first-page":"827","DOI":"10.1126\/science.1081058","volume":"301","author":"P.S. Dodds","year":"2003","unstructured":"Dodds P.S., Muhamad R., Watts D.J. (2003) An experimental study of search in global social networks. Science 301, 827\u2013829","journal-title":"Science"},{"key":"15_CR17","doi-asserted-by":"crossref","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small world? In: 19th Annual Conference on Distributed Computing (DISC), pp. 511\u2013513 (2005). Full version to appear in Theoretical Computer Science, special issue on complex networks (2006)","DOI":"10.1016\/j.tcs.2005.12.008"},{"key":"15_CR18","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.: A new perspective on the small-world phenomenon: greedy routing in tree-decomposed graphs. In: 13th Annual European Symposium on Algorithms (ESA), pp. 791\u2013802 (2005)","DOI":"10.1007\/11561071_70"},{"key":"15_CR19","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles Of Distributed Computing (PODC), pp. 169\u2013178 (2004)","DOI":"10.1145\/1011767.1011793"},{"key":"15_CR20","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Lebhar, E., Lotker, Z.: A doubling dimension threshold \u0398(log log n) for augmented graph navigability. In: 14th Annual European Symposium on Algorithms (ESA) (2006)","DOI":"10.1007\/11841036_35"},{"key":"15_CR21","unstructured":"Francis, P., Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., Zhang, L.: IDMaps: A global Internet host distance estimation service. IEEE ACM Trans. Netw. 9, 525\u2013540 (2001). Preliminary version in IEEE INFOCOM 1999"},{"issue":"5","key":"15_CR22","doi-asserted-by":"crossref","first-page":"679","DOI":"10.1006\/jpdc.2000.1705","volume":"61","author":"C. Gavoille","year":"2001","unstructured":"Gavoille C., Gengler M. (2001) Space-efficiency for routing Schemes of stretch factor three. J Parallel Distrib Comput 61(5): 679\u2013687","journal-title":"J Parallel Distrib Comput"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: 9th Annual European Symposium on Algorithms (ESA), pp. 476\u2013487 (2001)","DOI":"10.1007\/3-540-44676-1_40"},{"key":"15_CR24","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C. Gavoille","year":"2003","unstructured":"Gavoille C., Peleg D. (2003) Compact and localized distributed data tructures. J. Distrib. Comput. 16, 111\u2013120","journal-title":"J. Distrib. Comput."},{"key":"15_CR25","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Peleg, D., Perennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004). (Preliminary version in 12th ACM-SIAM SODA, 2001)","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"15_CR26","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low\u2013distortion embeddings. In: 44th Symposium on Foundations of Computer Science (FOCS), pp. 534\u2013543 (2003)","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"15_CR27","doi-asserted-by":"crossref","unstructured":"Guyton, J., Schwartz, M.: Locating nearby copies of replicated Internet servers. In: ACM SIGCOMM (1995)","DOI":"10.21236\/ADA451456"},{"key":"15_CR28","doi-asserted-by":"crossref","unstructured":"Hildrum, K., Kubiatowicz, J., Rao, S.: Object location in realistic networks. In: 16th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 25\u201335 (2004)","DOI":"10.1145\/1007912.1007918"},{"key":"15_CR29","unstructured":"Hotz, S.M.: Routing information organization to support scalable interdomain routing with heterogeneous path . Ph.D. Thesis, University of Southern California (1994)"},{"key":"15_CR30","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1038\/35022643","volume":"406","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg J. (2000) Navigation in a small world. Nature 406, 485","journal-title":"Nature"},{"key":"15_CR31","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: an algorithmic perspective. In: 32nd ACM Symposium on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"15_CR32","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Small-world phenomena and the dynamics of information. In: 15th Advances in Neural Information Processing Systems (NIPS), pp. 431\u2013438 (2001)","DOI":"10.7551\/mitpress\/1120.003.0060"},{"key":"15_CR33","unstructured":"Kleinberg, J.: Complex networks and decentralized search algorithms. In: International Congress of Mathematicians (2006)"},{"key":"15_CR34","doi-asserted-by":"crossref","unstructured":"Kleinberg, J., Slivkins, A., Wexler, T.: Triangulation and Embedding Using Small Sets of Beacons. In: 45th Symposium on Foundations of Computer Science (FOCS), pp. 444\u2013453 (2004)","DOI":"10.1109\/FOCS.2004.70"},{"key":"15_CR35","doi-asserted-by":"crossref","unstructured":"Kommareddy, C., Shankar, N., Bhattacharjee, B.: Finding close friends on the Internet. In: 12th IEEE International Conference on Network Protocols (ICNP) (2001)","DOI":"10.1109\/ICNP.2001.992910"},{"key":"15_CR36","doi-asserted-by":"crossref","unstructured":"Krauthgamer, R., Lee, J., Mendel, M., Naor, A.: Measured descent: A new embedding method for finite metrics. Geometric and Functional Analysis (GAFA) 15(4), 839\u2013858 (2005). Preliminary version in 45th IEEE FOCS (2004)","DOI":"10.1007\/s00039-005-0527-6"},{"key":"15_CR37","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 798\u2013807 (2004)"},{"key":"15_CR38","doi-asserted-by":"crossref","unstructured":"Lebhar, E., Schabanel, N.: Close to optimal decentralized routing in long-range contact networks. In: 31st International Colloquium on Automata, Languages and Programming (ICALP), pp. 894\u2013905 (2004)","DOI":"10.1007\/978-3-540-27836-8_75"},{"issue":"2","key":"15_CR39","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1090\/S0002-9939-98-04201-4","volume":"126","author":"J. Luukkainen","year":"1998","unstructured":"Luukkainen J., Saksman E. (1998) Every complete doubling metric space carries a doubling measure. Proc. Am. Math. Soc. 126(2): 531\u2013534","journal-title":"Proc. Am. Math. Soc."},{"key":"15_CR40","unstructured":"Manku, G., Bawa, M., Raghavan, P.: Symphony: distributed hashing in a small world. In: 4th USENIX Symposium on Internet Technologies and Systems (USITS) (2003)"},{"key":"15_CR41","doi-asserted-by":"crossref","unstructured":"Manku, G., Naor, M., Wieder, U.: Know thy neighbor\u2019s neighbor: the power of lookahead in randomized P2P networks. In: 36th ACM Symposium on Theory of Computing (STOC), pp. 54\u201363 (2004)","DOI":"10.1145\/1007352.1007368"},{"key":"15_CR42","doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) small-world models. In: 23rd Annual ACM SIGACT-SIGOPS Symposium on Principles Of Distributed Computing (PODC), pp. 179\u2013188 (2004)","DOI":"10.1145\/1011767.1011794"},{"key":"15_CR43","unstructured":"Martel, C., Nguyen, V.: Analyzing and characterizing small-world graphs. In: 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 311\u2013320 (2005)"},{"key":"15_CR44","doi-asserted-by":"crossref","unstructured":"Mendel, M., Har-Peled, S.: Fast construction of nets in low dimensional metrics, and their applications. In: 21st ACM Symposium on Computational Geometry (SoCG), pp. 150\u2013158 (2005)","DOI":"10.1145\/1064092.1064117"},{"key":"15_CR45","first-page":"60","volume":"2","author":"S. Milgram","year":"1967","unstructured":"Milgram S. (1967) The small world problem. Psychol Today 2, 60\u201367","journal-title":"Psychol Today"},{"key":"15_CR46","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: The 25th International Workshop on Graph\u2013Theoretical Concepts in Computer Science (LNCS 1665), pp. 30\u201341 (1999)","DOI":"10.1007\/3-540-46784-X_5"},{"key":"15_CR47","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"15_CR48","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and effciency for routing tables. J. ACM 36(3), 510\u2013530 (1989). (Preliminary version in 20th ACM STOC, 1988)"},{"key":"15_CR49","unstructured":"Plaxton, C.G., Rajaraman, R., Richa, A.W.: Accessing nearby copies of replicated objects in a distributed environment. Theory Comput. Syst. 32(3), 241\u2013280 (1999). Preliminary version in 9th ACM SPAA (1997)"},{"key":"15_CR50","unstructured":"Slivkins, A.: Distributed Approaches to Triangulation and Embedding. In: 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 640\u2013649 (2005)"},{"key":"15_CR51","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. Technical Report cul.cis\/TR2005-1977, Cornell University Computing and Information Science (2006). Available online at http:\/\/techreports.library.cornell.edu"},{"key":"15_CR52","doi-asserted-by":"crossref","unstructured":"Talwar, K.: Bypassing the embedding: approximation schemes and compact representations for growth restricted metrics. In: 36th ACM Symposium on Theory of Computing (STOC), pp. 281\u2013290 (2004)","DOI":"10.1145\/1007352.1007399"},{"key":"15_CR53","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"15_CR54","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005) (Preliminary version in 33rd ACM STOC, 2001)","DOI":"10.1145\/1044731.1044732"},{"key":"15_CR55","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D.J. Watts","year":"1998","unstructured":"Watts D.J., Strogatz S.H. (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393, 440\u2013442","journal-title":"Nature"},{"key":"15_CR56","doi-asserted-by":"crossref","unstructured":"Wong, B., Slivkins, A., Sirer, E.G.: Meridian: A Lightweight Network Location Service without Virtual Coordinates. In: ACM SIGCOMM (2005)","DOI":"10.1145\/1080091.1080103"},{"issue":"5","key":"15_CR57","doi-asserted-by":"crossref","first-page":"1453","DOI":"10.1090\/S0002-9939-98-04317-2","volume":"126","author":"J.M. Wu","year":"1998","unstructured":"Wu J.M. (1998) Hausdorff dimension and doubling measures on metric spaces. Proc. Am. Math. Soc. 126(5): 1453\u20131459","journal-title":"Proc. Am. Math. Soc."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-006-0015-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-006-0015-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-006-0015-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T10:35:56Z","timestamp":1736678156000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-006-0015-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12,16]]},"references-count":57,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,2,21]]}},"alternative-id":["15"],"URL":"https:\/\/doi.org\/10.1007\/s00446-006-0015-8","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12,16]]}}}