Abstract
This article addresses the problem of managing Moving Objects Databases (MODs) which capture the inherent imprecision of the information about the moving object's location at a given time. We deal systematically with the issues of constructing and representing the trajectories of moving objects and querying the MOD. We propose to model an uncertain trajectory as a three-dimensional (3D) cylindrical body and we introduce a set of novel but natural spatio-temporal operators which capture the uncertainty and are used to express spatio-temporal range queries. We devise and analyze algorithms for processing the operators and demonstrate that the model incorporates the uncertainty in a manner which enables efficient querying, thus striking a balance between the modeling power and computational efficiency. We address some implementation aspects which we experienced in our DOMINO project, as a part of which the operators that we introduce have been implemented. We also report on some experimental observations of a practical relevance.
- Agarwal, A. K., Arge, L., and Erickson, J. 2000. Indexing moving points. In Proceedings of the 19th International ACM Conference on Principles of Database Systems (PODS) Conference. ACM Press, New York, NY, 175--186.]] Google ScholarDigital Library
- Agarwal, P. K. 1990a. Partitioning arrangements of lines: 1. An efficient deterministic algorithm. Discrete Computat. Geom. 5, 449--483.]]Google ScholarDigital Library
- Agarwal, P. K. 1990b. Partitioning arrangements of lines: 2. Applications. Discr. Computat. Geom. 5, 533--573.]]Google ScholarDigital Library
- Agarwal, P. K., Flato, E., and Halperin, D. 2002. Polygon decomposition for efficient construction of minkowski sums. Computat. Geom. 21, 1-2, 39--61.]] Google ScholarDigital Library
- Basch, J. 2004. Personal communication.]]Google Scholar
- Basch, J., Guibas, L. J., and Ramkumar, G. D. 2003. Reporting red-blue intersections between two sets of connected segments. Algorithmica 35, 1, 1--20.]]Google Scholar
- Bentley, J. L. and Ottmann, T. A. 1979. Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28, 9, 643--647.]]Google ScholarDigital Library
- Brundick, F. S. and Hartwig, G. W. 1997. Model-based situational awareness. In Proceedings of the Joint Service Combat Identification Systems Conference (CISC-97).]]Google Scholar
- Cao, H., Wolfson, O., and Trajcevski, G. 2003. Spatio-temporal data reduction with deterministic error bounds. In Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing.]] Google ScholarDigital Library
- Carey, M., Chamberlin, D., Narayanan, S., Vance, B., Doole, D., Rileau, S., Swegarman, R., and Mattos, N. 1999. O-O what have they done to DB2. In Proceedings of the 25th International Conference on Very Large Databases (VLDB). 542--554.]] Google ScholarDigital Library
- Chamberlain, S. 1995. Model-based battle command: A paradigm whose time has come. In Proceedings of the Symposium on C2 Research and Technology, NDU.]]Google Scholar
- Chazelle, B. 1991. Triangulating a simple polygon in linear time. Discr. Computat. Geom. 6, 485--524.]] Google ScholarDigital Library
- Chazelle, B. and Edelsbrunner, H. 1992. An optimal algorithm for intersecting line segments in the plane. J. Assoc. Comput. Mach. 39 1, 1--54.]] Google ScholarDigital Library
- Chen, W., Chow, J., Fuh, Y., grandbois, J., Jou, M., Mattos, N., Tran, B., and Wang, Y. 1999. High level indexing of user-defined types. In Proceedings of the 25th International Conference on Very Large Databases (VLDB). 554--564.]] Google ScholarDigital Library
- Cheng, R., Kalashnikov, D., and Prabhakar, S. 2003. Evaluating probabilistic queries over imprecise data. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM Press, New York, NY, 551--562.]] Google ScholarDigital Library
- Chin, F. Y. L., Snoeyink, J., and Wang, C. A. 1999. Finding the medial axis of a simple polygon in linear time. Discr. Computat. Geom. 21, 3, 405--420.]]Google ScholarCross Ref
- Davis, J. R. 1998. Managing Geo-Spatial Information within the DBMS. IBM DB2 Spatial Extender (IBM White Paper).]]Google Scholar
- Dreyfus, S. E. 1969. An appraisal of some shortest-path algorithms. Operat. Res. 17, 3.]]Google ScholarDigital Library
- Erwig, M., Schneider, M., and Güting, R. H. 1998. Temporal and spatio-temporal datasets and their expressive power. In Proceedings of the Advances in Database Technologies (ER'98, Workshop on Spatio-Temporal Management). Lecture Notes in Computer Science, vol. 1552. Springer-Verlag, Berlin, Germany, 454--465.]] Google ScholarDigital Library
- ESRI. 1996. ArcView GIS:The Geographic Information System for Everyone. Environmental Systems Research Institute Inc., St. Paul, MN.]]Google Scholar
- Forlizzi, L., Güting, R. H., Nardelli, E., and Schneider, M. 2000. A data model and data structures for moving objects databases. In Proceedings of the ACM SIGMOD Internation Conference on Management of Data. ACM Press, New York, NY, 319--330.]] Google ScholarDigital Library
- Gaede, V. and Günther, O. 1998. Multidimensional access methods. ACM Comput. Surv. 11, 4.]] Google ScholarDigital Library
- Genesereth, M. R. and Nilsson, N. J. 1987. Logical Foundations of Artificial Intelligence. Morgan Kaufmann, San Francisco, CA.]] Google ScholarDigital Library
- Güting, R. H., Böhlen, M. H., Erwig, M., Jensen, C., Lorentzos, N., Schneider, M., and Vazirgiannis, M. 2000. A foundation for representing and queirying moving objects. ACM Trans. Database Syst. 25, 1, 1--42.]] Google ScholarDigital Library
- Güting, R. H., Böhlen, M. H., Erwig, M., Jensen, C. S., Lorentzos, N., Schneider, M., and Viqueira, J. R. R. 2003. Spatio-temporal models and languages: An approach based on data types. In Spatio-Temporal Databases: The Chorochronos Approach, M. Koubarakis et al., Eds. Lecture Notes in Computer Science, vol. 2520. Springer-Verlag, Berlin, Germany, 117--177.]]Google Scholar
- Hartwig, G. W., Brundick, F. S., and Kothenbeutel, C. S. 1996. Tactically significant route planning. Tech. Rep. ARL-TR-1139. Army Research Lab, Aberdeen Proving Ground, MJ.]]Google Scholar
- Hightower, J. and Borrielo, G. 2001. Location systems for ubiquitous computing. IEEE Comput. Mag. 34, 8 (Aug.), 57--66.]] Google ScholarDigital Library
- Kedem, K., Livne, R., Pach, J., and Sharir, M. 1986. On the union of Jordan-regions and collision-free translational motion amidst polygonal obstacles. Discr. Computat. Geom. 1, 59--71.]]Google ScholarDigital Library
- Kollios, D., Gunopulos, D., and Tsotras, V. J. 1999a. On indexing mobile objects. In Proceedings of the 18th Internations ACM PODS Conference on Principles of Database Systems. ACM Press, New York, NY, 261--272.]] Google ScholarDigital Library
- Kollios, G., Gunopulos, D., and Tsotras, V. J. 1999b. Nearest neighbour queries in a mobile environment. In Spatio-Temporal Database Management. In Proceedings of the Inernational Workshop STDBM '99. Lecture Notes in Computer Science, vol. 1678. Springer-Verlag, Berlin, Germany, 119--134.]] Google ScholarDigital Library
- Kornacker, M. 1999. High-sperformance extensible indexing. In Proceedings of the 25th International Conference on Very Large Databases (VLDB). 699--708.]] Google ScholarDigital Library
- Mairson, H. G. and Stolfi, J. 1988. Reporting and counting intersections between two sets of line segments. In Theoretical Foundations of Computer Science, NATO ASI., Vol. F40. Kluwer Academic Publishers, Norwell, MA.]]Google Scholar
- O'Rourke, J. 2000. Computational Geometry in C. Cambridge University Press, Cambridge, U.K.]] Google ScholarDigital Library
- Palazzi, L. and Snoeyink, R. 1994. Counting and reporting red/blue segment intersections. Graph. Models Image Process. 56, 4, 304--310.]] Google ScholarDigital Library
- Pasquale, A. D., Forlizzi, L., Jensen, C. S., Manolopoulos, Y., Nardelli, E., Pfoser, D., Proietti, G., Saltenis, S., Theodoridis, Y., and Tzouramanis, T. 2003. Access methods and query processing techniques. In Spatio-Temporal Databases: The Chorochronos Approach, M. Koubarakis et al., Eds. Lecture Notes in Computer Science, vol. 2520. Springer-Verlag, Berlin, Germany, 203--263.]]Google Scholar
- Pfoser, D. and Jensen, C. 1999. Capturing the uncertainty of moving objects representation. In Proceedings of the International Symposium on Advances in Spatial Databases (SSD). 111--132.]] Google ScholarDigital Library
- Pfoser, D., Theodoridis, Y., and Jensen, C. 1999. Indexing trajectories of moving point objects. Tech. rep. 99/07/03. Dept. of Computer Science, University of Aalborg, Aalborg, Denmark.]]Google Scholar
- Pitoura, E. and Samaras, G. 2001. Locating objects in mobile computing. IEEE Trans. Knowl. Data Eng. 13, 4, 571--592.]] Google ScholarDigital Library
- Prabhakar, S., Xia, Y., Kalashnikov, D., Aref, W., and Hambrusch, S. 2002. Query indexing and velocity constrained indexing: Scalable techniques for continuous queries on moving objects. IEEE Trans. Comput. 51, 10, 1124--1140.]] Google ScholarDigital Library
- Saltenis, S. and Jensen, C. 1999. R-tree based indexing of general spatio-temporal data. Tech. rep. TR-45. TimeCenter. Available online at www.cs.auc.dk/TimeCenter/pub.html.]]Google Scholar
- Saltenis, S. and Jensen, C. 2002. Indexing of moving objects for location-based services. In Proceedings of the International Conference on Data Engineering (ICDE). 463--472.]] Google ScholarDigital Library
- Saltenis, S., Jensen, C. S., Leutenegger, S. T., and Lopez, M. A. 2000. Indexing the positions of continuously moving objects. In Proceedings of the ACM SIGMOD International Conference on Management of Data, ACM Press, New York, NY, 331--342.]] Google ScholarDigital Library
- Sharir, M. and Agarwal, P. K. 1995. Davenport-Schinzel Sequences and Their Geometric Applications. Campbridge University Press, Cambridge, U.K.]] Google ScholarDigital Library
- Sistla, A., Wolfson, P., Chamberlain, S., and Dao, S. 1998. Querying the uncertain positions of moving objects. In Temporal Databases: Research and Practice, O. Etzion, S. Jajodia, and S. Sripada, Eds. Lecture Notes in Computer Science, vol. 1399. Springer-Verlag, Berlin, Germany, 310--337.]]Google Scholar
- Sistla, A. P., Wolfson, O., Chamberlain, S., and Dao, S. 1997. Modeling and querying moving objects. In Proceedings of the International Conference on Data Engineering (ICDE). 422--432.]] Google ScholarDigital Library
- Sutherland, W. A. 1978. Introduction to Metric and Topological Spaces. Oxford University Press, Oxford, U.K.]]Google Scholar
- Tansel, A., Clifford, J., Jajodia, S., Segev, A., and Snodgrass, R. 1993. Temporal Databases: Theory and Implementation. Benjamin Cummings Publishing Co., San Francisco, CA.]] Google ScholarDigital Library
- Tayeb, J., Ulusoy, O., and Wolfson, O. 1998. A quadtree-based dynamic attribute indexing method. Comput. J. 41, 3, 185--200.]]Google ScholarCross Ref
- Team, I. D. 1999. Informix datablade technology: Transforming data into smart data. Informix Press, Menlo Park, CA.]]Google Scholar
- Theodoridis, Y., Sellis, T., Papadopoulos, A. N., and Manolopoulos, Y. 1999a. Specifications for efficient indexing in spatiotemporal databases. In Proceedings of the International Conferece on Statistical and Scientific Database Management (SSDBM). IEEE Computer Society Press, Los Alamitos, CA, 123--132.]] Google ScholarDigital Library
- Theodoridis, Y., Silva, J. R. O., and Nascimento, M. A. 1999b. On the generation of spatiotemporal datasets. In Proceedings of the International Symposium on Large Spatial Databases. 147--164.]] Google ScholarDigital Library
- Trajcevski, G., Wolfson, O., Cao, H., Lin, H., Zhang, F., and Rishe, N. 2002a. Managing uncertain trajectories of moving objects with DOMINO. In Proceedings of the International Conference on Enterprise Information Systems (ICEIS). 218--225.]]Google Scholar
- Trajcevski, G., Wolfson, O., Xu, B., and Nelson, P. 2002b. Real-time traffic updates in moving object databases. In Proceedings of the MDDS Workshop, in conjunction with Database and Expert Systems Applications (DEXA)). 698--704.]] Google ScholarDigital Library
- Vazirgiannis, M., Theodoridis, Y., and Sellis, T. 1998. Spatiotemporal composition and indexing for large multimedia applications. Multimed. Syst. J. 6, 4.]] Google ScholarDigital Library
- Vazirgiannis, M. and Wolfson, O. 2001. A spatiotemporal model and language for moving objects on road networks. In Proceedings of the Symposium on Spatial and Temporal Databases (SSTD).]] Google ScholarDigital Library
- Want, R. and Schilit, B. 2001. Expanding the horizons of location aware computing. IEEE Comput. Mag. 34, 8 (Aug.), 31--34.]] Google ScholarDigital Library
- Weibel, R. 1997. Generalization of spatial data: Principles and selected algorithms. In Algorithmic Foundations of Geographic Information Systems, M. J. van Kreveld, J. Nievergelt, T. Roos, and P. Widmayer, Eds. Lecture Notes in Computer Science, vol. 1340. Springer-Verlag, Berlin, Germany, 99--152.]] Google ScholarDigital Library
- Wolfson, O., Cao, H., Lin, H., Trajcevski, G., Zhang, F., and Rishe, N. 2002. Management of dynamic location information in domino. In Proceedings of the International Conference on Extending Database Technology (EDBT).]] Google ScholarDigital Library
- Wolfson, O., Chamberlain, S., Dao, S., Jiang, L., and Mendez, G. 1998. Cost and imprecision in modeling the position of moving objects. In Proceedings of the International Conference on Data Engineering (ICDE). 588--596.]] Google ScholarDigital Library
- Wolfson, O., Sistla, A. P., Chamberlain, S., and Yesha, Y. 1999. Updating and querying databases that track mobile units. Distrib. Parall. Databases 7, 3, 257--387.]] Google ScholarDigital Library
- Wolfson, O. and Yin, H. 2003. Accuracy and resource consumption in tracking and location prediction. In Proceedings of the Symposium on Spatial and Temporal Databases (SSTD), 325--343.]]Google Scholar
Index Terms
- Managing uncertainty in moving objects databases
Recommendations
Probabilistic range queries in moving objects databases with uncertainty
MobiDe '03: Proceedings of the 3rd ACM international workshop on Data engineering for wireless and mobile accessThis work addresses the issue of answering spatio-temporal range queries when there is uncertainty associated with the model of the moving objects. Uncertainty is inherent in Moving Objects Database (MOD) applications and capturing it in the data model ...
Supporting uncertainty in moving objects in network databases
GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systemsThe management of moving objects has been intensively studied in the recent years. A wide and increasing range of database applications has to deal with spatial objects whose position changes continuously over time, called moving objects. Due to the ...
Supporting Uncertainty in Indexing and Querying of Moving Objects in Networks Databases
IFITA '09: Proceedings of the 2009 International Forum on Information Technology and Applications - Volume 01In order to get more accurate movement information of moving objects, and to capture the temporal trajectory of the spatial uncertainty, This article describes the uncertain trajectory model of the moving objects in the road networks databases, and ...
Comments