A spatio-temporal access method based on snapshots and events

ABSTRACT

This paper describes a new spatio-temporal access method (SEST-Index) that combines two approaches for modeling spatio-temporal information: snapshots and events. This method makes it possible to not only process time slice and interval queries, but also queries about events. The SEST Index implementation uses an R-tree structure for storing snapshots and a log data structure for storing events that occur between consecutive snapshots. Experimental results that compare SEST-Index and HR-tree show that, for a change frequency between 1% and 13%, SEST-Index requires less storage space than HR-tree, and for a change frequency between 1% and 7%, SEST-Index outperforms HR-tree for interval queries. In addition, as SEST-Index is an event-oriented structure, event queries are efficiently answered. In order to decrease the storage space for frequencies of change above 20%, this work explores alternatives that optimize the space of the log structure without affecting the efficiency of query answers.

REFERENCES

• 1: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 2: George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos , Alex Delis , Marios Hadjieleftheriou, Indexing Animated Objects Using Spatiotemporal Access Methods, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.758-777, September 2001 [doi>10.1109/69.956099]
• 3: George N. Kollios , Vassilis Tsotras , Alex Delis, Indexing problems in spatiotemporal databases, 2000
• 4: Yannis Manolopoulos , Yannis Theodoridis , Vassilis J. Tsotras, Advanced database indexing, Kluwer Academic Publishers, Norwell, MA, 2000
• 5: Mokbel, M. F., Ghanem, T. M., and Aref, W. G. Spatio-temporal access methods. IEEE Data Engineering Bulletin 26, 2 (2003), 40--49.
• 6: Nascimento, M., Silva, J., and Theodoridis, Y. Access structures for moving points. Tech. Rep. TR--33, TIME CENTER, 1998.
• 7: Mario A. Nascimento , Jefferson R. O. Silva , Yannis Theodoridis, Evaluation of Access Structures for Discretely Moving Points, Proceedings of the International Workshop on Spatio-Temporal Database Management, p.171-188, September 10-11, 1999
• 8: Dieter Pfoser , Nectaria Tryfona, Requirements, definitions, and notations for spatiotemporal application environments, Proceedings of the 6th ACM international symposium on Advances in geographic information systems, p.124-130, November 02-07, 1998, Washington, D.C., United States [doi>10.1145/288692.288715]
• 9: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 10: 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
• 11: 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
• 12: Yannis Theodoridis , Timos K. Sellis , Apostolos Papadopoulos , Yannis Manolopoulos, Specifications for Efficient Indexing in Spatiotemporal Databases, Proceedings of the 10th International Conference on Scientific and Statistical Database Management, p.123-132, July 01-03, 1998 [doi>10.1109/SSDM.1998.688117]
• 13: Yannis Theodoridis , Jefferson R. O. Silva , Mario A. Nascimento, On the Generation of Spatiotemporal Datasets, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.147-164, July 20-23, 1999
• 14: 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
• 15: Theodoros Tzouramanis , Michael Vassilakopoulos , Yannis Manolopoulos, Overlapping linear quadtrees and spatio-temporal query processing, The Computer Journal, v.43 n.4, p.325-343, Dec. 2000 [doi>10.1093/comjnl/43.4.325]
• 16: Worboys, M. Event-oriented approaches to geographic phenomena. International Journal of Geographical Information Science 19, 1(2005), 1--28.
• 17: Xu, X., Han, J., and Lu, W. RT-tree: An improved R-tree index structure for spatio-temporal database. In 4th International Symposium on Spatial Data Handling (1990), pp. 1040--1049.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Performance

Keywords:
r-trees, spatio-temporal access methods, temporal events