Dimensionality reduction for long duration and complex spatio-temporal queries

ABSTRACT

In this paper we present an approach to mine and query spatio-temporal data with the aim of finding interesting patterns and understanding the underlying data generating process. An important class of queries is based on the flock pattern. A flock is a large subset of objects moving along paths close to each other for a certain pre-defined time. One approach to process a "flock query" is to map spatio-temporal data into a high dimensional space and reduce the query into a sequence of standard range queries which can be presented using a spatial indexing structure. However, as is well known, the performance of spatial indexing structures drastically deteriorates in high dimensional space. In this paper we propose a preprocessing strategy which consists of using a random projection to reduce the dimensionality of the transformed space. Our experimental results show, for the first time, the possibility of breaking the curse of dimensionality in a spatio-temporal setting.

REFERENCES

• 1: Porcupine caribou herd satellite collar project. http://www.taiga.net/satellite/.
• 2: Dimitris Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins, Journal of Computer and System Sciences, v.66 n.4, p.671-687, 1 June 2003 [doi>10.1016/S0022-0000(03)00025-4]
• 3: G. Al-Naymat, S. Chawla, and J. Gudmundsson. Dimensionality reduction for long duration and complex spatio-temporal queries. TR 600. ISBN 1-86487-874-6, University of Sydney, July 2006.
• 4: Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998 [doi>10.1145/293347.293348]
• 5: Anthony Bagnall , Chotirat Ann Ratanamahatana , Eamonn Keogh , Stefano Lonardi , Gareth Janacek, A Bit Level Representation for Time Series Data Mining with Shape Based Similarity, Data Mining and Knowledge Discovery, v.13 n.1, p.11-40, July 2006 [doi>10.1007/s10618-005-0028-0]
• 6: Marc Benkert , Joachim Gudmundsson , Florian Hübner , Thomas Wolle, Reporting flock patterns, Proceedings of the 14th conference on Annual European Symposium, p.660-671, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_59]
• 7: Ella Bingham , Heikki Mannila, Random projection in dimensionality reduction: applications to image and text data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.245-250, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502546]
• 8: David Eppstein , Michael T. Goodrich , Jonathan Z. Sun, The skip quadtree: a simple dynamic data structure for multidimensional data, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064138]
• 9: Joachim Gudmundsson , Marc van Kreveld, Computing longest duration flocks in trajectory data, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183471.1183479]
• 10: J. Gudmundsson, M. van Kreveld, and B. Speckmann. Efficient detection of motion patterns in spatio-temporal data sets. To appear in GeoInformatica, 2006.
• 11: R. Güting, M. Bohlen, M. Erwig, C. Jensen, N. Lorentzos, E. Nardelli, M. Schneider, and J. R. Viqueira. Spatio-temporal models and languages: An approach based on data types. In Spatio-Temporal Databases: The CHOROCHRONOS Approach, pages 117--176. Springer-Verlag, 2003.
• 12: W. B. Johnson and J. Lindenstrauss. Extensions of lipschitz mappings into a hilbert space. In Conference in modern analysis and probability, pages 189--206. Amer. Math. Soc, 1982.
• 13: Patrick Laube , Stephan Imfeld, Analyzing Relative Motion within Groups of Trackable Moving Point Objects, Proceedings of the Second International Conference on Geographic Information Science, p.132-144, September 25-28, 2002
• 14: P. Laube, M. van Kreveld, and S. Imfeld. Finding REMO -detecting relative motion patterns in geospatial lifelines. In 11th International Symposium on Spatial Data Handling, pages 201--214, 2004.
• 15: F. Verhein and S. Chawla. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases. In Database Systems for Advanced Applications: 11th International Conference, DASFAA, pages 187--201, Singapore, 2006. Springer Berlin-Heidelberg.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Keywords:
data mining, dimensionality reduction, spatio-temporal data