Research Of Reverse K-Nearest Neighbor For Moving Objects

In recent years, mobile devices and widespread wireless networks have brought a proliferation of location-based services (LBS) applications. Location related queries play an important role in LBS. One important query type is the (monochromatic) reverse k-nearest neighbor (RkNN) queries that can find the objects whose k-nearest neighbor includes the query point. With the development of wireless technology, LBS applications are expected to provide information not only about stationary objects but also moving objects. Spatio-temporal queries for moving objects have been received increasing attention recently.Given a query point q, and a query time interval T, a reverse k-nearest neighbor for moving objects (M-RkNN) search aim to report RkNN set for every time stamp during T. Existing method (M-SAA) for processing such queries is not very efficient and applicable only to 2D data (inapplicable even for three dimensions). Motivated by this shortcoming, in this paper we propose a new algorithm named M-TPL for answering M-RkNN queries in arbitrary dimension. M-TPL adopt a filter-refinement framework and do not require any pre-computation. We introduce two novel pruning strategies named dominating cone of moving object and diagonal length property of time-parameterized MBRs for dynamic pruning.For the query point with linear movement, M-RkNN queries become further complicated. Given a moving query point q represented as a linear function of time and a query interval T, the continuous reverse k-nearest neighbor (CM-RkNN) queries can return the reverse k-nearest neighbor set of q at the new position for every time point during T. In this paper, we present and formally define CM-RkNN queries for the first time. Furthermore, we proposed a new algorithm named CM-TPL can handle such queries.Extensive experiments using large synthetic uniform and road-network based datasets prove that our proposed algorithm M-TPL has much smaller I/O and query time costs than M-SAA for M-RkNN queries in 2D. Furthermore, it can settle M-RkNN queries on dynamic multidimensional datasets and its query performance do not decline along with the increase of dimensionality. And we also prove that CM-TPL can deal with CM-RkNN queries efficiently and elegantly.