Continuous probabilistic nearest-neighbor queries for uncertain trajectories

ABSTRACT

This work addresses the problem of processing continuous nearest neighbor (NN) queries for moving objects trajectories when the exact position of a given object at a particular time instant is not known, but is bounded by an uncertainty region. As has already been observed in the literature, the answers to continuous NN-queries in spatio-temporal settings are time parameterized in the sense that the objects in the answer vary over time. Incorporating uncertainty in the model yields additional attributes that affect the semantics of the answer to this type of queries. In this work, we formalize the impact of uncertainty on the answers to the continuous probabilistic NN-queries, provide a compact structure for their representation and efficient algorithms for constructing that structure. We also identify syntactic constructs for several qualitative variants of continuous probabilistic NN-queries for uncertain trajectories and present efficient algorithms for their processing.

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: Rimantas Benetis , S. Jensen , Gytis Karĉiauskas , Simonas Ŝaltenis, Nearest and reverse nearest neighbor queries for moving objects, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.229-249, September 2006 [doi>10.1007/s00778-005-0166-4]
• 3: Hu Cao , Ouri Wolfson , Goce Trajcevski, Spatio-temporal data reduction with deterministic error bounds, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.211-228, September 2006 [doi>10.1007/s00778-005-0163-7]
• 4: R. Cheng, J. Chen, M. F. Mokbel, and C.-Y. Chow. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In ICDE, 2008.
• 5: 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]
• 6: Mark de Berg , Otfried Cheong , Marc van Kreveld , Mark Overmars, Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA, 2008
• 7: B. V. Gnedenko. Course of Probability Theory. Nauka, 1988.
• 8: R. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005.
• 9: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos, Efficient Indexing of Spatiotemporal Objects, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.251-268, March 25-27, 2002
• 10: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 11: Kathleen Hornsby , Max J. Egenhofer, Modeling Moving Objects over Multiple Granularities, Annals of Mathematics and Artificial Intelligence, v.36 n.1-2, p.177-194, September 2002 [doi>10.1023/A:1015812206586]
• 12: Yuan-Ko Huang , Chao-Chun Chen , Chiang Lee, Continuous K-Nearest Neighbor Query for Moving Objects with Uncertain Velocity, Geoinformatica, v.13 n.1, p.1-25, March 2009 [doi>10.1007/s10707-007-0041-0]
• 13: Glenn S. Iwerks , Hanan Samet , Kenneth P. Smith, Maintenance of K-nn and spatial join queries on continuously moving points, ACM Transactions on Database Systems (TODS), v.31 n.2, p.485-536, June 2006 [doi>10.1145/1138394.1138396]
• 14: Menelaos I. Karavelas, Voronoi Diagrams for Moving Disks and Applications, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.62-74, August 08-10, 2001
• 15: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, Nearest Neighbor Queries in a Mobile Environment, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.119-134, September 10-11, 1999
• 16: J. Lema, L. Forlizzi, R. Güting, E. Nardelli, and M. Schneider. Algorithms for moving objects databases. Computing Journal, 46(6), 2003.
• 17: Jae S. Lim, Two-dimensional signal and image processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 18: Mohamed F. Mokbel , Xiaopeing Xiong , Walid G. Aref, SINA: scalable incremental processing of continuous queries in spatio-temporal databases, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007638]
• 19: Kyriakos Mouratidis , Man Lung Yiu , Dimitris Papadias , Nikos Mamoulis, Continuous nearest neighbor monitoring in road networks, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 20: P. Olofsson. Probability, Statistics and Stochastic Processes. Wiley-Interscience, 2005.
• 21: Jian Pei , Ming Hua , Yufei Tao , Xuemin Lin, Query answering techniques on uncertain and probabilistic data: tutorial summary, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376774]
• 22: Dieter Pfoser , Christian S. Jensen, Capturing the Uncertainty of Moving-Object Representations, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.111-132, July 20-23, 1999
• 23: K. Raptopoulou , A. N. Papadopoulos , Y. Manolopoulos, Fast Nearest-Neighbor Query Processing in Moving-Object Databases, Geoinformatica, v.7 n.2, p.113-137, June 2003 [doi>10.1023/A:1023403908170]
• 24: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 25: H. Royden. Real Analysis. Macmillan Co., 1963.
• 26: Jochen Schiller , Agnès Voisard, Location Based Services, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 27: Cyrus Shahabi , Mohammad R. Kolahdouzan , Mehdi Sharifzadeh, A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases, Geoinformatica, v.7 n.3, p.255-273, September 2003 [doi>10.1023/A:1025153016110]
• 28: Gregory Shakhnarovich , Trevor Darrell , Piotr Indyk, Nearest-Neighbor Methods in Learning and Vision: Theory and Practice (Neural Information Processing), The MIT Press, 2006
• 29: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 30: M. Soliman, I. Ilyas, and K.-C. Chang. Top-k query processing in uncertain databases. In ICDE, 2007.
• 31: Dan Suciu , Nilesh Dalvi, Foundations of probabilistic answers to queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066303]
• 32: Pang-Ning Tan , Michael Steinbach , Vipin Kumar, Introduction to Data Mining, (First Edition), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 33: Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003 [doi>10.1145/777943.777944]
• 34: Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
• 35: Yufei Tao , Xiaokui Xiao , Reynold Cheng, Range search on multidimensional uncertain data, ACM Transactions on Database Systems (TODS), v.32 n.3, p.15-es, August 2007 [doi>10.1145/1272743.1272745]
• 36: G. Trajcevski, R. Tamassia, H. Ding, P. Scheuermann, and I. F. Cruz. Moving convolutions and continuous probabilistic nearest-neighbor queries for uncertain trajectories. Technical Report NWU-EECS-08-12, Northwestern University, Department of EECS, 2008. http://www.eecs.northwestern.edu/docs/techreports/.
• 37: Goce Trajcevski , Ouri Wolfson , Klaus Hinrichs , Sam Chamberlain, Managing uncertainty in moving objects databases, ACM Transactions on Database Systems (TODS), v.29 n.3, p.463-507, September 2004 [doi>10.1145/1016028.1016030]
• 38: Ouri Wolfson , A. Prasad Sistla , Sam Chamberlain , Yelena Yesha, Updating and Querying Databases that Track Mobile Units, Distributed and Parallel Databases, v.7 n.3, p.257-387, July 1999 [doi>10.1023/A:1008782710752]
• 39: Xiaopeng Xiong , Mohamed F. Mokbel , Walid G. Aref, SEA-CNN: Scalable Processing of Continuous K-Nearest Neighbor Queries in Spatio-temporal Databases, Proceedings of the 21st International Conference on Data Engineering, p.643-654, April 05-08, 2005 [doi>10.1109/ICDE.2005.128]
• 40: Xiaohui Yu , Ken Q. Pu , Nick Koudas, Monitoring k-Nearest Neighbor Queries over Moving Objects, Proceedings of the 21st International Conference on Data Engineering, p.631-642, April 05-08, 2005 [doi>10.1109/ICDE.2005.92]