Goce Trajcevski
Roberto Tamassia
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.
- F. Aurenhammer. Voronoi diagrams---a survey of a fundamental geometric data structure. ACM Comput. Surv., 23(3), 1991. Google Scholar
Digital Library
- R. Benetis, C. Jensen, G. Karciauskas, and S. Saltenis. Nearest and reverse nearest neighbor queries for moving objects. VLDB Journal, 15(3):229--249, 2006. Google ScholarDigital Library
- H. Cao, O. Wolfson, and G. Trajcevski. Spatio-temporal data reduction with deterministic error bounds. VLDB Journal, 15(3), 2006. Google ScholarDigital Library
- R. Cheng, J. Chen, M. F. Mokbel, and C.-Y. Chow. Probabilistic verifiers: Evaluating constrained nearest-neighbor queries over uncertain data. In ICDE, 2008. Google ScholarDigital Library
- R. Cheng, D. Kalashnikov, and S. Prabhakar. Querying imprecise data in moving objects environments. IEEE Transactions on Knowledge and Data Engineering, 16(9), 2003. Google ScholarDigital Library
- M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, 2001. Google ScholarDigital Library
- B. V. Gnedenko. Course of Probability Theory. Nauka, 1988.Google Scholar
- R. Güting and M. Schneider. Moving Objects Databases. Morgan Kaufmann, 2005.Google Scholar
- M. Hadjieleftheriou, G. Kollios, V. J. Tsotras, and D. Gunopulos. Efficient indexing of spatiotemporal objects. In EDBT, 2002. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Distance browsing in spatial databases. ACM Transactions on Database Systems, 24(2):265--318, 1999. Google ScholarDigital Library
- K. Hornsby and M. Egenhofer. Modeling moving objects over multiple granularities. Ann. Math. Artif. Intell., 36(1--2):177--194, 2002. Google ScholarDigital Library
- Y.-K. Huang, C.-C. Chen, and C. Lee. Continuous k-nearest neighbor query for moving objects with uncertain velocity. GeoInformatica, 2007. DOI 10.1007/s10707-007-0041-0. Google ScholarDigital Library
- G. Iwerks, H. Samet, and K. Smith. Maintenance of K-nn and spatial join queries on continuously moving points. ACM Transactions on Database Systems, 31(2), 2006. Google ScholarDigital Library
- M. Karavelas. Voronoi diagrams for moving disks and applications. In WADS, pages 62--74, 2001. Google ScholarDigital Library
- G. Kollios, D. Gunopulos, and V. Tsotras. Nearest neighbor queries in a mobile environment. In Spatio-Temporal Database Management, pages 119--134, 1999. Google ScholarCross Ref
- J. Lema, L. Forlizzi, R. Güting, E. Nardelli, and M. Schneider. Algorithms for moving objects databases. Computing Journal, 46(6), 2003.Google Scholar
- J. S. Lim. Two-Dimensional Signal and Image Processing. Prentice Hall, 1990. Google ScholarDigital Library
- M. Mokbel, X. Xiong, and W. Aref. SINA: Scalable incremental processing of continuous queries in spatio-temporal databases. In ACM SIGMOD, 2004. Google ScholarDigital Library
- K. Mouratidis, M. Yiu, D. Papadias, and N. Mamoulis. Continuous nearest neighbor monitoring in road networks. In VLDB, pages 43--54, 2006. Google ScholarDigital Library
- P. Olofsson. Probability, Statistics and Stochastic Processes. Wiley-Interscience, 2005.Google Scholar
- J. Pei, M. Hua, Y. Tao, and X. Lin. Query answering techniques on uncertain and probabilistic data: tutorial summary. In ACM SIGMOD, 2008. Google ScholarDigital Library
- D. Pfoser and C. Jensen. Capturing the uncertainty of moving objects representation. In SSD, 1999. Google ScholarDigital Library
- K. Raptopoulou, A. Papadopoulos, and Y. Manolopoulos. Fast nearest-neighbor query processing in moving-object databases. GeoInformatica, 7(2):113--137, 2003. Google ScholarDigital Library
- N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In ACM SIGMOD, pages 71--79, 1995. Google ScholarDigital Library
- H. Royden. Real Analysis. Macmillan Co., 1963.Google Scholar
- J. Schiller and A. Voisard. Location-based Services. Morgan Kaufmann Publishers, 2004. Google ScholarDigital Library
- C. Shahabi, M. Kolahdouzan, and M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. GeoInformatica, 7(3):255--273, 2003. Google ScholarDigital Library
- G. Shakharovich, T. Darrel, and P. Indyk, editors. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice. MIT Press, 2006. Google ScholarDigital Library
- M. Sharir and P. K. Agarwal. Davenport-Schinzel Sequences and Their Geometric Applications. Cambridge University Press, 1995. Google ScholarDigital Library
- M. Soliman, I. Ilyas, and K.-C. Chang. Top-k query processing in uncertain databases. In ICDE, 2007.Google ScholarCross Ref
- D. Suciu and N. Dalvi. Foundations of probabilistic answers to queries. In ACM SIGMOD, 2005. Tutorial. Google ScholarDigital Library
- P.-N. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-Wesley, 2005. Google ScholarDigital Library
- Y. Tao and D. Papadias. Spatial queries in dynamic environments. ACM Transactions on Database Systems, 28(2), 2003. Google ScholarDigital Library
- Y. Tao, D. Papadias, and Q. Shen. Continuous nearest neighbor search. In VLDB, 2002. Google ScholarDigital Library
- Y. Tao, X. Xiao, and R. Cheng. Range search on multidimensional uncertain data. ACM Transactions on Database Systems, 32(3), 2007. Google ScholarDigital Library
- 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/.Google Scholar
- G. Trajcevski, O. Wolfson, K. Hinrichs, and S. Chamberlain. Managing uncertainty in moving objects databases. ACM Transactions on Database Systems, 29(3), 2004. Google ScholarDigital Library
- O. Wolfson, A. P. Sistla, S. Chamberlain, and Y. Yesha. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7, 1999. Google ScholarDigital Library
- X. Xiong, M. Mokbel, and W. Aref. SEA-CNN: Scalable processing of continuous k-nearest neighbor queries in spatio-temporal databases. In ICDE, pages 643--654, 2005. Google ScholarDigital Library
- X. Yu, K. Pu, and N. Koudas. Monitoring k-nearest neighbor queries over moving objects. In ICDE, pages 631--642, 2005. Google ScholarDigital Library
Recommendations
Probabilistic Group Nearest Neighbor Queries in Uncertain Databases
The importance of query processing over uncertain data has recently arisen due to its wide usage in many real-world applications. In the context of uncertain databases, previous work have studied many query types such as nearest neighbor query, range ...
Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data
Uncertain data are inherent in various important applications and reverse nearest neighbor (RNN) query is an important query type for many applications. While many different types of queries have been studied on uncertain data, there is no previous work ...
Probabilistic nearest neighbor queries on uncertain moving object trajectories
Nearest neighbor (NN) queries in trajectory databases have received significant attention in the past, due to their applications in spatio-temporal data analysis. More recent work has considered the realistic case where the trajectories are uncertain; ...
Comments