Distributed Processing of kNN Queries over Moving Objects on Dynamic Road Networks
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917173844246528 |
|---|---|
| author | Tao, Mingjin Jiao, Kailin Li, Yawen Liu, Wei Yu, Ziqiang |
| author_facet | Tao, Mingjin Jiao, Kailin Li, Yawen Liu, Wei Yu, Ziqiang |
| contents | The k Nearest Neighbor (kNN) query over moving objects on road networks is essential for location-based services. Recently, this problem has been studied under road networks with distance as the metric, overlooking fluctuating travel costs. We pioneer the study of the kNN problem within dynamic road networks that account for evolving travel costs. Recognizing the limitations of index-based methods, which become quickly outdated as travel costs change, our work abandons indexes in favor of incremental network expansion on each snapshot of a dynamic road network to search for kNNs. To enhance expansion efficiency, we present DkNN, a distributed algorithm that divides the road network into sub-networks for parallel exploration using Dijkstra's algorithm across relevant regions. This approach effectively addresses challenges related to maintaining global distance accuracy during local, independent subgraph exploration, while minimizing unnecessary searches in irrelevant sub-networks and facilitating the early detection of true kNNs, despite the lack of constant global search monitoring. Implemented on the Storm platform, DkNN demonstrates superior efficiency and effectiveness over traditional methods in real-world road network scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23399 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Processing of kNN Queries over Moving Objects on Dynamic Road Networks Tao, Mingjin Jiao, Kailin Li, Yawen Liu, Wei Yu, Ziqiang Databases The k Nearest Neighbor (kNN) query over moving objects on road networks is essential for location-based services. Recently, this problem has been studied under road networks with distance as the metric, overlooking fluctuating travel costs. We pioneer the study of the kNN problem within dynamic road networks that account for evolving travel costs. Recognizing the limitations of index-based methods, which become quickly outdated as travel costs change, our work abandons indexes in favor of incremental network expansion on each snapshot of a dynamic road network to search for kNNs. To enhance expansion efficiency, we present DkNN, a distributed algorithm that divides the road network into sub-networks for parallel exploration using Dijkstra's algorithm across relevant regions. This approach effectively addresses challenges related to maintaining global distance accuracy during local, independent subgraph exploration, while minimizing unnecessary searches in irrelevant sub-networks and facilitating the early detection of true kNNs, despite the lack of constant global search monitoring. Implemented on the Storm platform, DkNN demonstrates superior efficiency and effectiveness over traditional methods in real-world road network scenarios. |
| title | Distributed Processing of kNN Queries over Moving Objects on Dynamic Road Networks |
| topic | Databases |
| url | https://arxiv.org/abs/2512.23399 |