An efficient approach for continuous density queries

Abstract

In location-based services, a density query returns the regions with high concentrations of moving objects (MOs). The use of density queries can help users identify crowded regions so as to avoid congestion. Most of the existing methods try very hard to improve the accuracy of query results, but ignore query efficiency.However, response time is also an important concern in query processing and may have an impact on user experience. In order to address this issue, we present a new definition of continuous density queries. Our approach for processing continuous density queries is based on the new notion of a safe interval, using which the states of both dense and sparse regions are dynamically maintained. Two indexing structures are also used to index candidate regions for accelerating query processing and improving the quality of results. The efficiency and accuracy of our approach are shown through an experimental comparison with snapshot density queries.

Keywords

continuous density queries / safe interval / query efficiency

References

[1] Hadjieleftheriou M, Kollios G, Gunopulos D, Tsotras V J. On-line discovery of dense areas in spatio-temporal databases. In: Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases. 2003, 306-324

[2] Jensen C S, Lin D, Ooi B C, Zhang R. Effective density queries on continuously moving objects. In: Proceedings of the 22nd International Conference on Data Engineering. 2006

[3] Ni J, Ravishankar C V. Pointwise-dense region queries in spatiotemporal databases. In: Proceedings of the 23rd International Conference on Data Engineering. 2007, 1066-1075

[4] Lai C,Wang L, Chen J D, Meng X F. Effective density queries for moving objects in road networks. In: Proceedings of the 9th Asia-Pacific Web Conference and the 8th International Conference on Web-Age Information Management. 2007, 200-211

[5] Elmongui H G, Ouzzani M, Aref W G. Challenges in spatio-temporal stream query optimization. In: Proceedings of the 5th International ACMWorkshop on Data Engineering forWireless and Mobile Access. 2006, 27-34

[6] Zhang J, Zhu M, Papadias D, Tao D, Lee D L. Location-based spatial queries. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data. 2003, 443-454

[7] Zheng B, Lee D L. Semantic caching in location-dependent query processing. In: Proceedings of the 7th International Symposium on Spatial and Temporal Databases. 2001, 97-116

[8] Xu J, Tang X, Lee D L. Performance analysisi of location-dependent cache invalidation schemes for mobile environments. IEEE Transaction on Knowledge and Data Engineering, 2003, 15(2): 474-488

[9] Lazaridis I, Porkaew K, Mehrotra S. Dynamic queries over mobile objects. In: Proceedings of the 8th International Conference on Extending Database Technology. 2002, 269-286

[10] Mokbel M F, Xiong X, Aref W G. Sina: scalable incremental processing of continuous queries in spatio-temporal databases. In: Proceeding of the 2004 ACM SIGMOD International Conference on Management of Data. 2004, 623-634

[11] Hu H, Xu J, Lee D L. A generic framework for monitoring continuous spatial queries over moving objects. In: Proceeding of the 2005 ACM SIGMOD International Conference on Management of Data. 2005, 479-490

[12] Dai D, Lu C, Lai L. A concurrency control protocol for continuously monitoring moving objects. In: Proceedings of the 10th International Conference on Mobile Data Management. 2009, 132-141

[13] Tanin E, Chen S, Tatemura J, Hsiung H. Monitoring moving objects using low frequency snapshots in sensor networks. In: Proceedings of the 9th International Conference on Mobile Data Management. 2008, 25-32

[14] Tao Y, Papadias D, Shen Q. Continuous nearest neighbor search. In: Proceedings of the 28th International Conference on Very Large Data Bases. 2002, 287-298

[15] Kolahdouzan M, Shahabi C. Continuous k-nearest neighbor queries in spatial network databases. In: Proceedings of the 2nd International Workshop on Spatio-Temporal Database Management. 2004, 57-64

[16] Do T, Hua K. ExtRange: continuous moving range queries in mobile peer-to-peer networks. In: Proceedings of the 10th International Conference on Mobile Data Management. 2009, 317-322

[17] Finkel R A, Bentley J I. Quad tree: a data structure for retrieval on composite keys. Acta Informatica, 1974, 4(1): 1-9

[18] Saltenisy S, Jensen C S, Leutenegger S T, Lopez M A. Indexing the positions of continuously moving objects. In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. 2000, 331-342

[19] Beckmann N, Kriegel H P, Schneider R, Seeger B. The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. 1990, 322-331

[20] http://idke.ruc.edu.cn/t/taxiGPSinBeijing.html

[21] Brinkhoff T. A framework for generating network-based moving objects. GeoInformatica, 2002, 6(2): 153-180

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg