High-Throughput k Nearest Neighbors Search in Road Networks
Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-26
DOI: 10.1145/3786656 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Yu Kong und 3 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Gefördert von: Australian Research Council, National Natural Science Foundation of China.
Abstract (Originalsprache)
Searching for the k nearest neighbors ( k NN) among a given object set is a fundamental problem in road networks. In many real-world applications, such as location-based services, the object set is dynamic, with frequent insertions and deletions. In such workloads, throughput reflects the overall efficiency of an algorithm in handling both frequent queries and updates. The state-of-the-art solutions often suffer from slow query performance or inefficient index maintenance, which can result in low or even zero throughput. We propose a local subgraph-based indexing framework designed to support high-throughput query processing under frequent object updates. Unlike global indexing methods, our framework confines each update to a limited number of related local subgraphs, significantly reducing index maintenance overhead. To optimize throughput, we also introduce an efficient query processing strategy that incrementally explores only the necessary boundary vertices in relevant parts of our index, thereby pruning unnecessary computations. We formally prove that k NN results computed using only local subgraph information remain globally correct. Extensive experiments are conducted on 13 large real-world road networks to demonstrate the effectiveness and efficiency of our proposed solution.
Förderung
- Australian Research Council
- National Natural Science Foundation of China
Zitieren
APA
Kong, Y., Chang, L., Wen, D., & Ouyang, D. (2026). High-Throughput k Nearest Neighbors Search in Road Networks. Proceedings of the ACM on Management of Data, 4(1), 1-26. https://doi.org/10.1145/3786656
Vancouver
Kong Y, Chang L, Wen D, Ouyang D. High-Throughput k Nearest Neighbors Search in Road Networks. Proceedings of the ACM on Management of Data. 2026;4(1):1-26. doi:10.1145/3786656
BibTeX
@article{Kong2026,
author = {Kong, Yu and Chang, Lijun and Wen, Dong and Ouyang, Dian},
title = {High-Throughput k Nearest Neighbors Search in Road Networks},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {1},
pages = {1--26},
doi = {10.1145/3786656}
}
EUVIMED