Abstract
This article addresses the problem of performing Nearest Neighbor (NN) queries on uncertain trajectories. The answer to an NN query for certain trajectories is time parameterized due to the continuous nature of the motion. As a consequence of uncertainty, there may be several objects that have a non-zero probability of being a nearest neighbor to a given querying object, and the continuous nature further complicates the semantics of the answer. We capture the impact that the uncertainty of the trajectories has on the semantics of the answer to continuous NN queries and we propose a tree structure for representing the answers, along with efficient algorithms to compute them. We also address the issue of performing NN queries when the motion of the objects is restricted to road networks. Finally, we formally define and show how to efficiently execute several variants of continuous NN queries. Our experiments demonstrate that the proposed algorithms yield significant performance improvements when compared with the corresponding naïve approaches.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agarwal, P.K., Arge, L., Erickson, J.: Indexing moving points. In: ACM PODS (2000)
Aggarwal, C.C., Agarwal, D.: On nearest neighbor indexing of nonlinear trajectories. In: ACM PODS (2003)
Aggarwal C.C., Yu P.S.: A survey of uncertain data algorithms and applications. IEEE Trans. Knowl. Data Eng. 21(5), 609–623 (2009)
Benetis R., Jensen C.S., Karciauskas G., Saltenis S.: Nearest and reverse nearest neighbor queries for moving objects. VLDB J. 15(3), 229–249 (2006)
Böhm, C., Ooi, B.C., Plant, C., Yan, Y.: Efficiently processing continuous k-NN queries on data streams. In: ICDE (2007)
Cao, H., Wolfson, O., Trajcevski, G.: Spatio-temporal data reduction with deterministic error bounds. VLDB J. 15(3), (2006)
Cheng, R., Chen, J., Mokbel, M.F., Chow, C.-Y.: Probabilistic verifiers: evaluating constrained nearest-neighbor queries over uncertain data. In: ICDE (2008)
Cheng R., Kalashnikov D.V., Prabhakar S.: Querying imprecise data in moving objects environments. IEEE Trans. Knowl. Data Eng 16(9), 112–1127 (2004)
de Berg M., van Kreveld M., Overmars M., Schwarzkopf O.: Computational geometry: algorithms and applications. Springer, New York (2001)
Demiryurek, U., Pan, B., Kashani, F.B., Shahabi, C.: Towards modeling the traffic data on road networks. In: GIS-IWCTS (2009)
Ding, Z., Güting, R.H.: Managing moving objects on dynamic transportation networks. In: SSDBM (2004)
Gao Y., Li C., Chen G., Chen L., Jiang X., Chen C.: Efficient k-nearest-neighbor search algorithms for historical moving object trajectories. J. Comput. Sci. Technol. 22(2), 232–244 (2007)
Gedik B., Wu K.-L., Yu P.S., Liu L.: Processing moving queries over moving objects using motion-adaptive indexes. IEEE Trans. Knowl. Data Eng. 18(5), 651–668 (2006)
Gnedenko B.V.: Course of Probability Theory. Nauka, Moscow (1988)
Güting R.H., Behr T., Xu J.: Efficient k-nearest neighbor search on moving object trajectories. VLDB J. 19(5), 687–714 (2010)
Güting, R.H., Böhlen, M.H., Erwig, M., Jensen, C.S., Lorentzos, N., Nardelli, E., Schneider, M., Viqueira, J.R.R.: Spatio-temporal models and languages: an approach based on data types. In: Spatio-Temporal Databases—The CHOROCHRONOS Approach (2003)
Güting R.H., Böhlen M.H., Erwig M., Jensen C.S., Lorentzos N.A., Schneider M., Vazirgiannis M.: A foundation for representing and querying moving objects. ACM Trans. Database Syst. 25(1), 1–42 (2000)
Güting R.H., de Almeida V.T., Ding Z.: Modeling and querying moving objects in networks. VLDB J. 15(2), 165–190 (2006)
Güting R.H., Schneider M.: Moving Objects Databases. Morgan Kaufmann, Los Altos (2005)
Hägerstrand T.: What about people in regional science?. Papers Reg. Sci. Assoc. 24, 7–21 (1970)
Hjaltason G.R., Samet H.: Distance browsing in spatial databases. ACM Trans. Database Syst. 24(2), 265–318 (1999)
Hornsby K., Egenhofer M.J.: Modeling moving objects over multiple granularities. Ann. Math. Artif. Intell. 36(1-2), 177–194 (2002)
Huang, Y.-K., Chen, Z.-W., Lee, C.: Continuous k-nearest neighbor query over moving objects in road networks. In: APWeb/WAIM, pp. 27–38 (2009)
Huang Z., Lu H., Ooi B.C., Tung A.K.H.: Continuous skyline queries for moving objects. IEEE Trans. Knowl. Data Eng. 18(12), 1645–1658 (2006)
Iwerks, G.S., Samet, H., Smith, K.P.: Maintenance of K-nn and spatial join queries on continuously moving points. ACM Trans. Database Syst. 31(2), (2006)
Jensen, C.S., Lin, D., Ooi, B.C., Zhang, R.: Effective density queries on continuously moving objects. In: ICDE, p. 71 (2006)
Kollios, G., Gunopulos, D., Tsotras, V.: Nearest neighbor queries in a mobile environment. In: STDM, pp. 119–134 (1999)
Kollios, G., Gunopulos, D., Tsotras, V.: On indexing mobile objects. In: ACM PODS, pp. 261–272 (1999)
Kuijpers, B., Othman, W.: Trajectory databases: data models, uncertainty and complete query languages. J. Comput. Syst. Sci. 76(7), (2010)
Lema, J.A.C., Forlizzi, L., Güting, R.H., Nardelli, E., Schneider, M.: Algorithms for moving objects databases. Comput. J. 46(6), (2003)
Li, G., Li, Y., Shu, L., Fan, P.: C-kNN query processing over moving objects with uncertain speeds in road networks. In: APWeb (2011)
Lim J.S.: Two-Dimensional Signal and Image Processing. Prentice Hall, Englewood Cliffs (1990)
Mamoulis, N., Cao, H., Kollios, G., Hadjieleftheriou, M., Tao, Y., Cheung, D.W.: Mining, indexing, and querying historical spatiotemporal data. In: ACM SIGKDD (2004)
Mokbel, M.F., Aref, W.G.: SOLE: scalable on-line execution of continuous queries on spatio-temporal data streams. VLDB J. 17(5), (2008)
Mouratidis, K., Yiu, M.L., Papadias, D., Mamoulis, N.: Continuous nearest neighbor monitoring in road networks. In: VLDB, pp. 43–54 (2006)
Nanni, M., Kuijpers, B., Körner, C., May, M., Pedreschi, D.: Spatiotemporal data mining. In: Mobility, Data Mining and Privacy (2008)
Pei, J., Hua, M., Tao, Y., Lin, X.: Query answering techniques on uncertain and probabilistic data: tutorial summary. In: ACM SIGMOD (2008)
Pelanis, M., Saltenis, S., Jensen, C.S.: Indexing the past, present, and anticipated future positions of moving objects. ACM Trans. Database Syst. 31(1), (2006)
Pfoser, D., Jensen, C.S.: Capturing the uncertainty of moving objects representation. In: SSD (1999)
Pfoser, D., Tryfona, N., Jensen, C.S.: Indeterminacy and spatiotemporal data: basic definitions and case study. GeoInformatica 9(3), (2005)
Raptopoulou K., Papadopoulos A., Manolopoulos Y.: Fast nearest-neighbor query processing in moving-object databases. GeoInformatica 7(2), 113–137 (2003)
Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: ACM SIGMOD (1995)
Royden H.L.: Real Analysis. Macmillan Co, New York (1963)
Shahabi C., Kolahdouzan M.R., Sharifzadeh M.: A road network embedding technique for k-nearest neighbor search in moving object databases. GeoInformatica 7(3), 255–273 (2003)
Shakhnarovich, G., Darrel, T., Indyk, P. (eds): Nearest-Neighbor Methods in Learning and Vision: Theory and Practice. MIT Press, Cambridge (2006)
Sharir M., Agarwal P.K.: Davenport–Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)
Soliman, M.A., Ilyas, I.F., Chang, K.C.-C.: Top-k query processing in uncertain databases. In: ICDE (2007)
Suciu, D., Dalvi, N.N.: Foundations of probabilistic answers to queries. In: ACM SIGMOD (2005) (tutorial)
Tao Y., Papadias D.: Spatial queries in dynamic environments. ACM Trans. Database Syst. 28(2), 131–139 (2003)
Tao, Y., Papadias, D., Sun, J.: The TPR* -tree: an optimized spatio-temporal access method for predictive queries. In: VLDB, pp. 790–801 (2003)
Tao Y., Xiao X., Cheng R.: Range search on multidimensional uncertain data. ACM Trans. Database Syst. 32(3), 15 (2007)
Theodoridis, Y., Sellis, T., Papadopoulos, A., Manolopoulos, Y.: Specifications for efficient indexing in spatiotemporal databases. In: SSDBM (1998)
Trajcevski, G., Tamassia, R., Cruz, I.F., Scheuermann, P., Hartglass, D., Zamierowski, C.: Ranking continuous nearest neighbors for uncertain trajectories: full and Peer Reviewed Accepted Version. Technical Report NWU-EECS-11-06, Dept. of EECS, Northwestern University (2011)
Trajcevski, G., Tamassia, R., Ding, H., Scheuermann, P., Cruz, I.F.: Continuous probabilistic nearest-neighbor queries for uncertain trajectories. In: EDBT (2009)
Trajcevski G., Wolfson O., Hinrichs K., Chamberlain S.: Managing uncertainty in moving objects databases. ACM Trans. Database Syst. 29(3), 463–507 (2004)
Trivedi K.S.: Probability and Statistics with Reliability, Queueing and Computer Science Applications. Wiley, London (2002)
Ullman J.D.: Principles of Database and Knwoledge—Base Systems. Computer Science Press, Rockville (1989)
Wolfson O., Sistla A.P., Chamberlain S., Yesha Y.: Updating and querying databases that track mobile units. Distr Parallel Databases 7(3), 257–387 (1999)
Xia, T., Zhang, D.: Continuous reverse nearest neighbor monitoring. In: ICDE (2006)
Yiu M.L., Mamoulis N., Papadias D.: Aggregate nearest neighbor queries in road networks. IEEE Trans. Knowl. Data Eng. 17(6), 820–833 (2005)
Yu, X., Pu, K.Q., Koudas, N.: Monitoring k-nearest neighbor queries over moving objects. In: ICDE, pp. 631–642 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by NSF awards CCF-0830149, CNS-0910952, IIS-0513553, and IIS-0812258, and by the Center for Geometric Computing at Brown University.
Rights and permissions
About this article
Cite this article
Trajcevski, G., Tamassia, R., Cruz, I.F. et al. Ranking continuous nearest neighbors for uncertain trajectories. The VLDB Journal 20, 767–791 (2011). https://doi.org/10.1007/s00778-011-0249-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00778-011-0249-3