Continuous density queries for moving objects

ABSTRACT

Monitoring dense areas, where the density of moving objects is higher than the given threshold, has many applications like traffic control, bandwidth management, and collision probability evaluation. Although many studies have been done on density queries for moving objects in highly dynamic scenarios, they all focused on how to answer snapshot density queries. In this paper, we focus on continuously monitoring dense regions for moving objects. Based on the notion of safe interval, we propose effective algorithms to evaluate and keep track of dense regions. Experimental results show that our method can achieve high efficiency when monitoring dense regions for moving objects.

REFERENCES

• 1: H. G. Elmongui, M. Ouzzani, and W. G. Aref. Challenges in spatiotemporal stream query optimization. In MobiDE, pages 27--34, June 2006.
• 2: M. Hadjieleftheriou, G. Kollios, D. Gunopulos, and V. J. Tsotras. On-line discovery of dense areas in spatio-temporal databases. In SSTD, pages 306--324, July 2003.
• 3: H. Hu, J. Xu, and D. L. Lee. A generic framework for monitoring continuous spatial queries over moving objects. In SIGMOD, June 2005.
• 4: C. S. Jensen, D. Lin, B. C. Ooi, and R. Zhang. Effective density queries on continuously moving objects. In ICDE, page 71, April 2006.
• 5: I. Lazaridis, K. Porkaew, and S. Mehrotra. Dynamic queries over mobile objects. In EDBT, pages 269--286, March 2002.
• 6: M. F. Mokbel, X. Xiong, and W. G. Aref. Sina: Scalable incremental processing of continuous queries in spatio-temporal databases. In SIGMOD, pages 623--634, June 2004.
• 7: J. Ni and C. V. Ravishankar. Pointwise-dense region queries in spatio-temporal databases. In ICDE, pages 1066--1075, April 2007.
• 8: S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the positions of continuously moving objects. In SIGMOD, pages 331--342, May 2000.
• 9: Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbor search. In VLDB, pages 287--298, August 2002.
• 10: J. Xu, X. Tang, and D. L. Lee. Performance analysis of location-dependent cache invalidation schemes for mobile environments. IEEE Transactions on Knowledge and Data Engineering (TKDE), 15(2):474--488, March/April 2003.
• 11: J. Zhang, M. Zhu, D. Papadias, Y. Tao, and D. L. Lee. Location-based spatial queries. In SIGMOD, pages 443--454, June 2003.
• 12: B. Zheng and D. L. Lee. Semantic caching in location-dependent query processing. In SSTD, pages 97--116, July 2001.

INDEX TERMS

Keywords:
Quad-tree, continuous density queries, moving objects, safe interval