Efficient anomaly monitoring over moving object trajectory streams

ABSTRACT

Lately there exist increasing demands for online abnormality monitoring over trajectory streams, which are obtained from moving object tracking devices. This problem is challenging due to the requirement of high speed data processing within limited space cost. In this paper, we present a novel framework for monitoring anomalies over continuous trajectory streams. First, we illustrate the importance of distance-based anomaly monitoring over moving object trajectories. Then, we utilize the local continuity characteristics of trajectories to build local clusters upon trajectory streams and monitor anomalies via efficient pruning strategies. Finally, we propose a piecewise metric index structure to reschedule the joining order of local clusters to further reduce the time cost. Our extensive experiments demonstrate the effectiveness and efficiency of our methods.

REFERENCES

• 1: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 2: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 3: Stephen D. Bay , Mark Schwabacher, Mining distance-based outliers in near linear time with randomization and a simple pruning rule, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956758]
• 4: Markus M. Breunig , Hans-Peter Kriegel , Raymond T. Ng , Jörg Sander, LOF: identifying density-based local outliers, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.93-104, May 15-18, 2000, Dallas, Texas, United States
• 5: A. Bulut and A.K. Singh. SWAT: Hierarchical stream summarization in large networks. In ICDE, 2003.
• 6: Yuhan Cai , Raymond Ng, Indexing spatio-temporal trajectories with Chebyshev polynomials, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007636]
• 7: Efficient Time Series Matching by Wavelets, Proceedings of the 15th International Conference on Data Engineering, p.126, March 23-26, 1999
• 8: Lei Chen , Raymond Ng, On the marriage of Lp-norms and edit distance, Proceedings of the Thirtieth international conference on Very large data bases, p.792-803, August 31-September 03, 2004, Toronto, Canada
• 9: Lei Chen , M. Tamer Özsu , Vincent Oria, Robust and fast similarity search for moving object trajectories, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066213]
• 10: Tzi-cker Chiueh, Content-Based Image Indexing, Proceedings of the 20th International Conference on Very Large Data Bases, p.582-593, September 12-15, 1994
• 11: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: Like Gao , Zhengrong Yao , X. Sean Wang, Evaluating continuous nearest neighbor queries for streaming time series via pre-fetching, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA [doi>10.1145/584792.584872]
• 13: Pierre Geurts, Pattern Extraction for Time Series Classification, Proceedings of the 5th European Conference on Principles of Data Mining and Knowledge Discovery, p.115-127, September 03-05, 2001
• 14: Victoria Hodge , Jim Austin, A Survey of Outlier Detection Methodologies, Artificial Intelligence Review, v.22 n.2, p.85-126, October 2004 [doi>10.1023/B:AIRE.0000045502.10941.a9]
• 15: Alexander Ihler , Jon Hutchins , Padhraic Smyth, Adaptive event detection with time-varying poisson processes, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150428]
• 16: Wen Jin , Anthony K. H. Tung , Jiawei Han, Mining top-n local outliers in large databases, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.293-298, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502554]
• 17: Eamonn Keogh, Exact indexing of dynamic time warping, Proceedings of the 28th international conference on Very Large Data Bases, p.406-417, August 20-23, 2002, Hong Kong, China
• 18: Eamonn Keogh , Kaushik Chakrabarti , Michael Pazzani , Sharad Mehrotra, Locally adaptive dimensionality reduction for indexing large time series databases, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.151-162, May 21-24, 2001, Santa Barbara, California, United States
• 19: Eamonn Keogh , Jessica Lin , Ada Fu, HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence, Proceedings of the Fifth IEEE International Conference on Data Mining, p.226-233, November 27-30, 2005 [doi>10.1109/ICDM.2005.79]
• 20: Edwin M. Knorr , Raymond T. Ng, Algorithms for Mining Distance-Based Outliers in Large Datasets, Proceedings of the 24rd International Conference on Very Large Data Bases, p.392-403, August 24-27, 1998
• 21: Edwin M. Knorr , Raymond T. Ng , Vladimir Tucakov, Distance-based outliers: algorithms and applications, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.3-4, p.237-253, February 2000 [doi>10.1007/s007780050006]
• 22: Flip Korn , H. V. Jagadish , Christos Faloutsos, Efficiently supporting ad hoc queries in large datasets of time sequences, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.289-300, May 11-15, 1997, Tucson, Arizona, United States
• 23: Jae-Gil Lee , Jiawei Han , Kyu-Young Whang, Trajectory clustering: a partition-and-group framework, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247546]
• 24: Lin Liao , Donald J. Patterson , Dieter Fox , Henry Kautz, Learning and inferring transportation routines, Artificial Intelligence, v.171 n.5-6, p.311-331, April, 2007 [doi>10.1016/j.artint.2007.01.006]
• 25: Junshui Ma , Simon Perkins, Online novelty detection on temporal sequences, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956828]
• 26: Sridhar Ramaswamy , Rajeev Rastogi , Kyuseok Shim, Efficient algorithms for mining outliers from large data sets, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.427-438, May 15-18, 2000, Dallas, Texas, United States
• 27: Yufei Tao , Xiaokui Xiao , Shuigeng Zhou, Mining distance-based outliers from large databases in any metric space, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150447]
• 28: Michail Vlachos , Marios Hadjieleftheriou , Dimitrios Gunopulos , Eamonn Keogh, Indexing multi-dimensional time-series with support for multiple distance measures, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956777]
• 29: Michail Vlachos , Christopher Meek , Zografoula Vagena , Dimitrios Gunopulos, Identifying similarities, periodicities and bursts for online search queries, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007586]
• 30: Byoung-Kee Yi , H. V. Jagadish , Christos Faloutsos, Efficient Retrieval of Similar Time Sequences Under Time Warping, Proceedings of the Fourteenth International Conference on Data Engineering, p.201-208, February 23-27, 1998
• 31: Qiankun Zhao , Steven C. H. Hoi , Tie-Yan Liu , Sourav S. Bhowmick , Michael R. Lyu , Wei-Ying Ma, Time-dependent semantic similarity measure of queries using historical click-through data, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135858]
• 32: Yunyue Zhu , Dennis Shasha, StatStream: statistical monitoring of thousands of data streams in real time, Proceedings of the 28th international conference on Very Large Data Bases, p.358-369, August 20-23, 2002, Hong Kong, China
• 33: Yunyue Zhu , Dennis Shasha, Warping indexes with envelope transforms for query by humming, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872780]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Multimedia databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Experimentation

Keywords:
outlier detection, similarity search, temporal data