Article

The 2-3TR-tree, a trajectory-oriented index structure for fully evolving valid-time spatio-temporal datasets

Authors:

Mahdi Abdelguerfi,

Julie Givaudan,

Roy LadnerAuthors Info & Claims

GIS '02: Proceedings of the 10th ACM international symposium on Advances in geographic information systems

Pages 29 - 34

https://doi.org/10.1145/585147.585155

Published: 08 November 2002 Publication History

Abstract

Supporting large volumes of multi-dimensional data is an inherent characteristic of modern database applications, such as Geographical Information Systems (GIS), Computer Aided design (CAD), and Image and Multimedia Databases. Such databases need underlying systems with extended features like query languages, data models, and indexing methods, as compared to traditional databases, mainly because of the complexity of representing and retrieving data. The presented work deals with access methods for databases that accurately model the real world. More precisely, the focus is on index structures that can capture the time varying nature of moving objects, namely spatio-temporal structures. A new taxonomy to classify these structures has been defined according to dataset characteristics and query requirements. Then, a new spatio-temporal access method, the 2-3TR-tree, has been designed to process specific datasets and fulfill specific query requirements that no other existing spatio-temporal index could handle.

References

[1]

Roy Ladner, Kevin Shaw, Mahdi, Abdelguerfi (editors), Mining Spatio-Temporal Information Systems, in print, Kluwer Academic Press, 2002.]]

Digital Library

[2]

Finkel, R.A. and J.L. Bentley, "Quad trees: A Data Structure for Retrieval on Composite Key", Acta Inform, 4:11--9, 1974.]]

[3]

Guttman, a., "R-trees: A Dynamic Index Structure for Spatial Searching", In Proc.ACM SIGMOD International Conference on Management of Data, pp.47--57, 1984.]]

Digital Library

[4]

Sellis, T., N. Roussopoulos, and C. Faloutsos, "The R+-tree: A dynamic index for multidimensional objects", In Proc. 13th Int. Conf. on Very Large Databases, pp.507--518, 1987.]]

Digital Library

[5]

Beckmann, N., H.P. Kriegel, R. Schneider, and B. Seeger, "The R*-tree; An efficient and Robust Access Method for Points and Rectangles", In Proc.ACM SIGMOD Inter. Conference on Management of Data, pp.322--331, 1990.]]

Digital Library

[6]

Kamel, C. Faloutsos, "Hilbert R-tree: An Improved R-tree Using Fractals", Proceedings of the 20th Conference on Very Large Data Bases (VLDB), pp. 500--509, 1994.]]

Digital Library

[7]

Yannis Theodoridis, Timos Sellis, Apostolos N. Papadopoulos, Yannis Manolopoulos, "Specifications for Efficient Indexing in Spatiotemporal Databases", In Statistical and Scientific Database Management, 1998.]]

Digital Library

[8]

T. Tzouramanis, M. Vassilakopoulos, and Y. Manolopoulos, "Overlapping linear quadtrees: A Spatio-Temporal Access Method", In Proc. of the 6th ACM Intl. Work-shop on GIS, pages 1--7, November 1998.]]

Digital Library

[9]

X. Xu, J. Han, and W. Lu, "RT-tree: An improved R-tree index structure for spatiotemporal databases", In Proc. of the 4th Intl. Symposium on Spatial Data Handling, pages 1040--1049, 1990.]]

[10]

Y. Theodoridis, M. Vazirgiannis, and T. Sellis, "Spatio-Temporal Indexing for Large Multimedia Applications. In Proc. of the 3rd IEEE Conf. on Multimedia Computing and Systems, pages 441--448, June 1996.]]

Digital Library

[11]

Nascimento, M.A., Silva, J.R.O and Theodoridis, Y., "Evaluation of Access Structures for Discretely Moving Points". In Proc. of the Intl. Workshop on Spatiotemporal Database Management (STDBM'99), pages 171--188. Edinburgh, UK, Sep/99.]]

Digital Library

[12]

M.A. Nascimento and J.R.O. Silva, "Towards historical R-trees", In Proc. of the 1998 ACM Symposium on Applied Computing, pages 235--240, February 1998.]]

Digital Library

[13]

T. Yufei, D. Papadias, " MV3R-tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries", Technical Report HKUST-CS00-06, 2000.]]

[14]

Pfoser, D., Jensen, C., Theodoridis, Y. "Novel Approaches to the Indexing of Moving Object Trajectories". VLDB, 2000.]]

Digital Library

[15]

Y. Theodoridis, T. Sellis, "A Model for the Prediction of R-Tree Performance," In Proc. Of the ACM Symposium on Principles of Database Systems (PODS)," 1996.]]

Digital Library

[16]

Abdelguerfi, M., Givaudan, J., "Advances in Spatio-Temporal R-tree Based Structures," Technical report TR012-02, Computer Science department, University of New Orleans, 2002.]]

Cited By

