Sequenced spatio-temporal aggregation in road networks

ABSTRACT

Many applications of spatio-temporal databases require support for sequenced spatio-temporal (SST) aggregation, e. g., when analyzing traffic density in a city. Conceptually, an SST aggregation produces one aggregate value for each point in time and space.

This paper is the first to propose a method to efficiently evaluate SST aggregation queries for the COUNT, SUM, and AVG aggregation functions. Based on a discrete time model and a discrete, 1.5 dimensional space model that represents a road network, we generalize the concept of (temporal) constant intervals towards constant rectangles that represent maximal rectangles in the space-time domain over which the aggregation result is constant. We propose a new data structure, termed SST-tree, which extends the Balanced Tree for one-dimensional temporal aggregation towards the support for two-dimensional, spatio-temporal aggregation. The main feature of the Balanced Tree to store constant intervals in a compact way by using two counters is extended towards a compact representation of constant rectangles in the space-time domain. We propose and evaluate two variants of the SST-tree. The SST^T-tree and SST^H-tree use trees and hashmaps to manage spacestamps, respectively. Our experiments show that both solutions outperform a brute force approach in terms of memory and time. The SST^H-tree is more efficient in terms of memory, whereas the SST^T-tree is more efficient in terms of time.

REFERENCES

• 1: R. Bayer. Binary b-trees for virtual memory. In ACM SIGFIDET, pages 219--235, 1971.
• 2: Bruno Becker , Stephan Gschwind , Thomas Ohler , Bernhard Seeger , Peter Widmayer, An asymptotically optimal multiversion B-tree, The VLDB Journal — The International Journal on Very Large Data Bases, v.5 n.4, p.264-275, December 1996 [doi>10.1007/s007780050028]
• 3: M. H. Böhlen, J. Gamper, and C. S. Jensen. Multi-dimensional aggregation for temporal data. In EDBT, pages 257--275, 2006.
• 4: Michael H. Böhlen , Richard Thomas Snodgrass , Michael D. Soo, Coalescing in Temporal Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.180-191, September 03-06, 1996
• 5: Thomas Brinkhoff, A Framework for Generating Network-Based Moving Objects, Geoinformatica, v.6 n.2, p.153-180, June 2002 [doi>10.1023/A:1015231126594]
• 6: 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
• 7: Google. Google's sparsehash project. http://code.google.com/p/google-sparsehash/. Current as of December 12, 2008.
• 8: Hartmut Güting , Teixeira de Almeida , Zhiming Ding, Modeling and querying moving objects in networks, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.165-190, June 2006 [doi>10.1007/s00778-005-0152-x]
• 9: 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
• 10: C. Hage , C. S. Jensen , T. B. Pedersen , L. Speicys , I. Timko, Integrated data management for mobile services in the real world, Proceedings of the 29th international conference on Very large data bases, p.1019-1030, September 09-12, 2003, Berlin, Germany
• 11: Christian S. Jensen , Jan Kolářvr , Torben Bach Pedersen , Igor Timko, Nearest neighbor queries in road networks, Proceedings of the 11th ACM international symposium on Advances in geographic information systems, p.1-8, November 07-08, 2003, New Orleans, Louisiana, USA [doi>10.1145/956676.956677]
• 12: C. S. Jensen, K.-J. Lee, S. Pakalnis, and S. Šaltenis. Advanced tracking of vehicles. In European Congress and Exhibition on ITS, page 12 pages, 2005.
• 13: Nick Kline , Richard Thomas Snodgrass, Computing Temporal Aggregates, Proceedings of the Eleventh International Conference on Data Engineering, p.222-231, March 06-10, 1995
• 14: R. Kothuri, A. Godfrind, and E. Beinat. Pro Oracle Spatial. Apress, 2004.
• 15: J. A. C. Lema, L. Forlizzi, R. H. Güting, E. Nardelli, and M. Schneider. Algorithms for moving objects databases. Comput. J., 46(6):680--712, 2003.
• 16: Ines Fernando Vega Lopez , Richard T. Snodgrass , Bongki Moon, Spatiotemporal Aggregate Computation: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.17 n.2, p.271-286, February 2005 [doi>10.1109/TKDE.2005.34]
• 17: Bongki Moon , Ines Fernando Vega Lopez , Vijaykumar Immanuel, Efficient Algorithms for Large-Scale Temporal Aggregation, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.744-759, March 2003 [doi>10.1109/TKDE.2003.1198403]
• 18: NCHRP. A Generic Data Model for Linear Referencing Systems. Transportation Research Board, Washington, DC, USA, 1997.
• 19: Dimitris Papadias , Panos Kalnis , Jun Zhang , Yufei Tao, Efficient OLAP Operations in Spatial Data Warehouses, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.443-459, July 12-15, 2001
• 20: Indexing Spatio-Temporal Data Warehouses, Proceedings of the 18th International Conference on Data Engineering, p.166, February 26-March 01, 2002
• 21: Richard Thomas Snodgrass, The TSQL2 Temporal Query Language, Kluwer Academic Publishers, Norwell, MA, 1995
• 22: Laurynas Speičys , Christian S. Jensen, Enabling Location-based Services--Multi-Graph Representation of Transportation Networks, Geoinformatica, v.12 n.2, p.219-253, June 2008 [doi>10.1007/s10707-007-0032-1]
• 23: Jimeng Sun , Dimitris Papadias , Yufei Tao , Bin Liu, Querying about the Past, the Present, and the Future in Spatio-Temporal Databases, Proceedings of the 20th International Conference on Data Engineering, p.202, March 30-April 02, 2004
• 24: Yufei Tao , George Kollios , Jeffrey Considine , Feifei Li , Dimitris Papadias, Spatio-Temporal Aggregation Using Sketches, Proceedings of the 20th International Conference on Data Engineering, p.214, March 30-April 02, 2004
• 25: Yufei Tao , Dimitris Papadias , Jun Zhang, Aggregate Processing of Planar Points, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.682-700, March 25-27, 2002
• 26: Ouri Wolfson , Hu Cao , Hai Lin , Goce Trajcevski , Fengli Zhang , Naphtali Rishe, Management of Dynamic Location Information in DOMINO, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.769-771, March 25-27, 2002
• 27: 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
• 28: Jun Yang , Jennifer Widom, Incremental Computation and Maintenance of Temporal Aggregates, Proceedings of the 17th International Conference on Data Engineering, p.51-60, April 02-06, 2001
• 29: Donghui Zhang , Alexander Markowetz , Vassilis J. Tsotras , Dimitrios Gunopulos , Bernhard Seeger, On computing temporal aggregates with range predicates, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-39, June 2008 [doi>10.1145/1366102.1366109]