Approximate distance oracles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Approximate distance oracles

Full text

Pdf (220 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents

Hersonissos, Greece

Pages: 183 - 192

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Mikkel Thorup
Uri Zwick

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 58, Citation Count: 42

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/380752.380798 What is a DOI?

ABSTRACT

Let G=(V,E) be an undirected weighted graph with |V|=n and |E|=m. Let k\ge 1 be an integer. We show that G=(V,E) can be preprocessed in O(kmn^{1/k}) expected time, constructing a data structure of size O(kn^{1+1/k}), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k-1, i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1. We show that a 1963 girth conjecture of Erd{\H{o}}s, implies that &ohgr(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name ``oracle''. Previously, data structures that used only O(n^{1+1/k}) space had a query time of &ohgr(n^{1/k}) and a slightly larger, non-optimal, stretch. Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.}

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Aingworth , C. Chekuri , P. Indyk , R. Motwani, Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication), SIAM Journal on Computing, v.28 n.4, p.1167-1181, Aug. 1999 [doi>10.1137/S0097539796303421]
	2	N. Alon, S. Hoory, and N. Linial. The Moore bound for irregular graphs. Submitted for publication, 2000.
	3	N. Alon and M. Naor. Derandomization, witnesses for boolean matrix multiplication, and construction of perfect hash functions. Algorithmica, 16:434-449, 1996.
	4	N. Alon and J. Spencer. The probabilistic method. Wiley, 1992.
	5	Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
	6	Srinivasa Rao Arikati , Danny Z. Chen , L. Paul Chew , Gautam Das , Michiel H. M. Smid , Christos D. Zaroliagis, Planar Spanners and Approximate Shortest Path Queries among Obstacles in the Plane, Proceedings of the Fourth Annual European Symposium on Algorithms, p.514-528, September 25-27, 1996
	7	Baruch Awerbuch , Bonnie Berger , Lenore Cowen , David Peleg, Near-Linear Time Construction of Sparse Neighborhood Covers, SIAM Journal on Computing, v.28 n.1, p.263-277, Feb. 1999 [doi>10.1137/S0097539794271898]
	8	Baruch Awerbuch , David Peleg, Routing with polynomial communication-space trade-off, SIAM Journal on Discrete Mathematics, v.5 n.2, p.151-162, May 1992 [doi>10.1137/0405013]
	9	Yair Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.161-168, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276725]
	10	C. Benson. Minimal regular graphs of girth eight and twelve. Canadian Journal of Mathematics, 18:1091-1094, 1966.
	11	Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
	12	J. Bondy and M. Simonovits. Cycles of even length in graphs. Journal of Combinatorial Theory, Series B, 16:97-105, 1974.
	13	J. Bourgain. On libschitz embedding of finite metric spaces in hilbert space. Israel J. Math., 52:46-52, 1985.
	14	W. Brown. On graphs that do not contain a Thomsen graph. Canad. Math. Bull., 9:281-285, 1966.
	15	J. L. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sc., 18:143-154, 1979.
	16	S. Chaudhuri and C. Zaroliagis. Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica, 27:212-226, 2000.
	17	Yi-Jen Chiang , Joseph S. B. Mitchell, Two-point Euclidean shortest path queries in the plane, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.215-224, January 17-19, 1999, Baltimore, Maryland, United States
	18	Edith Cohen, Fast Algorithms for Constructing t-Spanners and Paths with Stretch t, SIAM Journal on Computing, v.28 n.1, p.210-236, Feb. 1999 [doi>10.1137/S0097539794261295]
	19	Edith Cohen , Uri Zwick, All-pairs small-stretch paths, Journal of Algorithms, v.38 n.2, p.335-353, Feb. 2001 [doi>10.1006/jagm.2000.1117]
	20	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	21	Martin Dietzfelbinger , Torben Hagerup , Jyrki Katajainen , Martti Penttonen, A reliable randomized algorithm for the closest-pair problem, Journal of Algorithms, v.25 n.1, p.19-51, Oct. 1997 [doi>10.1006/jagm.1997.0873]
	22	M. Dietzfelbinger and M. Hune. A dictionary implementaion based on dynamic perfect hashing, 1996. DIMACS 1996 Implementation Challenge. To appear in AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Science.
	23	E. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.
	24	Hristo Djidjev, On-Line Algorithms for Shortest Path Problems on Planar Digraphs, Proceedings of the 22nd International Workshop on Graph-Theoretic Concepts in Computer Science, p.151-165, June 12-14, 1996
	25	Dorit Dor , Shay Halperin , Uri Zwick, All-Pairs Almost Shortest Paths, SIAM Journal on Computing, v.29 n.5, p.1740-1759, March 2000 [doi>10.1137/S0097539797327908]
	26	M. Elkin, Computing Almost Shortest Paths,, Weizmann Science Press of Israel, Jerusalem, Israel, 2001
	27	Michael Elkin , David Peleg, (1 + &egr;&Bgr;)-spanner constructions for general graphs, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.173-182, July 2001, Hersonissos, Greece [doi>10.1145/380752.380797]
	28	P. Erd os. Extremal problems in graph theory. In Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963), pages 29-36. Publ. House Czechoslovak Acad. Sci., Prague, 1964.
	29	P. Erdos, A. Renyi, and V. Sos. On a problem of graph theory. Studia Sci. Math. Hungar., 1:215-235, 1966.
	30	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	31	Michael L. Fredman , Robert Endre Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM (JACM), v.34 n.3, p.596-615, July 1987 [doi>10.1145/28869.28874]
	32	Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
	33	S. Halperin and U. Zwick. Unpublished result, 1996.
	34	Piotr Indyk, Sublinear time algorithms for metric space problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.428-434, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301366]
	35	David R. Karger , Daphne Koller , Steven J. Phillips, Finding the hidden path: time bounds for all-pairs shortest paths, SIAM Journal on Computing, v.22 n.6, p.1199-1217, Dec. 1993 [doi>10.1137/0222071]
	36	J. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7:48-50, 1956.
	37	Felix Lazebnik , Vasiliy A. Ustimenko, New examples of graphs without small cycles and of large size, European Journal of Combinatorics, v.14 n.5, p.445-460, Sept. 1993 [doi>10.1006/eujc.1993.1048]
	38	F. Lazebnik, V. Ustimenko, and A. Woldar. A new series of dense graphs of high girth. Bulletin of the American Mathematical Society (New Series), 32(1):73-79, 1995.
	39	F. Lazebnik , V. A. Ustimenko , A. J. Woldar, A characterization of the components of the graphs D(k,q), Discrete Mathematics, v.157 n.1-3, p.271-283, Oct. 1, 1996
	40	N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215-245, 1995.
	41	A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8:261-277, 1988.
	42	G. Margulis. Explicit group-theoretical construction of combinatorial schemes and their application to the design of expanders and concentrators. Problems of Information Transmission, 24:39-46, 1988.
	43	C. McGeoch. All-pairs shortest paths and the essential subgraph. Algorithmica, 13:426-461, 1995.
	44	David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
	45	D. Peleg. Proximity-preserving labeling schemes. J. Graph Theory, 33:167-176, 2000.
	46	D. Peleg and A. Schaffer. Graph spanners. J. Graph Theory, 13:99-116, 1989.
	47	I. Reiman. Uber ein Problem von K. Zarankiewicz. Acta. Math. Acad. Sci. Hungar., 9:269-273, 1958.
	48	Avi Shoshan , Uri Zwick, All Pairs Shortest Paths in Undirected Graphs with Integer Weights, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.605, October 17-18, 1999
	49	Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999 [doi>10.1145/316542.316548]
	50	Mikkel Thorup, Even strongly universal hashing is pretty fast, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.496-497, January 09-11, 2000, San Francisco, California, United States
	51	Mikkel Thorup, Floats, integers, and single source shortest paths, Journal of Algorithms, v.35 n.2, p.189-201, May 2000 [doi>10.1006/jagm.2000.1080]
	52	M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs, 2001. Submitted.
	53	Mikkel Thorup, Quick k-Median, k-Center, and Facility Location for Sparse Graphs, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.249-260, July 08-12, 2001
	54	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]
	55	J. Tits. Sur la trialite et certains groupes qui s'en d eduisent. Publ. Math. I.H.E.S., 2:14-20, 1959.
	56	R. Wenger, Extremal graphs with no C4,s, or C10,s, Journal of Combinatorial Theory Series B, v.52 n.1, p.113-116, May 1991 [doi>10.1016/0095-8956(91)90097-4]
	57	J. Williams. Heapsort. Comm. ACM, 7(5):347-348, 1964.
	58	A. Woldar and V. Ustimenko. An application of group theory to extremal graph theory. In Group theory, Proceedings of the Ohio State-Denison Conference, pages 293-298. World Sci. Publishing, River Edge, NJ, 1993.
	59	Uri Zwick, All Pairs Shortest Paths in weighted directed graphs ? exact and almost exact algorithms, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.310, November 08-11, 1998

CITED BY 42

	Edith Cohen , Eran Halperin , Haim Kaplan , Uri Zwick, Reachability and distance queries via 2-hop labels, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.937-946, January 06-08, 2002, San Francisco, California
	Liam Roditty , Mikkel Thorup , Uri Zwick, Roundtrip spanners and roundtrip routing in directed graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-851, January 06-08, 2002, San Francisco, California
	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
	Béla Bollobás , Don Coppersmith , Michael Elkin, Sparse distance preservers and additive spanners, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Stephen Alstrup , Philip Bille , Theis Rauhe, Labeling schemes for small distances in trees, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.828-837, January 06-08, 2002, San Francisco, California
	Surender Baswana , Ramesh Hariharan , Sandeep Sen, Maintaining all-pairs approximate shortest paths under deletion of edges, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Marta Arias , Lenore J. Cowen , Kofi A. Laing , Rajmohan Rajaraman , Orjeta Taka, Compact routing with name independence, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA
	Kirsten Hildrum , John D. Kubiatowicz , Satish Rao , Ben Y. Zhao, Distributed object location in a dynamic network, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
	Cyril Gavoille , David Peleg, Compact and localized distributed data structures, Distributed Computing, v.16 n.2-3, p.111-120, September 2003
	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
	Kirsten Hildrum , John Kubiatowicz , Sean Ma , Satish Rao, A note on the nearest neighbor in growth-restricted metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Surender Baswana , Sandeep Sen, Approximate distance oracles for unweighted graphs in Õ (n²) time, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	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
	Kunal Talwar, Bypassing the embedding: algorithms for low dimensional metrics, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	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
	Philip Klein, Preprocessing an undirected planar network to enable fast approximate distance queries, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.820-827, January 06-08, 2002, San Francisco, California
	Kofi A. Laing , Rajmohan Rajaraman, A space lower bound for name-independent compact routing in trees, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Don Coppersmith , Michael Elkin, Sparse source-wise and pair-wise distance preservers, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA
	Surender Baswana , Telikepalli Kavitha , Kurt Mehlhorn , Seth Pettie, New constructions of (α, β)-spanners and purely additive spanners, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	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
	Michael Elkin, Computing almost shortest paths, ACM Transactions on Algorithms (TALG), v.1 n.2, p.283-323, October 2005
	Mikkel Thorup, Compact oracles for reachability and approximate distances in planar digraphs, Journal of the ACM (JACM), v.51 n.6, p.993-1024, November 2004
	Feodor F. Dragan, Estimating all pairs shortest paths in restricted graph families: a unified approach, Journal of Algorithms, v.57 n.1, p.1-21, September 2005
	Jie Gao , Li Zhang, Well-separated pair decomposition for the unit-disk graph metric and its applications, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	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
	Feodor F. Dragan , Irina Lomonosov, On compact and efficient routing in certain graph classes, Discrete Applied Mathematics, v.155 n.11, p.1458-1470, June, 2007
	Ming-Yang Kao , Xiang-Yang Li , Weizhao Wang, Average case analysis for tree labelling schemes, Theoretical Computer Science, v.378 n.3, p.271-291, June, 2007
	Yon Dourisboure , Feodor F. Dragan , Cyril Gavoille , Chenyu Yan, Spanners for bounded tree-length graphs, Theoretical Computer Science, v.383 n.1, p.34-44, September, 2007
	Mattias Andersson , Joachim Gudmundsson , Christos Levcopoulos, Approximate distance oracles for graphs with dense clusters, Computational Geometry: Theory and Applications, v.37 n.3, p.142-154, August, 2007
	Ittai Abraham , Cyril Gavoille , Dahlia Malkhi , Noam Nisan , Mikkel Thorup, Compact name-independent routing with minimum stretch, ACM Transactions on Algorithms (TALG), v.4 n.3, p.1-12, June 2008
	Dmitri Krioukov , k c claffy , Kevin Fall , Arthur Brady, On compact routing for the internet, ACM SIGCOMM Computer Communication Review, v.37 n.3, July 2007
	Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan , Michiel Smid, Approximate distance oracles for geometric spanners, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-34, March 2008
	Michael Elkin, A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Liam Roditty , Michael Segal, On bounded leg shortest paths problems, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.775-784, January 07-09, 2007, New Orleans, Louisiana
	Gonzalo Navarro , Rodrigo Paredes , Edgar Chávez, t-Spanners for metric space searching, Data & Knowledge Engineering, v.63 n.3, p.820-854, December, 2007
	Monique V. Vieira , Bruno M. Fonseca , Rodrigo Damazio , Paulo B. Golgher , Davi de Castro Reis , Berthier Ribeiro-Neto, Efficient search ranking in social networks, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Marta Arias , Lenore J. Cowen , Kofi A. Laing, Compact roundtrip routing with topology-independent node names, Journal of Computer and System Sciences, v.74 n.5, p.775-795, August, 2008
	Jiefeng Cheng , Jeffrey Xu Yu, On-line exact shortest distance query processing, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia