skip to main content
10.1145/1097064.1097067acmconferencesArticle/Chapter ViewAbstractPublication PagesgisConference Proceedingsconference-collections
Article

Close pair queries in moving object databases

Published: 04 November 2005 Publication History

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]
N. Beckmann, H.Kriegel, R.Schneider, and B.Seeger. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. In Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 322--331, 1990.]]
[2]
J. L. Bentley and T. Ottmann. Algorithms for Reporting and Counting Geometric Intersections. IEEE Transactions on Computers, 28(9):643--647, 1979.]]
[3]
T. Brinkho, H. Kriegel, and B. Seeger. Efficient Processing of Spatial Joins Using R-Trees. In Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 237--246, 1993.]]
[4]
T. Brinkho, H. Kriegel, and B. Seeger. Parallel Processing of Spatial Joins Using R-trees. In Proceedings of International Conference on Data Engineering (ICDE), pages 258--265, 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]
A. Corral, Y. Manolopoulos, Y. Theodoridis, and M. Vassilakopoulos. Closest Pair Queries in Spatial Databases. In Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 189--200, 2000.]]
[7]
J. Dittrich and B. Seeger. Data Redundancy and Duplicate Detection in Spatial Join Processing. In Proceedings of International Conference on Data Engineering (ICDE), pages 535--546, 2000.]]
[8]
W. Freiseisen and P. Pau. A Generic Plane-Sweep for Intersecting Line Segments. In RISC-Technical Report no 98-18, 1998.]]
[9]
H. Gunadhi and A. Segev. Query Processing Algorithms for Temporal Intersection Joins. In Proceedings of International Conference on Data Engineering (ICDE), pages 336--344, 1991.]]
[10]
R. Güting, M. Bohlen, M. Erwig, C. Jensen, N. Lorentzos, M. Schneider, and M. Vazirgiannis. A Foundation for Representing and Querying Moving Objects. ACM Transactions on Database Systems (TODS), 25(1):1--42, 2000.]]
[11]
M. Hadjieleftheriou, G. Kollios, V. Tsotras, and D. Gunopulos. Efficient Indexing of Spatiotemporal Objects. In Proceedings of International Conference on Extending Database Technology (EDBT), pages 251--268, 2002.]]
[12]
G. R. Hjaltason and H. Samet. Incremental Distance Join Algorithms for Spatial Databases. In Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 237--248, 1998.]]
[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]
G. Kollios, D. Gunopulos, and V. J. Tsotras. On Indexing Mobile Objects. In ACM International Symposium on Principles of Database Systems (PODS), pages 261--272, 1999.]]
[15]
D. Lomet and B. Salzberg. The Performance of A Multiversion Access Method. In Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 353--363, 1990.]]
[16]
David B. Lomet. B-tree page size when caching is considered. SIGMOD Record, 27(3):28--32, 1998.]]
[17]
D. Pfoser, C. Jensen, and Y. Theodoridis. Novel Approaches in Query Processing for Moving Objects. In Proceedings of International Conference on Very Large Data Bases (VLDB), pages 395--406, 2000.]]
[18]
K. Porkaew, I. Lazaridis, and S. Mehrotra. Querying Mobile Objects in Spatio-Temporal Databases. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pages 5--78, 2001.]]
[19]
FAA Report. Minutes of the Research, Engineering and Development Advisory Committee.]]
[20]
S. Saltenis, C. Jensen, S. Leutenegger, and Mario A. Lopez. Indexing the Positions of Continuously Moving Objects. Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 331--342, 2000.]]
[21]
S. Shekhar and Y. Huang. Discovering Spatial Co-location Patterns: A Summary of Results. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pages 236--256, 2001.]]
[22]
J. Su, H. Xu, and O. Ibarra. Moving Objects: Logical Relationships and Queries. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pages 3--19, 2001.]]
[23]
Y. Tao and D. Papadias. Efficient Historical R-trees. In Proceedings of International Conference on Scientic and Statistical Database Management (SSDBM), pages 223--237, 2001.]]
[24]
Y. Tao and D. Papadias. MV3R-Tree: A Spatio-temporal Access Method for Timestamp and Interval Queries. In Proceedings of International Conference on Very Large Data Bases (VLDB), pages 431--440, 2001.]]
[25]
Y. Theodoridis, M. Vazirgiannis, and T. Sellis. Spatio-temporal Indexing for Large Multimedia Applications. In Proceedings of International Conference on Multimedia Computing and Systems (ICMCS), pages 441--448, 1996.]]
[26]
J. van den Bercken, B. Blohsfeld, J.-P. Dittrich, J. Krämer, T. Schäfer, M. Schneider, and B. Seeger. XXL- A Library Arrproach to Supporting Efficient Implementations of Advanced Database Queries. In Proceedings of International Conference on Very Large Data Bases (VLDB), pages 39--48, 2001.]]
[27]
J. van den Bercken and B. Seeger. Query Processing Techniques for Multiversion Access Methods. In Proceedings of International Conference on Very Large Data Bases (VLDB), pages 168--179, 1996.]]
[28]
M. Vazirgiannis and O. Wolfson. A Spatiotemporal Model and Language for Moving Objects on Road Networks. In Proceedings of Symposium on Spatial and Temporal Databases (SSTD), pages 20--35, 2001.]]
[29]
O. Wolfson, L. Jiang, A. P. Sistla, S. Chamberlain, N. Rishe, and M. Deng. Databases for Tracking Mobile Units in Real Time. In Proceedings of International Conference on Database Theory (ICDT), pages 169--186, 1999.]]
[30]
O. Wolfson, A. P. Sistla, B. Xu, J. Zhou, and S. Chamberlain. DOMINO: Databases for Moving Objects tracking. In Proceedings of ACM/SIGMOD Annual Conference on Management of Data (SIGMOD), pages 547--549, 1999.]]
[31]
O. Wolfson, B. Xu, S. Chamberlain, and L. Jiang. Moving Objects Databases: Issues and Solutions. In Proceedings of International Conference on Scientific and Statistical Database Management (SSDBM), pages 111--122, 1998.]]

