A Markov chain based pruning method for predictive range queries

ABSTRACT

Predictive range queries retrieve objects in a certain spatial region at a (future) prediction time. Processing predictive range queries on large moving object databases is expensive. Thus effective pruning is important, especially for long-term predictive queries since accurately predicting long-term future behaviors of moving objects is challenging and expensive. In this work, we propose a pruning method that effectively reduces the candidate set for predictive range queries based on (high-order) Markov chain models learned from historical trajectories. The key to our method is to devise compressed representations for sparse multi-dimensional matrices, and leverage efficient algorithms for matrix computations. Experimental evaluations show that our approach significantly outperforms other pruning methods in terms of efficiency and precision.

References

1. N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The r*-tree: An efficient and robust access method for points and rectangles. In SIGMOD, 1990.
2. T. Emrich, H. Kriegel, N. Mamoulis, M. Renz, and A. Züfle. Querying uncertain spatio-temporal data. In ICDE, 2012.
3. J. Froehlich and J. Krumm. Route prediction from trip observations. Technical report, SAE Technical Paper, 2008.
4. A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD, 1984.
5. A. M. Hendawi and M. F. Mokbel. Predictive spatio-temporal queries: a comprehensive survey and future directions. In SIGSPATIAL, 2012.
6. E.-J. Im and K. A. Yelick. Optimizing the performance of sparse matrix-vector multiplication. University of California, Berkeley, 2000.
7. C. S. Jensen, D. Lin, and B. C. Ooi. Query and update efficient b+-tree based indexing of moving objects. In VLDB, 2004.
8. J. Krumm. Real time destination prediction based on efficient routes. Technical report, SAE Technical Paper, 2006.
9. S. P. Meyn and R. L. Tweedie. Markov chains and stochastic stability. Springer Science & Business Media, 2012.
10. A. Monreale, F. Pinelli, R. Trasarti, and F. Giannotti. Wherenext: a location predictor on trajectory pattern mining. In SIGKDD, 2009.
11. M. Morzy. Mining frequent trajectories of moving objects for location prediction. In MLDM, 2007.
12. T. E. Oliphant. Python for scientific computing. Computing in Science & Engineering, 9(3), 2007.
13. S. Ray, R. Blanco, and A. K. Goel. Supporting location-based services in a main-memory database. In MDM, 2014.
14. Y. Saad. Sparskit: a basic tool kit for sparse matrix computations, 1994.
15. A. Sadilek and J. Krumm. Far out: Predicting long-term human mobility. In AAAI, 2012.
16. S. Saltenis, C. S. Jensen, S. T. Leutenegger, and M. A. Lopez. Indexing the positions of continuously moving objects. In SIGMOD, 2000.
17. D. Sidlauskas, S. Saltenis, C. W. Christiansen, J. M. Johansen, and D. Saulys. Trees or grids?: indexing moving objects in main memory. In SIGSPATIAL, 2009.
18. D. Sidlauskas, S. Saltenis, and C. S. Jensen. Parallel main-memory indexing for moving-object query and update workloads. In SIGMOD, 2012.
19. Y. Tao, C. Faloutsos, D. Papadias, and B. Liu. Prediction and indexing of moving objects with unknown motion patterns. In SIGMOD, 2004.
20. Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: An optimized spatio-temporal access method for predictive queries. In VLDB, 2003.
21. X. Xu, L. Xiong, and V. S. Sunderam. D-grid: An in-memory dual space grid index for moving object databases. In MDM, pages 252--261, 2016.
22. X. Xu, L. Xiong, V. S. Sunderam, J. Liu, and J. Luo. Speed partitioning for indexing moving objects. In SSTD, 2015.
23. A. Y. Xue, R. Zhang, Y. Zheng, X. Xie, J. Huang, and Z. Xu. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In ICDE, 2013.
24. G. Yavas, D. Katsaros, Ö. Ulusoy, and Y. Manolopoulos. A data mining approach for location prediction in mobile environments. Data Knowl. Eng., 54(2), 2005.
25. J. J. Ying, W. Lee, T. Weng, and V. S. Tseng. Semantic trajectory mining for location prediction. In SIGSPATIAL, 2011.
26. J. Zhou, A. K. H. Tung, W. Wu, and W. S. Ng. A "semi-lazy" approach to probabilistic path prediction. In SIGKDD, 2013.