Abstract
In the last decade, spatio-temporal database research focuses on the design of effective and efficient indexing structures in support of location-based queries such as predictive range queries and nearest neighbor queries. While a variety of indexing techniques have been proposed to accelerate the processing of updates and queries, not much attention has been paid to the updating protocol, which is another important factor affecting system performance. In this paper, we propose a generic and adaptive updating protocol for moving object databases with less number of updating messages between the objects and database server, thereby reducing the overall workload of the system. In contrast to the approach adopted by most conventional moving object database systems where the exact locations and velocities last disclosed are used to predict their motions, we propose the concept of Spatio-Temporal Safe Region to approximate possible future locations. Spatio-temporal safe regions provide larger space of tolerance for moving objects, freeing them from location and velocity updates as long as the errors remain predictable in the database. To answer predictive queries accurately, the server is allowed to probe the latest status of some moving objects when their safe regions are inadequate in returning the exact query results. Spatio-temporal safe regions are calculated and optimized by the database server with two contradictory objectives: reducing update workload while guaranteeing query accuracy and efficiency. To achieve this, we propose a cost model that estimates the composition of active and passive updates based on historical motion records and query distribution. We have conducted extensive experiments to evaluate our proposal on a variety of popular indexing structures. The results confirm the viability, robustness, accuracy and efficiency of our proposed protocol.
- eCourier. http://api.ecourier.co.uk/.Google Scholar
- R-tree Portal, http://www.rtreeportal.org/.Google Scholar
- T. Brinkhoff. A Framework for Generating Network-Based Moving Objects. GeoInformatica, 6(2):153--180, 2002. Google ScholarDigital Library
- S. Chen, C. S. Jensen, and D. Lin. A benchmark for evaluating moving object indexes. PVLDB, 1(2):1574--1585, 2008. Google ScholarDigital Library
- S. Chen, B. C. Ooi, K.-L. Tan, and M. A. Nascimento. St2 b-tree: a self-tunable spatio-temporal b+ -tree index for moving objects. In SIGMOD, pages 29--42, 2008. Google ScholarDigital Library
- S. Chen, B. C. Ooi, and Z. Zhang. Capturing the motions with adaptive updating model in moving object database. http://www.comp.nus.edu.sg/chensu/stsr-tr.pdf.Google Scholar
- B. Gedik and L. Liu. Mobieyes: Distributed processing of continuously moving queries on moving objects in a mobile system. In EDBT, pages 67--87, 2004.Google ScholarCross Ref
- H. Hu, J. Xu, and D. L. Lee. A generic framework for monitoring continuous spatial queries over moving objects. In SIGMOD, pages 479--490, 2005. Google ScholarDigital Library
- C. S. Jensen, D. Lin, and B. C. Ooi. Query and Update Efficient B+-Tree Based Indexing of Moving Objects. In VLDB, pages 768--779, 2004. Google ScholarDigital Library
- D. Lin, C. S. Jensen, B. C. Ooi, and S. Saltenis. Efficient indexing of the historical, present, and future positions of moving objects. In MDM, pages 59--66, 2005. Google ScholarDigital Library
- 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, 2004. Google ScholarDigital Library
- S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the Positions of Continuously Moving Objects. In SIGMOD, pages 331--342, 2000. Google ScholarDigital Library
- Y. Tao, C. Faloutsos, D. Papadias, and B. Liu. Prediction and indexing of moving objects with unknown motion patterns. In SIGMOD, pages 611--622, 2004. Google ScholarDigital Library
- Y. Tao, D. Papadias, and J. Sun. The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries. In VLDB, pages 790--801, 2003. Google ScholarDigital Library
- Y. Tao, D. Papadias, J. Zhai, and Q. Li. Venn sampling: A novel prediction technique for moving objects. In ICDE, pages 680--691, 2005. Google ScholarDigital Library
- O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7(3):257--387, 1999. Google ScholarDigital Library
- W. Wu, W. Guo, and K.-L. Tan. Distributed processing of moving k-nearest-neighbor query on moving objects. In ICDE, pages 1116--1125, 2007.Google ScholarCross Ref
- X. Xiong, M. F. Mokbel, and W. G. Aref. Sea-cnn: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In ICDE, pages 643--654, 2005. Google ScholarDigital Library
- M. L. Yiu, Y. Tao, and N. Mamoulis. The bdual -tree: indexing moving objects by space filling curves in the dual space. VLDB J., 17(3):379--400, 2008. Google ScholarDigital Library
- X. Yu, K. Q. Pu, and N. Koudas. Monitoring k-nearest neighbor queries over moving objects. In ICDE, pages 631--642, 2005. Google ScholarDigital Library
- M. Zhang, S. Chen, C. S. Jensen, B. C. Ooi, and Z. Zhang. Effectively indexing uncertain moving objects for predictive queries. In VLDB, 2009. Google ScholarDigital Library
- Z. Zhang, R. Cheng, D. Papadias, and A. K. H. Tung. Minimizing communication cost for continous skyline maintenance. In SIGMOD, 2009. Google ScholarDigital Library
- Z. Zhang, Y. Yang, A. K. H. Tung, and D. Papadias. Continuous k-means monitoring over moving objects. IEEE Trans. Knowl. Data Eng., 20(9):1205--1216, 2008. Google ScholarDigital Library
Index Terms
- An adaptive updating protocol for reducing moving object database workload
Recommendations
An adaptive updating protocol for reducing moving object database workload
In the last decade, spatio-temporal database research focuses on the design of effective and efficient indexing structures in support of location-based queries such as predictive range queries and nearest neighbor queries. While a variety of indexing ...
A Kalman filter updating method for the indoor moving object database
A moving object database (MODB), a database representing information on moving objects, has many uses in a wide range of applications, such as the digital battlefield and transportation systems. In the transportation system, an MODB processes queries ...
Approximating Object Location for Moving Object Database
ICDCSW '03: Proceedings of the 23rd International Conference on Distributed Computing SystemsWe consider a moving object database, which keeps track of object locations and supports location-aware queries. Frequent location update to the database can provide high query accuracy but result in heavy consumption on the scarce communication ...
Comments