Mahmood APunni SAref W(2019)Spatio-temporal access methodsGeoinformatica10.1007/s10707-018-0329-223:1(1-36)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10707-018-0329-2
Ghari Neiat ABouguettaya AGhari Neiat ABouguettaya A(2018)Spatio-Temporal Linear Composition of Sensor Cloud ServicesCrowdsourcing of Sensor Cloud Services10.1007/978-3-319-91536-4_3(25-50)Online publication date: 26-Jun-2018
https://doi.org/10.1007/978-3-319-91536-4_3
Qian HLu Y(2017)Simplifying GPS Trajectory Data with Enhanced Spatial-Temporal ConstraintsISPRS International Journal of Geo-Information10.3390/ijgi61103296:11(329)Online publication date: 30-Oct-2017
https://doi.org/10.3390/ijgi6110329
Show More Cited By

Index Terms

The 2-3TR-tree, a trajectory-oriented index structure for fully evolving valid-time spatio-temporal datasets
1. Information systems
  1. Information retrieval
  2. Information systems applications

Recommendations

Indexing range sum queries in spatio-temporal databases

Although spatio-temporal databases have received considerable attention recently, there has been little work on processing range sum queries on the historical records of moving objects despite their importance. Since the direct access to a huge amount ...
A Prototype Spatio-temporal Database Built on Top of Relational Database
ITNG '15: Proceedings of the 2015 12th International Conference on Information Technology - New Generations

A spatio-temporal database manages both space and time data, whose position or extent may change over time. It is widely used in Transportation Management Systems and Geographic Information Systems to answer queries for objects at a particular position ...
A scalable constraint-based Q-hash indexing for moving objects

In this paper, we develop a Q-hash index structure to efficiently store the position of moving objects. An environment of moving objects contains continuously changing locations which are hard to index using traditional index structures such as R-trees, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '02: Proceedings of the 10th ACM international symposium on Advances in geographic information systems

November 2002

190 pages

ISBN:1581135912

DOI:10.1145/585147

General Chairs:
Kia Makki
Florida International University, USA
,
Niki Pissinou
Florida International University, USA
,
Program Chairs:
Agnòs Voisard
Freie Universität Berlin
,
Shu-Ching Chen
Florida International University, USA

Copyright © 2002 ACM.

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: 08 November 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CIKM02

Sponsor:

CIKM02: Eleventh ACM International Conference on Information and Knowledge Management

November 8 - 9, 2002

Virginia, McLean, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
1,238
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Mahmood APunni SAref W(2019)Spatio-temporal access methodsGeoinformatica10.1007/s10707-018-0329-223:1(1-36)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1007/s10707-018-0329-2
Ghari Neiat ABouguettaya AGhari Neiat ABouguettaya A(2018)Spatio-Temporal Linear Composition of Sensor Cloud ServicesCrowdsourcing of Sensor Cloud Services10.1007/978-3-319-91536-4_3(25-50)Online publication date: 26-Jun-2018
https://doi.org/10.1007/978-3-319-91536-4_3
Qian HLu Y(2017)Simplifying GPS Trajectory Data with Enhanced Spatial-Temporal ConstraintsISPRS International Journal of Geo-Information10.3390/ijgi61103296:11(329)Online publication date: 30-Oct-2017
https://doi.org/10.3390/ijgi6110329
Neiat ABouguettaya ASellis TMistry S(2017)Crowdsourced Coverage as a Service: Two-Level Composition of Sensor Cloud ServicesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2017.267273829:7(1384-1397)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1109/TKDE.2017.2672738
Hengfei Zhang Yong Yan Guang Yang Xiaojun Tan (2013)Multi-Approximation based Time-Parameterized moving objects R-tree2013 15th IEEE International Conference on Communication Technology10.1109/ICCT.2013.6820471(733-737)Online publication date: Nov-2013
https://doi.org/10.1109/ICCT.2013.6820471
Muckell JHwang JPatil VLawson CPing FRavi SLiao L(2011)SQUISHProceedings of the 2nd International Conference on Computing for Geospatial Research & Applications10.1145/1999320.1999333(1-8)Online publication date: 23-May-2011
https://dl.acm.org/doi/10.1145/1999320.1999333
Lu CDai JJin YMathuria J(2009)GLIPIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2008.18321:5(714-728)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1109/TKDE.2008.183
Halaoui H(2009)AIRSTDAdvanced Internet Based Systems and Applications10.1007/978-3-642-01350-8_8(80-90)Online publication date: 24-Apr-2009
https://dl.acm.org/doi/10.1007/978-3-642-01350-8_8
Botea VMallett DNascimento MSander J(2008)PISTGeoinformatica10.1007/s10707-007-0030-312:2(143-168)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1007/s10707-007-0030-3
Feng JZhu YMukai NWatanabe T(2007)Search on transportation networks for location-based serviceApplied Intelligence10.1007/s10489-006-0004-426:1(69-79)Online publication date: 1-Feb-2007
https://dl.acm.org/doi/10.1007/s10489-006-0004-4
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents