{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T05:34:30Z","timestamp":1673242470165},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2015,5,8]],"date-time":"2015-05-08T00:00:00Z","timestamp":1431043200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2015,10]]},"DOI":"10.1007\/s00446-015-0246-7","type":"journal-article","created":{"date-parts":[[2015,5,7]],"date-time":"2015-05-07T05:28:26Z","timestamp":1430976506000},"page":"309-320","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient distributed computation of distance sketches in networks"],"prefix":"10.1007","volume":"28","author":[{"given":"Atish Das","family":"Sarma","sequence":"first","affiliation":[]},{"given":"Michael","family":"Dinitz","sequence":"additional","affiliation":[]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,5,8]]},"reference":[{"key":"246_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., Bartal, Y., Chan, T.-H.H., Dhamdhere, K.D., Gupta, A., Kleinberg, J., Neiman, O., Slivkins, A.: Metric embeddings with relaxed guarantees. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201905, pp. 83\u2013100, Washington, DC, USA. IEEE Computer Society (2005)","DOI":"10.1109\/SFCS.2005.51"},{"key":"246_CR2","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R.M., Lipton, R.J., Lov\u00e1sz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: FOCS, pp. 218\u2013223 (1979)","DOI":"10.1109\/SFCS.1979.34"},{"issue":"3","key":"246_CR3","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1016\/j.ipl.2007.11.001","volume":"106","author":"S Baswana","year":"2008","unstructured":"Baswana, S.: Streaming algorithm for graph spanners: single pass and constant processing time per edge. Inf. Process. Lett. 106(3), 110\u2013114 (2008)","journal-title":"Inf. Process. Lett."},{"key":"246_CR4","doi-asserted-by":"crossref","unstructured":"Bharambe, A.R., Agrawal, M., Seshan, S.: Mercury: supporting scalable multi-attribute range queries. In: SIGCOMM, pp. 353\u2013366 (2004)","DOI":"10.1145\/1015467.1015507"},{"key":"246_CR5","doi-asserted-by":"crossref","unstructured":"Chan, T.-H.H., Dinitz, M., Gupta, A.: Spanners with slack. In: Proceedings of the 14th European Symposium on Algorithms, pp. 196\u2013207 (2006)","DOI":"10.1007\/11841036_20"},{"issue":"1","key":"246_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-9089-3","volume":"53","author":"R Cohen","year":"2009","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. Algorithmica 53(1), 1\u201315 (2009)","journal-title":"Algorithmica"},{"key":"246_CR7","doi-asserted-by":"crossref","unstructured":"Cooper, B.F.: Quickly routing searches without having to move content. In: IPTPS, pp. 163\u2013172 (2005)","DOI":"10.1007\/11558989_15"},{"issue":"3","key":"246_CR8","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1137\/0406029","volume":"6","author":"D Coppersmith","year":"1993","unstructured":"Coppersmith, D., Tetali, P., Winkler, P.: Collisions among random walks on a graph. SIAM J. Discret. Math. 6(3), 363\u2013374 (1993)","journal-title":"SIAM J. Discret. Math."},{"key":"246_CR9","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, vol. 24, pp. 595\u2013601. MIT Press and McGraw-Hill, Cambridge (2001)"},{"key":"246_CR10","doi-asserted-by":"crossref","unstructured":"Dabek, F., Cox, R., Kaashoek, F., Morris, R.: Vivaldi: A decentralized network coordinate system. In: Proceedings of the ACM SIGCOMM \u201904 Conference, Portland, Oregon, August (2004)","DOI":"10.1145\/1015467.1015471"},{"key":"246_CR11","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Goldberg, A.V., Johnson, D.S.: Implementation challenge for shortest paths. In: Encyclopedia of Algorithms (2008)","DOI":"10.1007\/978-0-387-30162-4_181"},{"issue":"7","key":"246_CR12","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1109\/TMC.2006.104","volume":"5","author":"S Dolev","year":"2006","unstructured":"Dolev, S., Schiller, E., Welch, J.L.: Random walk for self-stabilizing group communication in ad hoc networks. IEEE Trans. Mob. Comput. 5(7), 893\u2013905 (2006). also in PODC\u201902","journal-title":"IEEE Trans. Mob. Comput."},{"key":"246_CR13","unstructured":"Feigenbaum, J., Kannan, S., McGregor, A., Suri, S., Zhang, J.: Graph distances in the streaming model: the value of space. In: SODA, pp. 745\u2013754 (2005)"},{"issue":"3","key":"246_CR14","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1109\/TKDE.2007.46","volume":"19","author":"F Fouss","year":"2007","unstructured":"Fouss, F., Pirotte, A., Renders, J.-M., Saerens, M.: Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. Knowl. Data Eng. 19(3), 355\u2013369 (2007)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"246_CR15","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1109\/TC.2003.1176982","volume":"52","author":"AJ Ganesh","year":"2003","unstructured":"Ganesh, A.J., Kermarrec, A.-M., Massouli\u00e9, L.: Peer-to-peer membership management for gossip-based protocols. IEEE Trans. Comput. 52(2), 139\u2013149 (2003)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"246_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"246_CR17","doi-asserted-by":"crossref","unstructured":"Gkantsidis, C., Mihail, M., Saberi, A.: Hybrid search schemes for unstructured peer-to-peer networks. In: INFOCOM, pp. 1526\u20131537 (2005)","DOI":"10.1109\/INFCOM.2005.1498436"},{"key":"246_CR18","doi-asserted-by":"crossref","unstructured":"Goldberg, A.V.: Point-to-point shortest path algorithms with preprocessing. In: SOFSEM (1), pp. 88\u2013102 (2007)","DOI":"10.1007\/978-3-540-69507-3_6"},{"key":"246_CR19","doi-asserted-by":"crossref","unstructured":"Israeli, A., Jalfon, M.: Token management schemes and random walks yield self-stabilizing mutual exclusion. In: PODC, pp. 119\u2013131 (1990)","DOI":"10.1145\/93385.93409"},{"key":"246_CR20","doi-asserted-by":"crossref","unstructured":"Karger, D.R., Ruhl, M.: Simple efficient load balancing algorithms for peer-to-peer systems. In: SPAA, pp. 36\u201343 (2004)","DOI":"10.1145\/1007912.1007919"},{"issue":"1","key":"246_CR21","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1137\/S0097539703433912","volume":"34","author":"M Katz","year":"2004","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. SIAM J. Comput. 34(1), 23\u201340 (2004)","journal-title":"SIAM J. Comput."},{"key":"246_CR22","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J.M., Demers, A.J.: Spatial gossip and resource location protocols. In: STOC, pp. 163\u2013172 (2001)","DOI":"10.1145\/380752.380796"},{"key":"246_CR23","doi-asserted-by":"crossref","unstructured":"Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G., Talwar, K.: Efficient distributed approximation algorithms via probabilistic tree embeddings. In: Proceedings of 27th ACM Symposium on Principles of Distributed Computing (PODC), 2008. Journal version: Distributed Computing (2012)","DOI":"10.1007\/s00446-012-0157-9"},{"key":"246_CR24","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"M Khan","year":"2008","unstructured":"Khan, M., Pandurangan, G.: A fast distributed approximation algorithm for minimum spanning trees. Distrib. Comput. 20, 391\u2013402 (2008)","journal-title":"Distrib. Comput."},{"key":"246_CR25","doi-asserted-by":"crossref","first-page":"32:1","DOI":"10.1145\/1568318.1568322","volume":"56","author":"J Kleinberg","year":"2009","unstructured":"Kleinberg, J., Slivkins, A., Wexler, T.: Triangulation and embedding using small sets of beacons. J. ACM 56, 32:1\u201332:37 (2009)","journal-title":"J. ACM"},{"key":"246_CR26","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: The small-world phenomenon: an algorithm perspective. In: STOC, pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"246_CR27","doi-asserted-by":"crossref","unstructured":"Law, C., Siu, K.: Distributed construction of random expander networks. In: Proceedings of IEEE INFOCOM (2003)","DOI":"10.1109\/INFCOM.2003.1209234"},{"key":"246_CR28","doi-asserted-by":"crossref","unstructured":"Loguinov, D., Kumar, A., Rai, V., Ganesh, S.: Graph-theoretic analysis of structured peer-to-peer systems: routing distances and fault resilience. In: SIGCOMM, pp. 395\u2013406 (2003)","DOI":"10.1145\/863955.863999"},{"key":"246_CR29","doi-asserted-by":"crossref","unstructured":"Lv, Q., Cao, P., Cohen, E., Li, K., Shenker, S.: Search and replication in unstructured peer-to-peer networks. In: ICS, pp. 84\u201395 (2002)","DOI":"10.1145\/514191.514206"},{"key":"246_CR30","doi-asserted-by":"crossref","unstructured":"Morales, R., Gupta, I.: Avmon: Optimal and scalable discovery of consistent availability monitoring overlays for distributed systems. In: ICDCS, p. 55 (2007)","DOI":"10.1109\/ICDCS.2007.87"},{"key":"246_CR31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"246_CR32","doi-asserted-by":"crossref","unstructured":"Pandurangan, G., Khan, M.: Theory of communication networks. In: Algorithms and Theory of Computation Handbook, Second Edition. CRC Press (2009)","DOI":"10.1201\/9781584888215-c27"},{"key":"246_CR33","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)"},{"key":"246_CR34","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: ICALP, pp. 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"246_CR35","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Distance estimation and object location via rings of neighbors. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201905, pp. 41\u201350. ACM, New York, NY (2005)","DOI":"10.1145\/1073814.1073823"},{"key":"246_CR36","doi-asserted-by":"crossref","unstructured":"Slivkins, A.: Towards fast decentralized construction of locality-aware overlay networks. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC \u201907, pp. 89\u201398. ACM, New York, NY (2007)","DOI":"10.1145\/1281100.1281116"},{"issue":"1","key":"246_CR37","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"},{"key":"246_CR38","doi-asserted-by":"crossref","unstructured":"Wong, B., Slivkins, A., Sirer, E.G.: Meridian: a lightweight network location service without virtual coordinates. In: Proceedings of the 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM \u201905, pp. 85\u201396. ACM, New York, NY (2005)","DOI":"10.1145\/1080091.1080103"},{"key":"246_CR39","doi-asserted-by":"crossref","unstructured":"Yen, L., Saerens, M., Mantrach, A., Shimbo, M.: A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances. In: KDD, pp. 785\u2013793 (2008)","DOI":"10.1145\/1401890.1401984"},{"key":"246_CR40","doi-asserted-by":"crossref","unstructured":"Zhong, M., Shen, K., Seiferas, J.I.: Non-uniform random membership management in peer-to-peer networks. In: INFOCOM, pp. 1151\u20131161 (2005)","DOI":"10.1109\/INFCOM.2005.1498342"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0246-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-015-0246-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-015-0246-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,24]],"date-time":"2019-08-24T18:00:09Z","timestamp":1566669609000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-015-0246-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,8]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,10]]}},"alternative-id":["246"],"URL":"https:\/\/doi.org\/10.1007\/s00446-015-0246-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,5,8]]}}}