Liming Zhan
ABSTRACT
The range search on trajectories is fundamental in a wide spectrum of applications such as environment monitoring and location based services. In practice, a large portion of spatio-temporal data in the above applications is generated with low sampling rate and the uncertainty arises between two subsequent observations of a moving object. To make sense of the uncertain trajectory data, it is critical to properly model the uncertainty of the trajectories and develop efficient range search algorithms on the new model. Assuming uncertain trajectories are modeled by the popular Markov Chains, in this paper we investigate the problem of range search on uncertain trajectories. In particular, we propose a general framework for range search on uncertain trajectories following the filtering-and-refinement paradigm where summaries of uncertain trajectories are constructed to facilitate the filtering process. Moreover, statistics based and partition based filtering techniques are developed to enhance the filtering capabilities. Comprehensive experiments demonstrate the effectiveness and efficiency of our new techniques.
- L. Chen, Y. Tang, M. Lv, and G. Chen. Partition-based range query for uncertain trajectories in road networks. GeoInformatica, 19(1):61--84, 2015. Google Scholar
Digital Library
- R. Cheng, D. V. Kalashnikov, and S. Prabhakar. Querying imprecise data in moving object environments. IEEE Trans. Knowl. Data Eng., 16(9):1112--1127, 2004. Google ScholarDigital Library
- N. N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. VLDB J., 16(4):523--544, 2007. Google ScholarDigital Library
- T. Emrich, H.-P. Kriegel, N. Mamoulis, M. Renz, and A. Züfle. Indexing uncertain spatio-temporal data. In CIKM, pages 395--404, 2012. Google ScholarDigital Library
- T. Emrich, H.-P. Kriegel, N. Mamoulis, M. Renz, and A. Züfle. Querying uncertain spatio-temporal data. In ICDE, pages 354--365, 2012. Google ScholarDigital Library
- A. Guttman. R-trees: A dynamic index structure for spatial searching. In SIGMOD Conference, pages 47--57, 1984. Google ScholarDigital Library
- G. Hardy, J. Littlewood, and G. Pólya. Inequalities. Cambridge University Press, 1988.Google Scholar
- H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In VLDB, pages 275--286, 1998. Google ScholarDigital Library
- H. Jeung, H. Lu, S. Sathe, and M. L. Yiu. Managing evolving uncertainty in trajectory databases. IEEE Trans. Knowl. Data Eng., Accppted in 2013.Google Scholar
- S. Karlin and H. Taylor. A First Course in Stochastic Processes. Academic Press, 1975.Google Scholar
- C. Ma, H. Lu, L. Shou, and G. Chen. Ksq: Top-(k) similarity query on uncertain trajectories. IEEE Trans. Knowl. Data Eng., 25(9):2049--2062, 2013. Google ScholarDigital Library
- R. Meester. A Natural Introduction to Probability Theory. 2004.Google Scholar
- J. Niedermayer, A. Züfle, T. Emrich, M. Renz, N. Mamoulis, L. Chen, and H.-P. Kriegel. Probabilistic nearest neighbor queries on uncertain moving object trajectories. PVLDB, 7(3):205--216, 2013. Google ScholarDigital Library
- D. Pfoser and C. S. Jensen. Capturing the uncertainty of moving-object representations. In SSD, pages 111--132, 1999. Google ScholarDigital Library
- Y. Tao, X. Xiao, and R. Cheng. Range search on multidimensional uncertain data. ACM Trans. Database Syst., 32(3):15, 2007. Google ScholarDigital Library
- G. Trajcevski, O. Wolfson, K. Hinrichs, and S. Chamberlain. Managing uncertainty in moving objects databases. ACM Trans. Database Syst., 29(3):463--507, 2004. Google ScholarDigital Library
- X. Xie, M. L. Yiu, R. Cheng, and H. Lu. Scalable evaluation of trajectory queries over imprecise location data. IEEE Trans. Knowl. Data Eng., Accppted in 2013.Google Scholar
- C. Xu, Y. Gu, L. Chen, J. Qiao, and G. Yu. Interval reverse nearest neighbor queries on uncertain data with markov correlations. In ICDE, pages 170--181, 2013. Google ScholarDigital Library
- J. Yuan, Y. Zheng, X. Xie, and G. Sun. Driving with knowledge from the physical world. In KDD, pages 316--324, 2011. Google ScholarDigital Library
- Y. Zhang, X. Lin, W. Zhang, J. Wang, and Q. Lin. Effectively indexing the uncertain space. IEEE Trans. Knowl. Data Eng., 22(9):1247--1261, 2010. Google ScholarDigital Library
- Y. Zhang, W. Zhang, Q. Lin, and X. Lin. Effectively indexing the multi-dimensional uncertain objects for range searching. In EDBT, pages 504--515, 2012. Google ScholarDigital Library
- K. Zheng, G. Trajcevski, X. Zhou, and P. Scheuermann. Probabilistic range queries for uncertain trajectories on road networks. In EDBT, pages 283--294, 2011. Google ScholarDigital Library
- K. Zheng, Y. Zheng, X. Xie, and X. Zhou. Reducing uncertainty of low-sampling-rate trajectories. In ICDE, pages 1144--1155, 2012. Google ScholarDigital Library
Index Terms
- Range Search on Uncertain Trajectories
Recommendations
Probabilistic range queries for uncertain trajectories on road networks
EDBT/ICDT '11: Proceedings of the 14th International Conference on Extending Database TechnologyTrajectories representing the motion of moving objects are typically obtained via location sampling, e.g. using GPS or road-side sensors, at discrete time-instants. In-between consecutive samples, nothing is known about the whereabouts of a given moving ...
Inferring Uncertain Trajectories from Partial Observations
ICDM '14: Proceedings of the 2014 IEEE International Conference on Data MiningThe explosion in the availability of GPS-enabled devices has resulted in an abundance of trajectory data. In reality, however, majority of these trajectories are collected at a low sampling rate and only provide partial observations on their actually ...
Worst-case efficient range search indexing: invited tutorial
PODS '09: Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsIn this tutorial we will describe some of the recent advances in the development of worst-case efficient range search indexing structures, that is, structures for storing a set of data points such that the points in a axis-parallel (hyper-) query ...
Comments