An Efficient Method for Monitoring Continuous Top-k Queries

ABSTRACT

Continuous monitoring of spatial queries has received significant research attention in the past few years. In this paper, we propose an efficient method for continuous monitoring of the top-k queries. In contrast to the conventional top-k query, a new top-k query considers both spatial and non-spatial attributes. We use a grid-based data structure and propose a novel grid access method. The proposed method (i) quickly identifies the moving objects that enter or exit the grid cells and (ii) reduces the number of unnecessary operations by comparing the bit-vector information of moving objects. Experimental simulations demonstrate that the proposed methods are several times faster than the previous methods and use considerably less memory.

References

1. Cheema, M.A., Brankovic, L., LIN, X. Zhang, W., Wang, W. 2010. Multi-guarded safe zone: An effective technique to monitor moving circular range queries. In: ICDE.
2. Xia, T., Zhang, D. 2006. Continuous reverse nearest neighbor monitoring. In: ICDE, pp. 77.
3. Yu, X., Pu, K.Q., Koudas, N. 2005. Monitoring k-nearest neighbor queries over moving objects. In: ICDE, pp. 631--6423
4. Song, Z., Reussopoulos, N. 2001. K-Nearest neighbor search for moving query point. In: Jensen, C.s., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol.2121, pp. 79--96. Springer, Heidelberg
5. X. Yu, K. Q. Pu, and N. Koudas. 2005. Monitoring k-nearest neighbor queries over moving objects. In Proc. ICDE.
6. Xiong X., Mokble M., Aref W. 2005. "SEA-CNN: Scalible Processing of Continuous K-Neares Neighbor Queries in Spatiotemporal Databases." Proceedings of ICDE Conference.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines