Frequent spatio-temporal patterns in trajectory data warehouses

ABSTRACT

In this paper we present an approach for storing and aggregating spatio-temporal patterns by using a Trajectory Data Warehouse (TDW). In particular, our aim is to allow the analysts to quickly evaluate frequent patterns mined from trajectories of moving objects occurring in a specific spatial zone and during a given temporal interval.

We resort to a TDW, based on a data cube model, having spatial and temporal dimensions, discretized according to a hierarchy of regular grids, and whose facts are sets of trajectories which intersect the spatio-temporal cells of the cube. The idea is to enrich such a TDW with a new measure: frequent patterns obtained from a data-mining process on trajectories. As a consequence these patterns can be analysed by the user at various levels of granularity by means of OLAP queries.

The research issues discussed in this paper are (1) the extraction/mining of the patterns to be stored in each cell, which requires an adequate projection phase of trajectories before mining; (2) the spatio-temporal aggregation of patterns to answer roll-up queries, which poses many problems due to the holistic nature of the aggregation function.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 2: 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]
• 3: C. Giannella, J. Han, J. Peri, X. Yan, and P. Yu. Mining frequent patterns in data streams at multiple time granularities. In NSF Workshop on Next Generation Data Mining, 2003.
• 4: Fosca Giannotti , Mirco Nanni , Fabio Pinelli , Dino Pedreschi, Trajectory pattern mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281230]
• 5: Hector Gonzalez , Jiawei Han , Xiaolei Li , Diego Klabjan, Warehousing and Analyzing Massive RFID Data Sets, Proceedings of the 22nd International Conference on Data Engineering, p.83, April 03-07, 2006 [doi>10.1109/ICDE.2006.171]
• 6: H. Kargupta and K. Sivakumar. Existential Pleasures of Distributed Data Mining. In Data Mining: Next Generation Challenges and Future Directions. AAAI/MIT Press, 2004.
• 7: C. Lucchese, S. Orlando, P. Palmerini, R. Perego, and F. Silvestri. kDCI: a Multi-Strategy Algorithm for Mining Frequent Sets. In Proc. FIMI, 2003.
• 8: G. Marketos, E. Frentzos, I. Ntoutsi, N. Pelekis, A. Raffaetà, and T. Theodoridis. Building Real-World Trajectory Warehouses. In MobiDE, pages 8--15, 2008.
• 9: R. S. Monteiro, G. Zimbrao, H. Schwarz, B. Mitschang, and J. M. de Souza. Building the Data Warehouse of Frequent Itemsets in the DWFIST Approach. In Proc. ISMIS, pages 294--303, 2005.
• 10: S. Orlando, R. Orsini, A. Raffaetà, A. Roncato, and C. Silvestri. Trajectory Data Warehouses: Design and Implementation Issues. Journal of Computing Science and Engineering, 1(2): 240--261, 2007.
• 11: N. Pelekis, Y. Theodoridis, S. Vosinakis, and T. Panayiotopoulos. Hermes - A Framework for Location-Based Data Management. In Proc. EDBT, 2006.
• 12: Claudio Silvestri , Salvatore Orlando, Approximate mining of frequent patterns on streams, Intelligent Data Analysis, v.11 n.1, p.49-73, January 2007
• 13: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.7 Database Administration

General Terms:
Algorithms, Design, Experimentation

Keywords:
aggregate function, frequent patterns, trajectories