Journals
  Publication Years
  Keywords
Search within results Open Search
Please wait a minute...
For Selected: Toggle Thumbnails
Dynamic aggregate nearest neighbor query algorithm in weighted road network space
Fangshu CHEN, Wei ZHANG, Xiaoming HU, Yufei ZHANG, Xiankai MENG, Linxiang SHI
Journal of Computer Applications    2023, 43 (7): 2026-2033.   DOI: 10.11772/j.issn.1001-9081.2022091371
Abstract194)   HTML5)    PDF (2757KB)(181)       Save

As a classical problem in spatial databases, Aggregate Nearest Neighbor (ANN) query is of great importance in the optimization of network link structures, the location selection of logistics distribution points and the car-sharing services, and can effectively contribute to the development of fields such as logistics, mobile Internet industry and operations research. The existing research has some shortcomings: lack of efficient index structure for large-scale dynamic road network data, low query efficiency of the algorithms when the data point locations move in real time and network weights update dynamically. To address these problems, an ANN query algorithm in dynamic scenarios was proposed. Firstly, with adopting G-tree as the road network index, a pruning algorithm combining spatial index structures such as quadtrees and k-d trees with the Incremental Euclidean Restriction (IER) algorithm was proposed to solve ANN queries in statistic space. Then, aiming at the issue of frequent updates of data point locations in dynamic scenarios, the time window and safe zone update strategy were added to reduce the iteration times of the algorithm, experimental results showed that the efficiency could be improved by 8% to 85%. Finally, for ANN query problems with road network weight changed, based on historical query results, two correction based continuous query algorithms were proposed to obtain the current query results according to the increment of weight changes. In certain scenarios, these algorithms can reduce errors by approximately 50%. The theoretical research and experimental results show that the proposed algorithms can solve the ANN query problems in dynamic scenarios efficiently and more accurately.

Table and Figures | Reference | Related Articles | Metrics