Reverse K Nearest Neighbor Query in Large Road Networks: a Tree Decomposition Based Approach

Reverse k-nearest neighbor (R $k$ NN) query in road networks is an important and fundamental problem. Given a facility query vertex $q$, an $\mathrm{R} k \text{NN}$ query asks for finding all user vertices such that each of them regards $q$ as one of the $k$ nearest neighbors $(k \text{NN})$. Although $\mathbf{R} k \mathbf{N N}$ has a wide range of applications, such as location selection, influential domain analysis, potential customer analysis, we note that this problem has not been well addressed. Existing solutions typically need to traverse the graph and perform $k \text{NN}$ queries for every vertex in a non-decreasing order of their distances to the query vertex, which incurs high computational cost, especially for large graphs. In this paper, we develop a novel tree decomposition based approach, namely TD-Query. In general, a tree decomposition can be considered as an index to store the hierarchical decomposition of the graph. By making use of the nice properties of the tree decomposition, we develop useful search branch pruning techniques such that we can avoid traversing the entire graph. Observing that TD-Query may still visit many result irrelevant nodes during the traversal, we propose an advanced approach, termed ATD-Query. In specific, we first identify a set of critical nodes in the tree decomposition. Based on these critical nodes, we then construct an augmented tree decomposition by storing auxiliary data structures for tree nodes with little space and time overhead. On top of the augmented tree decomposition, ATD-Query can collect the query results by only visiting a subset of critical nodes, and hence substantially improve the query efficiency. We conduct extensive experiments on 8 reallife road networks, and the experimental results demonstrate that ATD-Query can achieve up to an order of magnitude performance improvement over the state-of-the-art algorithm, while consuming much less memory for index structure.