Incremental pattern discovery on streams, graphs and tensors

ABSTRACT

Incremental pattern discovery targets streaming applications where the data continuously arrive incrementally. The questions are how to find patterns (main trends) incrementally; or how to efficiently update the old patterns when new data arrive; or how to utilize the patterns to solve other problems such as anomaly detection?

We first investigate a powerful data model, tensor stream (TS), where there is one tensor per timestamp. To capture diverse data formats, we have a zero-order TS for a single time-series (e.g., the stock price over time), a first-order TS for multiple time-series (sensor measurement streams), a second-order TS for matrices (graphs), and a high-order TS for multi-arrays (Internet communication network, source-destination-port). Second, we develop different online algorithms on TS: 1) the centralized and distributed SPIRIT [7] for mining a 1st-order TS, as well as its extensions for local correlation function and privacy preservation; 2) the compact matrix decomposition (CMD) [5] and GraphScope [4] for a 2nd-order TS; 3) the dynamic tensor analysis (DTA) [2], streaming tensor analysis (STA) and window-based tensor analysis (WTA) for a high-order TS. All the techniques are extensively evaluated for real applications such as network forensics, cluster monitoring.

REFERENCES

• 1: Evan Hoke , Jimeng Sun , John D. Strunk , Gregory R. Ganger , Christos Faloutsos, InteMon: continuous mining of sensor data in large-scale self-infrastructures, ACM SIGOPS Operating Systems Review, v.40 n.3, July 2006 [doi>10.1145/1151374.1151384]
• 2: Jimeng Sun , Dacheng Tao , Christos Faloutsos, Beyond streams and graphs: dynamic tensor analysis, 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.1150445]
• 3: Jimeng Sun, Spiros Papadimitriou, and Christos Faloutsos. Distributed pattern discovery in multiple streams. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), 2006.
• 4: Jimeng Sun , Christos Faloutsos , Spiros Papadimitriou , Philip S. Yu, GraphScope: parameter-free mining of large time-evolving graphs, 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.1281266]
• 5: Jimeng Sun, Yinglian Xie, Hui Zhang, and Christos Faloutsos. Less is more: Compact matrix decomposition for large sparse graphs. In SDM, 2007.
• 6: Lieven De Lathauwer. Signal Processing Based on Multilinear Algebra. PhD thesis, Katholieke, University of Leuven, Belgium, 1997.
• 7: Spiros Papadimitriou , Jimeng Sun , Christos Faloutsos, Streaming pattern discovery in multiple time-series, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 8: Stephen Bay , Krishna Kumaraswamy , Markus G. Anderle , Rohit Kumar , David M. Steier, Large Scale Detection of Irregularities in Accounting Data, Proceedings of the Sixth International Conference on Data Mining, p.75-86, December 18-22, 2006 [doi>10.1109/ICDM.2006.93]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models

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

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance

Keywords:
data mining, graph mining, stream mining, tensor analysis