CLG-Tree: A New Index for Large-Scale Network kNN Queries

The kNN (k Nearest Neighbor) query in road network environments is a critical issue in location-based services that has received a lot of attention in the industry. As real road networks become more complex and the number of moving objects increases rapidly, so does the number of queries, posing significant challenges to real-time kNN queries based on road networks. kNN query methods based on tree indexes (such as G-Tree and G*-Tree) are currently widely used as efficient methods in the industry, but when two query points are far apart in the index, the query must traverse a large number of tree nodes, making them less efficient for long-distance queries in large road networks. To address this issue, we propose a CLG-Tree (Combination Method of G-Tree and Hub Labeling) index structure that employs a hierarchical labeling method. CLG-Tree optimizes the G-Tree by generating hierarchical labels for boundary nodes and creates a new kNN query algorithm called IAA-kNN (Improved Assembly Algorithm) that uses the CLG-Tree index. To improve query efficiency, IAAkNN employs dynamic programming and label merging algorithms to address the issue of traversing too many tree nodes when dealing with long-distance queries. Experiments on the DIMACS dataset demonstrate that the IAA-kNN algorithm outperforms G-Tree-kNN.