High-Throughput k Nearest Neighbors Search in Road Networks

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.