Discovering Patterns in Streams and Graphs
Aalborg University, July 2007
Instructor: C. Faloutsos (CMU)
Reading List

Textbooks

• [Textbook] C. Faloutsos Searching Multimedia Databases by Content, Kluwer Academic Press, 1996. Evaluation draft (pdf)

• [PTVF] William H. Press Saul A. Teukolsky William T. Vetterling Brian P. Flannery Numerical Recipes in C Cambridge University Press, 1992, 2nd Edition. On-line evaluation copy

A. Fractals

• Christos Faloutsos and Ibrahim Kamel, Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension, Proc. ACM SIGACT-SIGMOD-SIGART PODS, May 1994, pp. 4-13, Minneapolis, MN.

B. SVD

• Textbook, chapter 6 
• SVD: In PTVF ch. 2.6; Textbook Appendix D
• Karhunen-Loeve: in Textbook Appendix D.

C. Graph mining

• Michalis Faloutsos, Petros Faloutsos and Christos Faloutsos, On Power-Law Relationships of the Internet Topology, SIGCOMM 1999.
• R. Albert, H. Jeong, and A.-L. Barabási, Diameter of the World Wide Web Nature, 401, 130-131 (1999).
• Jure Leskovec, Jon Kleinberg, Christos Faloutsos Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, KDD 2005, Chicago, IL, USA, 2005.

D. Streams, sequences and forecasting

• DFT/DCT: In PTVF ch. 12.1, 12.3, 12.4; in Textbook Appendix B.
• Wavelets: In PTVF ch. 13.10; in Textbook Appendix C
• Time sequences: Textbook, chapters 7, 8 and 10.
• Byong-Kee Yi, Nikolaos D. Sidiropoulos, Theodore Johnson, H.V. Jagadish, Christos Faloutsos and Alex Biliris, Online Data Mining for Co-Evolving Time Sequences, ICDE 2000,  Feb. 2000.

RECOMMENDED OPTIONAL READING

Fractals

•  B. Mandelbrot Fractal Geometry of Nature W.H. Freeman, 1977. (The classic book on fractals).
• Manfred Schroeder, Fractals, Chaos, Power Laws: Minutes From an Infinite Paradise W.H. Freeman and Company, 1991. (An excellent introduction to fractals)

Graph Mining

•  Mining the Web: Discovering Knowledge from Hypertext Data, by Soumen Chakrabarti ,  Morgan-Kaufmann Publishers
•  Linked: The New Science of Networks by Albert-László Barabási (fun reading - very thought provoking)

Stream  mining 

• George E.P. Box, Gwilym M. Jenkins and Gregory C. Reinsel, Time Series Analysis: Forecasting and Control Prentice Hall, 1994 (3rd Edition). (Time series forecasting - the classic approach. It also has the algorithms for linear predictive coding.)
• Andreas S. Weigend and Neil A. Gerschenfeld, Time Series Prediction: Forecasting the Future and Understanding the Past Addison Wesley, 1994. (Time series forecasting: non-linear/chaotic approaches)
• Spiros Papadimitriou, Jimeng Sun and Christos Faloutsos Streaming Pattern Discovery in Multiple Time-Series VLDB 2005, Trondheim, Norway.

Last modified: July 3, 2007, by Christos Faloutsos