Continuous reverse k nearest neighbor monitoring on moving objects in road networks

Continuous reverse k nearest neighbor (CRkNN) monitoring in road networks has recently received increasing attentions. However, there is still a lack of efficient CRkNN algorithms in road networks up to now. In road networks, moving query objects and data objects are restricted by the connectivity of the road network and both the object–query distance and object–object distance updates affect the result of CRkNN queries. In this paper, we present a novel algorithm for continuous and incremental evaluation of CRkNN queries in road networks. Our method is based on a novel data structure called dual layer multiway tree (DLM tree) we proposed to represent the whole monitoring region of a CRkNN query q. We propose several lemmas to reduce the monitoring region of q and the number of candidate objects as much as possible. Moreover, by associating a variable NN_count with each candidate object, we can simplify the monitoring of candidate objects. There are a large number of objects roaming in a road network and many of them are irrelevant to a specific CRkNN query of a query object q. To minimize the processing extension, for a road in the network, we give an IQL list and an IQCL list to specify the set of query objects and data objects whose location updates should be maintained for CRkNN processing of query objects. Our CRkNN method consists of two phase: the initial result generating phase and incremental maintenance phase. In each phase, algorithms with high performance are proposed to make our CRkNN method more efficient. Extensive simulation experiments are conducted and the result shows that our proposed approach is efficient and scalable in processing CRkNN queries in road networks.     

Continuous distance-based skyline queries in road networks

In recent years, the research community has introduced various methods for processing skyline queries in road networks. A skyline query retrieves the skyline points that are not dominated by others in terms of static and dynamic attributes (i.e., the road distance). This paper addresses the issue of efficiently processing continuous skyline queries in road networks. Two novel and important distance-based skyline queries are presented, namely, the continuous  _dε-skyline$d_{\epsilon }\mathrm{-}\mathit{skyline}$query   (_Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$) and the continuous k nearest neighbor-skyline query (Cknn-SQ  ). A grid index is first designed to effectively manage the information of data objects and then two algorithms are proposed, the _Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$algorithm   and the _Cdε-SQ⁺${\mathit{Cd}}_{\epsilon }\mathrm{-}{\mathit{SQ}}^{+}$algorithm  , which are combined with the grid index to answer the _Cdε-SQ${\mathit{Cd}}_{\epsilon }\mathrm{-}\mathit{SQ}$. Similarly, the Cknn-SQ algorithm and the Cknn-SQ⁺algorithm are developed to efficiently process the Cknn-SQ. Extensive experiments using real road network datasets demonstrate the effectiveness and the efficiency of the proposed algorithms.