|
|
|
An efficient approach for continuous density queries |
Jie WEN1( ), Xiaofeng MENG1, Xing HAO1, Jianliang XU2 |
| 1. School of Information, Renmin University of China, Beijing 100872, China; 2. Department of Computer Science, Hong Kong Baptist University, Hong Kong, China |
|
|
|
|
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
|
|
Corresponding Author(s):
WEN Jie,Email:wj.shinee@ruc.edu.cn
|
|
Issue Date: 01 October 2012
|
|
| 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
doi: 10.1007/978-3-540-45072-6_18
|
| 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
doi: 10.1145/1140104.1140111
|
| 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
doi: 10.1145/872757.872812
|
| 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
doi: 10.1109/TKDE.2003.1185846
|
| 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
doi: 10.1145/1007568.1007638
|
| 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
doi: 10.1145/1066157.1066212
|
| 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
doi: 10.1016/B978-155860869-6/50033-0
|
| 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
doi: 10.1007/BF00288933
|
| 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
doi: 10.1145/342009.335427
|
| 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
doi: 10.1023/A:1015231126594
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
