Processing probabilistic spatio-temporal range queries over moving objects with uncertainty

ABSTRACT

Range queries for querying the current and future positions of the moving objects have received growing interests in the research community. Existing methods, however, assume that an object only moves along an anticipated path. In this paper, we study the problem of answering probabilistic range queries on moving objects based on an uncertainty model, which captures the possible movements of objects with probabilities. Evaluation of probabilistic queries is challenging due to large objects volume and costly computation. We map the uncertain movements of all objects to a dual space for indexing. By querying the index, we quickly eliminate unqualified objects and employ an approximate approach to examine the remaining candidates for final answer. We conduct a comprehensive performance study, which shows our proposal significantly reduces the number of object examinations and the overall cost of the query evaluation.

REFERENCES

• 1: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluating probabilistic queries over imprecise data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872823]
• 2: Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Querying Imprecise Data in Moving Object Environments, IEEE Transactions on Knowledge and Data Engineering, v.16 n.9, p.1112-1127, September 2004 [doi>10.1109/TKDE.2004.46]
• 3: Reynold Cheng , Yuni Xia , Sunil Prabhakar , Rahul Shah , Jeffrey Scott Vitter, Efficient indexing methods for probabilistic threshold queries over uncertain data, Proceedings of the Thirtieth international conference on Very large data bases, p.876-887, August 31-September 03, 2004, Toronto, Canada
• 4: W. Feller. An Introduction to Probability Theory and Its Applications 2nd edn. (Wiley), pp 340--391, 1957.
• 5: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 6: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 7: Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft , Jie-Bing Yu, Processing queries by linear constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.257-267, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263689]
• 8: P. V. C. Hough. Method and Means for Recognizing Complex Patterns, U. S. Patent No. 306964, 1962.
• 9: H. V. Jagadish, On Indexing Line Segments, Proceedings of the 16th International Conference on Very Large Data Bases, p.614-625, August 13-16, 1990
• 10: S. Karlin and H. M. Taylor. A First Course in Stochastic Processes 2nd edn. (Academic Press), pp. 340--391, 1975.
• 11: George Kollios , Dimitris Papadopoulos , Dimitrios Gunopulos , J. Tsotras, Indexing mobile objects using dual transformations, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.2, p.238-256, April 2005 [doi>10.1007/s00778-004-0139-z]
• 12: Zhuyu Lei , Cem U. Saraydar , Narayan B. Mandayam, Paging area optimization based on interval estimation in wireless personal communication networks, Mobile Networks and Applications, v.5 n.1, p.85-99, March 2000 [doi>10.1023/A:1019135923695]
• 13: A. Papoulis. Probability, Random Variables and Stochastic Processes 3rd edn. (McGraw-Hill), 1991.
• 14: H. Packard. Normal and Inverse Normal Distribution for the HP-67. "http://www.hpmuseum.org/software/67pacs/67ndist.htm".
• 15: C. Rose, Minimizing the average cost of paging and registration: a timer-based method, Wireless Networks, v.2 n.2, p.109-116, June 1996 [doi>10.1007/BF01225634]
• 16: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 17: A. Prasad Sistla , Ouri Wolfson , Sam Chamberlain , Son Dao, Modeling and Querying Moving Objects, Proceedings of the Thirteenth International Conference on Data Engineering, p.422-432, April 07-11, 1997
• 18: Yufei Tao , Christos Faloutsos , Dimitris Papadias , Bin Liu, Prediction and indexing of moving objects with unknown motion patterns, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007637]
• 19: Yufei Tao , Dimitris Papadias , Jimeng Sun, The TPR*-tree: an optimized spatio-temporal access method for predictive queries, Proceedings of the 29th international conference on Very large data bases, p.790-801, September 09-12, 2003, Berlin, Germany
• 20: Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway