Computing longest duration flocks in trajectory data

ABSTRACT

Moving point object data can be analyzed through the discovery of patterns. We consider the computational efficiency of computing two of the most basic spatio-temporal patterns in trajectories, namely flocks and meetings. The patterns are large enough subgroups of the moving point objects that exhibit similar movement and proximity for a certain amount of time. We consider the problem of computing a longest duration flock or meeting. We give several exact and approximation algorithms, and also show that some variants are as hard as MaxClique to compute and approximate.

REFERENCES

• 1: Boris Aronov , Sariel Har-Peled, On approximating the depth and related problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 2: M. Benkert, J. Gudmundsson, F. Huebner and T. Wolle. Reporting flock patterns. In Proc. of the 14th European Symposium on Algorithms, 2006.
• 3: J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies. Discrete & Computational Geometry 13:41--57, 1995.
• 4: A. U. Frank and J. F. Raper and J.-P. Cheylan (Eds.). Life and motion of spatial socio-economic units. Taylor & Francis, 2001.
• 5: M. R. Garey and D. S. Johnson. Computers and intractability. W. H. Freeman, 1979.
• 6: J. Gudmundsson, M. van Kreveld and B. Speckmann. Efficient Detection of Patterns in 2D Trajectories of Moving Points. To appear in GeoInformatica, 2006.
• 7: R. H. Güting and M. Schneider. Moving objects databases. Morgan Kaufmann Publishers, 2005
• 8: Marios Hadjieleftheriou , George Kollios , Petko Bakalov , Vassilis J. Tsotras, Complex spatio-temporal pattern queries, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 9: Kathleen Hornsby , Max J. Egenhofer, Modeling Moving Objects over Multiple Granularities, Annals of Mathematics and Artificial Intelligence, v.36 n.1-2, p.177-194, September 2002 [doi>10.1023/A:1015812206586]
• 10: J. Håstad. Clique is hard to approximate within n 1-ε. ACTA Mathematica, 182:105--142, 1999.
• 11: P. Kalnis, N. Mamoulis and S. Bakiras. On discovering moving clusters in spatio-temporal data. In Proc. 9th International Symposium on Spatial and Temporal Databases, pages 364--381, 2005.
• 12: G. Kollios, S. Sclaroff and M. Betke. Motion mining: discovering spatio-temporal patterns in databases of human motion. In ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 2001.
• 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 Proc. 11th International Symp. on Spatial Data Handling, pages 201--214, 2004.
• 15: Nikos Mamoulis , Huiping Cao , George Kollios , Marios Hadjieleftheriou , Yufei Tao , David W. Cheung, Mining, indexing, and querying historical spatiotemporal data, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014080]
• 16: Harvey J. Miller , Jiawei Han, Geographic Data Mining and Knowledge Discovery, Taylor & Francis, Inc., Bristol, PA, 2001
• 17: R. T. Ng. Detecting outliers from large datasets. In H. J. Miller and J. Han, editors, Geographic data mining and knowledge discovery, pages 218--235. Taylor & Francis, 2001.
• 18: Porcupine Caribou Herd Satellite Collar project. http://www.taiga.net/satellite/.
• 19: Yunyao Qu , Changzhou Wang , X. Sean Wang, Supporting fast search in time series for movement patterns in multiple scales, Proceedings of the seventh international conference on Information and knowledge management, p.251-258, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288664]
• 20: John F. Roddick , Kathleen Hornsby , Myra Spiliopoulou, An Updated Bibliography of Temporal, Spatial, and Spatio-temporal Data Mining Research, Proceedings of the First International Workshop on Temporal, Spatial, and Spatio-Temporal Data Mining-Revised Papers, p.147-164, September 12, 2000
• 21: N. Sumpter and A. J. Bulpitt. Learning spatio-temporal patterns for predicting object behaviour. Image Vision and Computing, 18(9):697--704, 2000.
• 22: F. Verhein and S. Chawla. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases. In Proc. of the 11th International Conference on Database Systems for Advanced Applications, 2006.
• 23: Wildlife tracking projects with GPS GSM collars. http://www.environmental-studies.de.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, geometric algorithms, moving objects, spatio-temporal patterns