Papers › Kharita: Robust Map Inference using Graph Spanners
Kharita: Robust Map Inference using Graph Spanners
Rade Stanojevic, Sofiane Abbar, Saravanan Thirumuruganathan, Sanjay Chawla, Fethi Filali, Ahid Aleimat
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The widespread availability of GPS information in everyday devices such as cars, smartphones and smart watches make it possible to collect large amount of geospatial trajectory information. A particularly important, yet technically challenging, application of this data is to identify the underlying road network and keep it updated under various changes. In this paper, we propose efficient algorithms that can generate accurate maps in both batch and online settings. Our algorithms utilize techniques from graph spanners so that they produce maps can effectively handle a wide variety of road and intersection shapes. We conduct a rigorous evaluation of our algorithms over two real-world datasets and under a wide variety of performance metrics. Our experiments show a significant improvement over prior work. In particular, we observe an increase in Biagioni f-score of up to 20% when compared to the state of the art while reducing the execution time by an order of magnitude. We also make our source code open source for reproducibility and enable other researchers to build on our work.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections