Document Open Access Logo

Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees

Authors Ramtin Afshar, Michael T. Goodrich, Evrim Ozel

PDF
Thumbnail PDF

File

LIPIcs.SEA.2022.9.pdf
  • Filesize: 12.88 MB
  • 18 pages

Document Identifiers

Author Details

Ramtin Afshar
  • University of California, Irvine, CA, USA
Michael T. Goodrich
  • University of California, Irvine, CA, USA
Evrim Ozel
  • University of California, Irvine, CA, USA

Cite As Get BibTex

Ramtin Afshar, Michael T. Goodrich, and Evrim Ozel. Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SEA.2022.9

Abstract

The completeness of road network data is significant in the quality of various routing services and applications. We introduce an efficient randomized algorithm for exact learning of road networks using simple distance queries, which can find missing roads and improve the quality of routing services. The efficiency of our algorithm depends on a cluster degree parameter, d_max, which is an upper bound on the degrees of vertex clusters defined during our algorithm. Unfortunately, we leave open the problem of theoretically bounding d_max, although we conjecture that d_max is small for road networks and other similar types of graphs. We support this conjecture by experimentally evaluating our algorithm on road network data for the U.S. and 5 European countries of various sizes. This analysis provides experimental evidence that our algorithm issues a quasilinear number of queries in expectation for road networks and similar graphs.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Random network models
  • Theory of computation → Query learning
Keywords
  • Road Networks
  • Exact Learning
  • Graph Reconstruction
  • Randomized Algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. Graph reconstruction with a betweenness oracle. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 5:1-5:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.5.
  2. Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Doerr, Kasper Green Larsen, and Kurt Mehlhorn. The query complexity of finding a hidden permutation. In Andrej Brodnik, Alejandro López-Ortiz, Venkatesh Raman, and Alfredo Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms: Papers in Honor of J. Ian Munro on the Occasion of His 66th Birthday, pages 1-11, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/978-3-642-40273-9_1.
  3. Ramtin Afshar, Amihood Amir, Michael T. Goodrich, and Pedro Matias. Adaptive exact learning in a mixed-up world: Dealing with periodicity, errors and jumbled-index queries in string reconstruction. In Christina Boucher and Sharma V. Thankachan, editors, String Processing and Information Retrieval - 27th International Symposium, SPIRE 2020, Orlando, FL, USA, October 13-15, 2020, Proceedings, volume 12303 of Lecture Notes in Computer Science, pages 155-174. Springer, 2020. URL: https://doi.org/10.1007/978-3-030-59212-7_12.
  4. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing binary trees in parallel. In Christian Scheideler and Michael Spear, editors, SPAA '20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 491-492. ACM, 2020. URL: https://doi.org/10.1145/3350755.3400229.
  5. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing biological and digital phylogenetic trees in parallel. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 3:1-3:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.3.
  6. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Parallel network mapping algorithms. In Kunal Agrawal and Yossi Azar, editors, SPAA '21: 33rd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, 6-8 July, 2021, pages 410-413. ACM, 2021. URL: https://doi.org/10.1145/3409964.3461822.
  7. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Mapping networks via parallel kth-hop traceroute queries. In Petra Berenbrink and Benjamin Monmege, editors, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022, March 15-18, 2022, Marseille, France (Virtual Conference), volume 219 of LIPIcs, pages 4:1-4:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.STACS.2022.4.
  8. Noga Alon and Vera Asodi. Learning a hidden subgraph. SIAM J. Discret. Math., 18(4):697-712, 2005. URL: https://doi.org/10.1137/S0895480103431071.
  9. Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, and Benny Sudakov. Learning a hidden matching. SIAM J. Comput., 33(2):487-501, 2004. URL: https://doi.org/10.1137/S0097539702420139.
  10. Dana Angluin and Jiang Chen. Learning a hidden hypergraph. J. Mach. Learn. Res., 7:2215-2236, 2006. URL: http://jmlr.org/papers/v7/angluin06a.html.
  11. Dana Angluin and Jiang Chen. Learning a hidden graph using o(logn) queries per edge. J. Comput. Syst. Sci., 74(4):546-556, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.006.
  12. David A. Bader, Henning Meyerhenke, Peter Sanders, and Dorothea Wagner, editors. Graph Partitioning and Graph Clustering, 10th DIMACS Implementation Challenge Workshop, Georgia Institute of Technology, Atlanta, GA, USA, February 13-14, 2012. Proceedings, volume 588 of Contemporary Mathematics. American Mathematical Society, 2013. URL: https://doi.org/10.1090/conm/588.
  13. Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihalák, and L. Shankar Ram. Network discovery and verification. IEEE J. Sel. Areas Commun., 24(12):2168-2181, 2006. URL: https://doi.org/10.1109/JSAC.2006.884015.
  14. Marshall W. Bern, David Eppstein, and F. Frances Yao. The expected extremes in a delaunay triangulation. In Javier Leach Albert, Burkhard Monien, and Mario Rodríguez-Artalejo, editors, Automata, Languages and Programming, 18th International Colloquium, ICALP91, Madrid, Spain, July 8-12, 1991, Proceedings, volume 510 of Lecture Notes in Computer Science, pages 674-685. Springer, 1991. URL: https://doi.org/10.1007/3-540-54233-7_173.
  15. Anna Bernasconi, Carsten Damm, and Igor Shparlinski. Circuit and decision tree complexity of some number theoretic problems. Information and Computation, 168(2):113-124, 2001. URL: https://doi.org/10.1006/inco.2000.3017.
  16. Melissa Chase and Seny Kamara. Structured encryption and controlled disclosure. In Masayuki Abe, editor, Advances in Cryptology - ASIACRYPT 2010 - 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings, volume 6477 of Lecture Notes in Computer Science, pages 577-594. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-17373-8_33.
  17. Sung-Soon Choi and Jeong Han Kim. Optimal query complexity bounds for finding graphs. Artificial Intelligence, 174(9):551-569, 2010. URL: https://doi.org/10.1016/j.artint.2010.02.003.
  18. Padraig Corcoran, Musfira Jilani, Peter Mooney, and Michela Bertolotto. Inferring semantics from geometry: the case of street networks. In Jie Bao, Christian Sengstock, Mohammed Eunus Ali, Yan Huang, Michael Gertz, Matthias Renz, and Jagan Sankaranarayanan, editors, Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, Bellevue, WA, USA, November 3-6, 2015, pages 42:1-42:10. ACM, 2015. URL: https://doi.org/10.1145/2820783.2820822.
  19. Luca Dall'Asta, J. Ignacio Alvarez-Hamelin, Alain Barrat, Alexei Vázquez, and Alessandro Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. Theor. Comput. Sci., 355(1):6-24, 2006. URL: https://doi.org/10.1016/j.tcs.2005.12.009.
  20. Shahar Dobzinski and Jan Vondrak. From query complexity to computational complexity. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 1107-1116, New York, NY, USA, 2012. ACM. URL: https://doi.org/10.1145/2213977.2214076.
  21. David Eppstein and Michael T. Goodrich. Studying (non-planar) road networks through an algorithmic lens. CoRR, abs/0808.3694, 2008. URL: http://arxiv.org/abs/0808.3694.
  22. David Eppstein and Siddharth Gupta. Crossing patterns in nonplanar road networks. In Erik G. Hoel, Shawn D. Newsam, Siva Ravada, Roberto Tamassia, and Goce Trajcevski, editors, Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2017, Redondo Beach, CA, USA, November 7-10, 2017, pages 40:1-40:9. ACM, 2017. URL: https://doi.org/10.1145/3139958.3139999.
  23. Martin Erwig. The graph voronoi diagram with applications. Networks, 36(3):156-163, 2000. URL: https://doi.org/10.1002/1097-0037(200010)36:3<156::AID-NET2>3.0.CO;2-L.
  24. Stefan Funke, Robin Schirrmeister, and Sabine Storandt. Automatic extrapolation of missing road network data in openstreetmap. In Ioannis Katakis, François Schnitzler, Thomas Liebig, Dimitrios Gunopulos, Katharina Morik, Gennady L. Andrienko, and Shie Mannor, editors, Proceedings of the 2nd International Workshop on Mining Urban Data co-located with 32nd International Conference on Machine Learning (ICML 2015), Lille, France, July 11th, 2015, volume 1392 of CEUR Workshop Proceedings, pages 27-35. CEUR-WS.org, 2015. URL: http://ceur-ws.org/Vol-1392/paper-04.pdf.
  25. Stefan Funke and Sabine Storandt. Provable efficiency of contraction hierarchies with randomized preprocessing. In Khaled M. Elbassioni and Kazuhisa Makino, editors, Algorithms and Computation - 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings, volume 9472 of Lecture Notes in Computer Science, pages 479-490. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-48971-0_41.
  26. Esha Ghosh, Seny Kamara, and Roberto Tamassia. Efficient graph encryption scheme for shortest path queries. In Jiannong Cao, Man Ho Au, Zhiqiang Lin, and Moti Yung, editors, ASIA CCS '21: ACM Asia Conference on Computer and Communications Security, Virtual Event, Hong Kong, June 7-11, 2021, pages 516-525. ACM, 2021. URL: https://doi.org/10.1145/3433210.3453099.
  27. Vladimir Grebinski and Gregory Kucherov. Reconstructing a hamiltonian cycle by querying the graph: Application to DNA physical mapping. Discret. Appl. Math., 88(1-3):147-165, 1998. URL: https://doi.org/10.1016/S0166-218X(98)00070-5.
  28. Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28(1):104-124, 2000. URL: https://doi.org/10.1007/s004530010033.
  29. Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Trans. Algorithms, 14(4), August 2018. URL: https://doi.org/10.1145/3199606.
  30. Valerie King, Li Zhang, and Yunhong Zhou. On the complexity of distance-based evolutionary tree reconstruction. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA, pages 444-453. ACM/SIAM, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644179.
  31. Claire Mathieu and Hang Zhou. A simple algorithm for graph reconstruction. In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 68:1-68:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ESA.2021.68.
  32. Lev Reyzinšpace0mm and Nikhil Srivastava. On the longest path algorithm for reconstructing trees from distance matrices. Inf. Process. Lett., 101(3):98-100, 2007. URL: https://doi.org/10.1016/j.ipl.2006.08.013.
  33. Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theor. Comput. Sci., 859:48-56, 2021. URL: https://doi.org/10.1016/j.tcs.2021.01.006.
  34. Raimund Seidel. Backwards analysis of randomized geometric algorithms. In János Pach, editor, New Trends in Discrete and Computational Geometry, pages 37-67. Springer Berlin Heidelberg, Berlin, Heidelberg, 1993. URL: https://doi.org/10.1007/978-3-642-58043-7_3.
  35. G. Tardos. Query complexity, or why is it difficult to separate NP^A∩ coNP^A from P^A by random oracles A? Combinatorica, 9(4):385-392, December 1989. URL: https://doi.org/10.1007/BF02125350.
  36. Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1-24, 2005. URL: https://doi.org/10.1145/1044731.1044732.
  37. M.S. Waterman, T.F. Smith, M. Singh, and W.A. Beyer. Additive evolutionary trees. Journal of Theoretical Biology, 64(2):199-213, 1977. URL: https://doi.org/10.1016/0022-5193(77)90351-4.
  38. Andrew Chi-Chih Yao. Decision tree complexity and Betti numbers. In Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC '94, pages 615-624, New York, NY, USA, 1994. ACM. URL: https://doi.org/10.1145/195058.195414.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact