Volume 20 Issue 3 - October 21, 2011 PDF
Continuous Reverse k-nearest Neighbor Monitoring on Moving Objects in Road Networks
Li Guohui1, Li Yanhong1, Li Jianjun1, LihChyun Shu2*, Yang Fumin1
1School of Computer Science & Technology, Huazhong University of Science & Technology, PRChina
2Department of Accountancy, National Cheng Kung University, Taiwan 701, ROC
Font Enlarge
This research studies the problem of continuous reverse k-nearest neighbor (CRkNN) query processing in road networks. A reverse k-nearest neighbor (RkNN) query returns the data objects that have the query object in the set of their k-nearest neighbors. It is the complimentary problem to that of finding the k-nearest neighbors (kNN) of a query object and has been studied extensively in the past few years.  Although there are a few algorithms available for finding RkNN of a query in Euclidean space, they are not suitable for RkNN query processing in road networks. We propose an efficient method for CRkNN query processing in road networks where both queries and objects move arbitrarily in a road network.

Our method consists of two phases, the initial-result generation phase and the incremental maintenance phase. In the initial phase, an initial RkNN result set, called IniCRkNN, is obtained and the monitored region of the query in question is calculated. We use a novel data structure, called DLM tree, to represent the monitored region of the query. The DLM tree is a dual layer multiway tree whose top layer is the monitored area of all RkNN candidates, called the range tree, and the bottom layer is the verifying areas of all candidates, called the verifying tree. With the DLM tree, we reduce the problem of processing a CRkNN query into monitoring a DLM tree. We can incrementally refine the CRkNN result, rather than re-computing it from scratch every time there is a location update. We prove several important facts that allow us to minimize the size of the tree and the number of candidate objects.

We evaluate the performance of our algorithms through simulation experiments. We compare our method with a method that calculates IniCRkNN at each time instant, which we call NAV. In general, our method is about 1.9 times faster than NAV, and it is robust with respect to the value of k, query cardinality, object cardinality, query mobility, object mobility, query speed and the size of network. In summary, our method is both efficient and scalable.
< Previous
Next >
Copyright National Cheng Kung University