Graph-decomposed k-NN searching algorithm on road network
image: Figure 1
Credit: Wei JIANG, Bo NING, Guanyu LI, Mei BAI, Xiao JIA, Fangliang WEI
With the rapid development of mobile networks, location-based services have become deeply embedded in people's daily lives. Although the k-NN search problem has obtained a lot of research results, the search problem on road networks still faces many challenges due to the nature of frequent movement of objects on road networks. One of the most straightforward solutions is to utilize Dijkstra's algorithm, which searches k nodes from the remaining nodes to a target node in non-decreasing distance order. A tree-based decomposition solution to the k-NN search problem is designed into the TEN-Query algorithm. A tree-based decomposition index is proposed to convert the graph into a tree structure, where local search results are pre-computed and indexed. However, most indicators are limited by the size of the k value.
To solve the problems, a research team led by Wei JIANG published their new research on 15 June 2024 in Frontiers of Computer Science co-published by Higher Education Press and Springer Nature.
The team proposed Graph-Decomposed k-NN Searching Algorithm to improve the time-efficiency of nearest nodes searching.
In the research, A graph-decomposed tree is constructed from road network. All nodes of the road network are first abstracted as tree nodes, then tree nodes are constructed as a graph-decomposed tree, the tree nodes are connected into a tree based on the weighted cost model.
The pruning strategy can improve the time-efficiency of k-NN searching algorithm, displayed in Algorithm 1, that can be divided into three subroutines. The first subroutine is used to construct a graph-decomposed tree of road network (Section 3.1 and Line 1). The second subroutine is the key step of kNN searching to find all the shortest path from nodes to query node (Lines 2-9). The query node weighted by 0 is initially added to the candidate set (Line 2), then the verification of minimum common ancestor between query node and data node is determined for different processing strategies to calculate the shortest path.
This paper designs a novel algorithm of kNN searching on road network. A graph-decomposed tree is constructed from road network based on one abstracted rule and a cost model, then a graph-decomposed kNN searching algorithm is proposed to improve the query time-efficiency. Extensive empirical studies on real and synthetic graphs demonstrate that our techniques outperform the state-of-the-art algorithms on six datasets.