A Dynamic Interval Based Circular Safe Region Algorithm for Continuous Queries on Moving Objects

Shengsheng Wang, Chen Zhang

College of Computer Science and Technology, Jilin University, Changchun, China.
Department of Computer Information Systems, Bryant University, Smithfield, RI, USA.

DOI: 10.4236/ijcns.2011.45036                

Abstract

Moving object database (MOD) engine is the foundation of Location-Based Service (LBS) information systems. Continuous queries are important in spatial-temporal reasoning of a MOD. The communication costs were the bottleneck for improving query efficiency until the rectangular safe region algorithm partly solved this problem. However, this algorithm can be further improved, as we demonstrate with the dynamic interval based continuous queries algorithm on moving objects. Two components, circular safe region and dynamic intervals were adopted by our algorithm. Theoretical proof and experimental results show that our algorithm substantially outperforms the traditional periodic monitoring and the rectangular safe region algorithm in terms of monitoring accuracy, reducing communication costs and server CPU time. Moreover, in our algorithm, the mobile terminals do not need to have any computational ability.

Keywords

Location Based Service, Moving Object Database, Continuous Spatial Query

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	S. Ilarri, E. Mena and A. Illarramendi, “Location-Dependent Query Processing: Where We Are and Where We Are Heading,” ACM Computing Surveys, Vol. 42, No. 3, 2010, pp. 1-79. doi:10.1145/1670679.1670682
[2]	H. D. Chon, D. Agrawal and A. El Abbadi, “Storage and Retrieval of Moving Objects,” Proceedings of the 2nd International Conference on Mobile Data Management, Hong Kong, 8-10 January 2001, pp. 173-184.
[3]	H. D. Chon, D. Agrawal and A. El Abbadi, “FATES: Finding a Time Dependent Shortest Path,” Proceedings of the 4th International Conference on Mobile Data Ma- nagement, Melbourne, 21-24 January 2003, pp. 165-180.
[4]	Y. Chen, F. Rao, X. Yu and D. Liu, “CAMEL: A Moving Object Database Approach for Intelligent Location Aware Services,” Lecture Notes in Computer Science, Vol. 2574, 2003, pp. 331-334. doi:10.1007/3-540-36389-0_23
[5]	C. S. Jensen, D. Lin and B. C. Ooi, “Query and Update Efficient B+-Tree Based Indexing of Moving Objects,” Proceedings of the 30th International Conference on Very Large Data Bases, Toronto, 29 August - 3 September 2004, pp. 768-779.
[6]	M. F. Mokbel, X. Xiong and W. G. Aref, “SINA: Scalable Incremental Processing of Continuous Queries in Spatio-Temporal Databases,” Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, 13-18 June 2004.
[7]	S. Prabhakar, Y. Xia, D. V. Kalashnikov, W. G. Aref and S. E. Hambrusch, “Query Indexing and Velocity Cons- trained Indexing: Scalable Techniques for Continuous Queries on Moving Objects,” IEEE Transactions on Computers, Vol. 51, No. 10, 2002, pp. 1124-1140. doi:10.1109/TC.2002.1039840
[8]	Y. Tao, D. Papadias and Q. Shen, “Continuous Nearest Neighbor Search,” 28th International Conference on Very Large Data Bases, Hong Kong, 20-23 August 2002. doi:10.1016/B978-155860869-6/50033-0
[9]	X. Yu, K. Q. Pu and N. Koudas, “Monitoring K-Nearest Neighbor Queries over Moving Objects,” 21st International Conference on Data Engineering, Tokyo, 5-8 April 2005, pp. 631-642
[10]	H. Hu, J. Xu and D.L. Lee, “A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects,” Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, Baltimore, 13-16 June 2005. doi:10.1145/1066157.1066212
[11]	D. A. Randell, A.G. Cohn and Z. Cui, “Computing Transitivity Tables: A Challenge for Automated Theorem Provers,” Lecture Notes in Computer Science, Vol. 607, 1992, pp. 786-790.