Cited By

View all
  • (2024)Multi-Entry Generalized Search Trees for Indexing TrajectoriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691320(421-431)Online publication date: 29-Oct-2024
  • (2024)Classic distance join queries using compact data structuresInformation Sciences: an International Journal10.1016/j.ins.2024.120732674:COnline publication date: 18-Jul-2024
  • (2024)Future and Research Perspectives of Spatiotemporal Data Management MethodsSpatiotemporal Data Analytics and Modeling10.1007/978-981-99-9651-3_12(235-245)Online publication date: 16-Apr-2024
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GIS '05: Proceedings of the 13th annual ACM international workshop on Geographic information systems
November 2005
306 pages
ISBN:1595931465
DOI:10.1145/1097064
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 November 2005

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

CIKM05
Sponsor:

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)1
Reflects downloads up to 06 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Multi-Entry Generalized Search Trees for Indexing TrajectoriesProceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems10.1145/3678717.3691320(421-431)Online publication date: 29-Oct-2024
  • (2024)Classic distance join queries using compact data structuresInformation Sciences: an International Journal10.1016/j.ins.2024.120732674:COnline publication date: 18-Jul-2024
  • (2024)Future and Research Perspectives of Spatiotemporal Data Management MethodsSpatiotemporal Data Analytics and Modeling10.1007/978-981-99-9651-3_12(235-245)Online publication date: 16-Apr-2024
  • (2023)Proportionality on Spatial Data with ContextACM Transactions on Database Systems10.1145/358843448:2(1-37)Online publication date: 13-May-2023
  • (2022)Towards big data behavioral analysis: rethinking GPS trajectory mining approaches from geographic, semantic, and quantitative perspectivesArchitectural Intelligence10.1007/s44223-022-00011-y1:1Online publication date: 26-Jul-2022
  • (2021)SCP-Tree: Finding Multiple Nearest Parking Spots With Minimal Group Travel CostIEEE Access10.1109/ACCESS.2021.31312299(158946-158960)Online publication date: 2021
  • (2021)XStar: a software system for handling taxi trajectory big dataComputational Urban Science10.1007/s43762-021-00015-w1:1Online publication date: 28-Jul-2021
  • (2020)Trajectory Outlier Detection on Trajectory Data StreamsIEEE Access10.1109/ACCESS.2020.29745218(34187-34196)Online publication date: 2020
  • (2019)A Natural-language-based Visual Query Approach of Uncertain Human TrajectoriesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.2934671(1-1)Online publication date: 2019
  • (2019)Spatio-temporal access methodsGeoinformatica10.1007/s10707-018-0329-223:1(1-36)Online publication date: 1-Jan-2019
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media