Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Afshar, Ramtin; Goodrich, Michael T.; Ozel, Evrim https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-165432
URL:

; ;

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

pdf-format:


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.

BibTeX - Entry

@InProceedings{afshar_et_al:LIPIcs.SEA.2022.9,
  author =	{Afshar, Ramtin and Goodrich, Michael T. and Ozel, Evrim},
  title =	{{Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees}},
  booktitle =	{20th International Symposium on Experimental Algorithms (SEA 2022)},
  pages =	{9:1--9:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-251-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{233},
  editor =	{Schulz, Christian and U\c{c}ar, Bora},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16543},
  URN =		{urn:nbn:de:0030-drops-165432},
  doi =		{10.4230/LIPIcs.SEA.2022.9},
  annote =	{Keywords: Road Networks, Exact Learning, Graph Reconstruction, Randomized Algorithms}
}

Keywords: Road Networks, Exact Learning, Graph Reconstruction, Randomized Algorithms
Seminar: 20th International Symposium on Experimental Algorithms (SEA 2022)
Issue date: 2022
Date of publication: 11.07.2022
Supplementary Material: Software (Source Code): https://github.com/UC-Irvine-Theory/RoadNetworkReconstruction archived at: https://archive.softwareheritage.org/swh:1:dir:337dc5ac6d78bd68031d6f94b24332b935797a67


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI