Supporting uncertainty in moving objects in network databases

ABSTRACT

The 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 continuous and unpredictable nature of the movements, they cannot be precisely stored in a database, and therefore objects' positions are sampled, and between these sampled positions interpolation is used. This sampling/interpolation approach results in uncertainty in the objects' positions in the whole trajectory of the moving objects. In this paper, we try to analyze this problem about uncertainty when the movement is restricted to a network. Examples of such movements are cars in highways and trains in railroads. The uncertainty problem is simpler in such cases compared to the free movement in 2-dimensional space. We describe the geometry of the uncertain trajectories of the objects with movement constrained to networks, an extension to the framework in [18, 16] to support uncertainty, as well as some implementation considerations using Secondo, an extensible database system that supports non-standard applications.

REFERENCES

• 1: 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]
• 2: R. Cheng, S. Prabhakar, and D. Kalashnikov. Querying imprecise data in moving object environments. In Proc. of the IEEE International Conference on Data Engineering (ICDE), pages 723--725, 2003.
• 3: J. A. Cotelo Lema, L. Forlizzi, R. H. Güting, E. Nardelli, and M. Schneider. Algorithms for moving objects databases. The Computer Journal, 46(6):680--712, 2003.
• 4: Victor Teixeira De Almeida , Ralf Hartmut Güting, Indexing the Trajectories of Moving Objects in Networks*, Geoinformatica, v.9 n.1, p.33-60, March 2005 [doi>10.1007/s10707-004-5621-7]
• 5: Stefan Dieker , Ralf Hartmut Güting, Plug and Play with Query Algebras: SECONDO-A Generic DBMS Development Environment, Proceedings of the 2000 International Symposium on Database Engineering & Applications, p.380-392, September 18-20, 2000
• 6: Stefan Dieker , Ralf Hartmut Güting , Miguel Rodríguez Luaces, A Tool for Nesting and Clustering Large Objects, Proceedings of the 12th International Conference on Scientific and Statistical Database Management (SSDBM'00), p.169, July 26-28, 2000 [doi>10.1109/SSDM.2000.869786]
• 7: Managing Moving Objects on Dynamic Transportation Networks, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.287, June 21-23, 2004 [doi>10.1109/SSDBM.2004.48]
• 8: Z. Ding and R. H. Güting. Uncertainty management for network constrained moving objects. In Proc. of the 15th Intl. Workshop on Database and Expert Systems Applications (DEXA), pages 411--421, 2004.
• 9: Martin Erwig , Ralf Hartmut Güting , Markus Schneider , Michalis Vazirgiannis, Spatio-Temporal Data Types: An Approach to Modeling and Querying Moving Objects in Databases, Geoinformatica, v.3 n.3, p.269-296, September 1999 [doi>10.1023/A:1009805532638]
• 10: Martin Erwig , Markus Schneider, Vague Regions, Proceedings of the 5th International Symposium on Advances in Spatial Databases, p.298-320, July 15-18, 1997
• 11: Luca Forlizzi , Ralf Hartmut Güting , Enrico Nardelli , Markus Schneider, A data model and data structures for moving objects databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.319-330, May 15-18, 2000, Dallas, Texas, United States
• 12: E. Frentzos. Indexing objects moving on fixed networks. In Proc. of the 8th Intl. Symp. on Spatial and Temporal Databases (SSTD), pages 289--305, 2003.
• 13: H. Gowrisankar and S. Nittel. Reducing uncertainty in location prediction of moving objects in road networks (extended abstract). In Proc. of the 2nd Intl. Conf. on Geographic Information Science (GIScience), 2002.
• 14: J. S. Greenfeld. Matching GPS observations to locations on a digital map. In Proc. of the 81th Annual Meeting of the Transportation Research Board, 2002.
• 15: Ralf Hartmut Güting, Second-order signature: a tool for specifying data models, query processing, and optimization, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.277-286, May 25-28, 1993, Washington, D.C., United States
• 16: R. H. Güting, V. T. de Almeida, and Z. Ding. Modeling and querying moving objects in networks. VLDB Journal, 2005. To appear. Also available as Technical Report 308, FernuniversitÄat Hagen, Fachbereich Informatik at http://www.informatik.fernuni-hagen.de/import/pi4/papers/PaperMon.pdf.
• 17: R. H. Güting, T. Behr, V. T. de Almeida, Z. Ding, F. Hoffmann, and M. Spiekermann. SECONDO: An extensible DBMS architecture and prototype. Technical Report 313, Fernuniversität Hagen, Fachbereich Informatik, 2004. Available at http://www.informatik.fernuni-hagen.de/import/pi4/papers/Secondo04.pdf.
• 18: Ralf Hartmut Güting , Michael H. Böhlen , Martin Erwig , Christian S. Jensen , Nikos A. Lorentzos , Markus Schneider , Michalis Vazirgiannis, A foundation for representing and querying moving objects, ACM Transactions on Database Systems (TODS), v.25 n.1, p.1-42, March 2000 [doi>10.1145/352958.352963]
• 19: Dieter Pfoser , Christian S. Jensen, Indexing of network constrained moving objects, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.25-32, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956680]
• 20: 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
• 21: M. A. Quddus, W. Y. Ochieng, L. Zhao, and R. B. Noland. A general map matching algorithm for transport telematics applications. GPS Solutions Journal, 7(3):157--167, 2003.
• 22: A. P. Sistla, O. Wolfson, S. Chamberlain, and S. Dao. Querying the uncertain position of moving objects. In Temporal Databases: Research and Practice, volume 1399, pages 310--337. LNCS, 1998.
• 23: Erlend Tøssebro , Mads Nygård, An Advanced Discrete Model for Uncertain Spatial Data, Proceedings of the Third International Conference on Advances in Web-Age Information Management, p.37-51, August 11-13, 2002
• 24: Erlend Tøssebro , Mads Nygård, Uncertainty in Spatiotemporal Databases, Proceedings of the Second International Conference on Advances in Information Systems, p.43-53, October 23-25, 2002
• 25: E. Tøssebro and M. Nygård. A medium complexity discrete model for uncertain spatial data. In Proc. 7th Int. Database Engineering and Applications Symposium (IDEAS), pages 376--384, 2003.
• 26: 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]
• 27: Goce Trajcevski , Ouri Wolfson , Fengli Zhang , Sam Chamberlain, The Geometry of Uncertainty in Moving Objects Databases, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.233-250, March 25-27, 2002
• 28: C. E. White, D. Bernstein, and A. L. Kornhauser. Some map matching algorithms for personal navigation assistants. Transportation Research, Part C(8):91--108, 2000.
• 29: Ouri Wolfson , Sam Chamberlain , Son Dao , Liqin Jiang , Gisela Mendez, Cost and Imprecision in Modeling the Position of Moving Objects, Proceedings of the Fourteenth International Conference on Data Engineering, p.588-596, February 23-27, 1998
• 30: 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]
• 31: A Weight-based Map Matching Method in Moving Objects Databases, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.437, June 21-23, 2004 [doi>10.1109/SSDBM.2004.10]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Design, Languages

Keywords:
moving objects databases, network, uncertainty