License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2022.9
URN: urn:nbn:de:0030-drops-165432
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16543/
Afshar, Ramtin ;
Goodrich, Michael T. ;
Ozel, Evrim
Efficient Exact Learning Algorithms for Road Networks and Other Graphs with Bounded Clustering Degrees
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}
}
