More Web Proxy on the site http://driver.im/

research-article

Approximate Distance Oracles with Improved Bounds

Author:

Shiri ChechikAuthors Info & Claims

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

Pages 1 - 10

https://doi.org/10.1145/2746539.2746562

Published: 14 June 2015 Publication History

Abstract

A distance oracle is a compact data structure capable of quickly estimating distances in a given graph. In this paper we provide a new construction for distance oracles in general undirected weighted graphs. Our data structure, for any integer k, requires O( n^1+1/k) space, guarantees a stretch of 2k-1, and answers any query in only O(1) time.

References

[1]

I. Abraham, and C. Gavoille. On Approximate Distance Labels and Routing Schemes with Affine Stretch. DISC, 404--415, 2011.

Digital Library

[2]

I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81--100, 1993.

[3]

B. Awerbuch, B. Berger, L. Cowen, and D. Peleg. Near-linear time construction of sparse neighborhood covers. In SIAM J. Comput., Vol. 28, No. 1, 263--277, 1998.

Digital Library

[4]

S. Baswana, A. Gaur, S. Sen and J. Upadhyay. Distance oracles for unwieghted graphs: Breaking the quadratic barrier with constant additive error. In ICALP, pages 609--621, 2008.

Digital Library

[5]

S. Baswana and T. Kavitha. Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In Proc. IEEE Symp. on Foundations of Computer Science (FOCS), 591--602, 2006.

Digital Library

[6]

S.Chechik. Approximate Distance Oracles with Constant Query Time. To appear in Proc. 46th ACM Symp. on Theory of Computing (STOC), 2014.

Digital Library

[7]

E. Cohen. Fast algorithms for constructing $t$-spanners and paths with stretch $t$. SIAM J. Comput., 28:210--236, 1998.

Digital Library

[8]

P. Erdos. Extremal problems in graph theory. In Theory of graphs and its applications, pages 29--36, 1964.

[9]

J. Matousek. On the distortion required for embeding finite metric spaces into normed spaces. In Israel Journal of Math 93, 333--344, 1996.

[10]

M. Mendel, and A. Naor. Ramsey partitions and proximity data structures In Proc. 47th IEEE Symp. on Foundations of Computer Science (FOCS), 109--118, 2006.

Digital Library

[11]

M. Mendel, and A. Naor. Ramsey partitions and proximity data structures. In Journal of the European Mathematical Society, 9:2, 253--275, 2007.

[12]

M. Mendel and C. Schwob. Fast C-K-R Partitions of Sparse Graphs. In Journal of Theoretical Comp. Sci., (2), 1--18, 2009.

[13]

A. Naor, and T. Tao. Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem. In Israel Journal of Mathematics, 192,489--504, 2012.

[14]

M. Patrascu and L. Roditty. Distance oracles beyond the thorup-zwick bound. In FOCS, pages 815--823, 2010.

Digital Library

[15]

M. Patrascu, L. Roditty and M. Thorup. A New Infinity of Distance Oracles for Sparse Graphs In FOCS, pages 738--747, 2012.

Digital Library

[16]

L. Roditty, M. Thorup, and U. Zwick. Deterministic constructions of approximate distance oracles and spanners. In Proc. 32nd Int. Colloq. on Automata, Languages & Prog., 261--272, 2005.

Digital Library

[17]

C. Sommer. Shortest-Path Queries in Static Networks In ACM Computing Surveys,46(4), 2014.

Digital Library

[18]

M. Thorup and U. Zwick. Approximate distance oracles. In J. ACM, 52, 1--24, 2005.

Digital Library

[19]

C. Wulff-Nilsen. Approximate Distance Oracles with Improved Preprocessing Time. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA),202--208,2012.

Digital Library

[20]

C. Wulff-Nilsen. Approximate Distance Oracles with Improved Query Time. In Proc. 24th ACM-SIAM Symp. on Discrete Algorithms (SODA), 539--549, 2013.

Digital Library

Cited By

