Close pair queries in moving object databases

ABSTRACT

Databases of moving objects are important for air traffic control, ground traffic, and battlefield configurations. We introduce the (historical and spatial) range close-pair query for moving objects as an important problem for such databases. The purpose of a range close-pair query for moving objects is to find pairs of objects that were closer than ε during time interval $I$ and within spatial range R, where ε, I and R are user-specified parameters.This paper solves the range close-pair query using two components: the retrieval component and the close-pair identification component. The retrieval component breaks up long trajectories into trajectory segments, which are produced in increasing time order, without the need for sorting. The retrieval component takes advantage of a new index mechanism, the Multiple TSB-tree. The segments are then pipelined to the close-pair identification component. The identification component introduces a novel spatial sweep that sweeps by time and one spatial dimension at the same time. Extensive experimental results are provided, demonstrating the advantages of the new approach when considering close pairs.

REFERENCES

• 1: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 2: J. L. Bentley and T. Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Transactions on Computers, 28(9):643--647, 1979.
• 3: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 4: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Parallel Processing of Spatial Joins Using R-trees, Proceedings of the Twelfth International Conference on Data Engineering, p.258-265, February 26-March 01, 1996
• 5: V. Chakka, A. Everspaugh, and J. M. Patel. Indexing Large Trajectory Data Sets with SETI. In Conference on Innovative Data Systems Research, 2003.
• 6: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 7: Data Redundancy and Duplicate Detection in Spatial Join Processing, Proceedings of the 16th International Conference on Data Engineering, p.535, February 28-March 03, 2000
• 8: W. Freiseisen and P. Pau. A Generic Plane-Sweep for Intersecting Line Segments. In RISC-Technical Report no 98-18, 1998.
• 9: Himawan Gunadhi , Arie Segev, Query Processing Algorithms for Temporal Intersection Joins, Proceedings of the Seventh International Conference on Data Engineering, p.336-344, April 08-12, 1991
• 10: 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]
• 11: 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
• 12: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 13: D. Zhang J. Shan and B. Salzberg. On Spatial-Range Closest-Pair Query. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pages 252--269, 2003.
• 14: George Kollios , Dimitrios Gunopulos , Vassilis J. Tsotras, On indexing mobile objects, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.261-272, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304002]
• 15: David Lomet , Betty Salzberg, The performance of a multiversion access method, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.353-363, May 23-26, 1990, Atlantic City, New Jersey, United States
• 16: David Lomet, B-tree page size when caching is considered, ACM SIGMOD Record, v.27 n.3, p.28-32, Sept. 1, 1998 [doi>10.1145/290593.290598]
• 17: Dieter Pfoser , Christian S. Jensen , Yannis Theodoridis, Novel Approaches in Query Processing for Moving Object Trajectories, Proceedings of the 26th International Conference on Very Large Data Bases, p.395-406, September 10-14, 2000
• 18: Kriengkrai Porkaew , Iosif Lazaridis , Sharad Mehrotra, Querying Mobile Objects in Spatio-Temporal Databases, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.59-78, July 12-15, 2001
• 19: FAA Report. Minutes of the Research, Engineering and Development Advisory Committee.
• 20: Simonas Šaltenis , Christian S. Jensen , Scott T. Leutenegger , Mario A. Lopez, Indexing the positions of continuously moving objects, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.331-342, May 15-18, 2000, Dallas, Texas, United States
• 21: Shashi Shekhar , Yan Huang, Discovering Spatial Co-location Patterns: A Summary of Results, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.236-256, July 12-15, 2001
• 22: Jianwen Su , Haiyan Xu , Oscar H. Ibarra, Moving Objects: Logical Relationships and Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.3-19, July 12-15, 2001
• 23: Yufei Tao , Dimitris Papadias, Efficient Historical R-trees, Proceedings of the 13th International Conference on Scientific and Statistical Database Management, p.223-232, July 18-20, 2001
• 24: Yufei Tao , Dimitris Papadias, MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.431-440, September 11-14, 2001
• 25: Spatio-Temporal Indexing for Large Multimedia Applications, Proceedings of the 1996 International Conference on Multimedia Computing and Systems (ICMCS '96), p.0441, June 17-23, 1996
• 26: Jochen Van den Bercken , Björn Blohsfeld , Jens-Peter Dittrich , Jürgen Krämer , Tobias Schäfer , Martin Schneider , Bernhard Seeger, XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries, Proceedings of the 27th International Conference on Very Large Data Bases, p.39-48, September 11-14, 2001
• 27: Jochen Van den Bercken , Bernhard Seeger, Query Processing Techniques for Multiversion Access Methods, Proceedings of the 22th International Conference on Very Large Data Bases, p.168-179, September 03-06, 1996
• 28: Michalis Vazirgiannis , Ouri Wolfson, A Spatiotemporal Model and Language for Moving Objects on Road Networks, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.20-35, July 12-15, 2001
• 29: Ouri Wolfson , Liqin Jiang , A. Prasad Sistla , Sam Chamberlain , Naphtali Rishe , Minglin Deng, Databases for Tracking Mobile Units in Real Time, Proceeding of the 7th International Conference on Database Theory, p.169-186, January 10-12, 1999
• 30: Ouri Wolfson , Prasad Sistla , Bo Xu , Jutai Zhou , Sam Chamberlain, DOMINO: databases fOr MovINg Objects tracking, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.547-549, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 31: Ouri Wolfson , Bo Xu , Sam Chamberlain , Liqin Jiang, Moving Objects Databases: Issues and Solutions, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.111-122, July 01-03, 1998 [doi>10.1109/SSDM.1998.688116]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

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

General Terms:
Algorithms, Experimentation, Performance