Yong-Jin Choi
ABSTRACT
A query optimizer requires selectivity estimation of a query to choose the most efficient access plan. An effective method of selectivity estimation for the future locations of moving objects has not yet been proposed. Existing methods for spatial selectivity estimation do not accurately estimate the selectivity of a query to moving objects, because they do not consider the future locations of moving objects, which change continuously as time passes.In this paper, we propose an effective method for spatio-temporal selectivity estimation to solve this problem. We present analytical formulas which accurately calculate the selectivity of a spatio-temporal query as a function of spatio-temporal information. Extensive experimental results show that our proposed method accurately estimates the selectivity over various queries to spatio-temporal data combining real-life spatial data and synthetic temporal data. When Tiger/lines is used as real-life spatial data, the application of an existing method for spatial selectivity estimation to the estimation of the selectivity of a query to moving objects has the average error ratio from 14% to 85%, whereas our method for spatio-temporal selectivity estimation has the average error ratio from 9% to 23%.
- S. Acharya, V. Poosala, and S. Ramaswamy. Selectivity estimation in spatial databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 13-24, 1999. Google Scholar
Digital Library
- P. K. Agarwal, L. Arge, and J. Erickson. Indexing moving points. In Proceedings of the ACM Symposium on Principles of Database Systems, pages 175-186, 2000. Google ScholarDigital Library
- L. Forlizzi, R. H. Guting, E. Nardelli, and M. Schneider. A data model and data structures for moving objects databases. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 319-330, 2000. Google ScholarDigital Library
- P. B. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In Proceedings of the International Conference on Very Large Data Bases, pages 466-475, 1997. Google ScholarDigital Library
- G. Kollios, D. Gunopulos, and V. J. Tsotras. On indexing mobile objects. In Proceedings of the ACM Symposium on Principles of Database Systems, pages 261-272, 1999. Google ScholarDigital Library
- U. S. B. of Census. Tiger/lines precensus files: 1994 technical documentation, technical report, 1994.Google Scholar
- D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches in query processing for moving object trajectories. In Proceedings of the International Conference on Very Large Data Bases, pages 395-406, 2000. Google ScholarDigital Library
- S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the positions of continuously moving objects. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 331-342, 2000. Google ScholarDigital Library
- A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Modeling and querying moving objects. In Proceedings of the IEEE International Conference on Data Engineering, pages 422-432, 1997. Google ScholarDigital Library
- M. Stonebraker, J. Frew, K. Gardels, and J. Meredith. The sequoia 2000 storage benchmark. In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 2-11, 1993. Google ScholarDigital Library
- Y. Tao and D. Papadias. Mv3r-tree: A spatio-temporal access method for timestamp and interval queries. In Proceedings of the International Conference on Very Large Data Bases, pages 431-440, 2001. Google ScholarDigital Library
- O. Wolfson, S. Chamberlain, S. Dao, L. Jiang, and G. Mendez. Cost and imprecision in modeling the position of moving objects. In Proceedings of the IEEE International Conference on Data Engineering, pages 588-596, 1998. Google ScholarDigital Library
Index Terms
- Selectivity estimation for spatio-temporal queries to moving objects
Recommendations
Clustering moving objects for spatio-temporal selectivity estimation
ADC '04: Proceedings of the 15th Australasian database conference - Volume 27Many spatio-temporal applications involve managing and querying moving objects. In such an environment, predictive spatio-temporal queries become an important query class to be processed to capture the nature of moving objects. In this paper, we ...
Efficient evaluation of continuous spatio-temporal queries on moving objects with uncertain velocity
Continuous Range (CR) query and Continuous K-Nearest Neighbor (CKNN) query are two important types of spatio-temporal queries. Given a time interval [t s , t ...
Comments