Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front Comput Sci    2012, Vol. 6 Issue (5) : 581-595    https://doi.org/10.1007/s11704-012-1120-4
RESEARCH ARTICLE
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
 Download: PDF(726 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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
 Cite this article:   
Jie WEN,Xiaofeng MENG,Xing HAO, et al. An efficient approach for continuous density queries[J]. Front Comput Sci, 2012, 6(5): 581-595.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-012-1120-4
https://academic.hep.com.cn/fcs/EN/Y2012/V6/I5/581
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