Bilò DChechik SChoudhary KCohen SFriedrich TSchirneck M(2024)Improved Distance (Sensitivity) Oracles with Subquadratic Space2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00097(1550-1558)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00097
Meng XXie WCui J(2024)RGCNdist2vec: Using Graph Convolutional Networks and Distance2Vector to Estimate Shortest Path Distance Along Road NetworksSpatial Data and Intelligence10.1007/978-981-97-2966-1_13(174-187)Online publication date: 30-Apr-2024
https://doi.org/10.1007/978-981-97-2966-1_13
Charalampopoulos PGawrychowski PLong YMozes SPettie SWeimann OWulff-Nilsen C(2023)Almost Optimal Exact Distance Oracles for Planar GraphsJournal of the ACM10.1145/358047470:2(1-50)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3580474
Show More Cited By

Index Terms

Approximate Distance Oracles with Improved Bounds
1. Theory of computation

Recommendations

Approximate distance oracles with constant query time
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes of a given graph.

In this paper we consider approximate distance oracles for general undirected graphs with non-negative ...
Approximate distance oracles for unweighted graphs in expected O(n²) time

Let G = (V, E) be an undirected graph on n vertices, and let δ(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive integer t, the graph G can be preprocessed to build a data structure that can ...
Approximate distance oracles

Let G = (V,E) be an undirected weighted graph with |V| = n and |E| = m. Let k ≥ 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '15: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing

June 2015

916 pages

ISBN:9781450335362

DOI:10.1145/2746539

General Chair:
Rocco Servedio
Columbia University
,
Program Chair:
Ronitt Rubinfeld
MIT and Tel Aviv University

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '15

Sponsor:

SIGACT

STOC '15: Symposium on Theory of Computing

June 14 - 17, 2015

Oregon, Portland, USA

Acceptance Rates

STOC '15 Paper Acceptance Rate 93 of 347 submissions, 27%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
762
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)6

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bilò DChechik SChoudhary KCohen SFriedrich TSchirneck M(2024)Improved Distance (Sensitivity) Oracles with Subquadratic Space2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00097(1550-1558)Online publication date: 27-Oct-2024
https://doi.org/10.1109/FOCS61266.2024.00097
Meng XXie WCui J(2024)RGCNdist2vec: Using Graph Convolutional Networks and Distance2Vector to Estimate Shortest Path Distance Along Road NetworksSpatial Data and Intelligence10.1007/978-981-97-2966-1_13(174-187)Online publication date: 30-Apr-2024
https://doi.org/10.1007/978-981-97-2966-1_13
Charalampopoulos PGawrychowski PLong YMozes SPettie SWeimann OWulff-Nilsen C(2023)Almost Optimal Exact Distance Oracles for Planar GraphsJournal of the ACM10.1145/358047470:2(1-50)Online publication date: 25-Mar-2023
https://dl.acm.org/doi/10.1145/3580474
Abboud ABringmann KFischer NSaha BServedio R(2023)Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive CombinatoricsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585240(391-404)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585240
Roditty LSaha BServedio R(2023)New Algorithms for All Pairs Approximate Shortest PathsProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585197(309-320)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585197
Elkin MShabat I(2023)Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00141(2278-2311)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00141
Karczmarz ASankowski P(2023)Sensitivity and Dynamic Distance Oracles via Generic Matrices and Frobenius Form2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00106(1745-1756)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00106
Roditty LTov R(2023)Approximate distance oracles with improved stretch for sparse graphsTheoretical Computer Science10.1016/j.tcs.2022.11.016943(89-101)Online publication date: Jan-2023
https://doi.org/10.1016/j.tcs.2022.11.016
Liu SWang XWeiszer MChen J(2023)Extracting Multi-objective Multigraph Features for the Shortest Path Cost Prediction: Statistics-based or Learning-based?Green Energy and Intelligent Transportation10.1016/j.geits.2023.100129(100129)Online publication date: Oct-2023
https://doi.org/10.1016/j.geits.2023.100129
Bilò DChoudhary KCohen SFriedrich TKrogmann SSchirneck M(2023)Compact Distance Oracles with Large Sensitivity and Low StretchAlgorithms and Data Structures10.1007/978-3-031-38906-1_11(149-163)Online publication date: 28-Jul-2023
https://doi.org/10.1007/978-3-031-38906-1_11
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents