# Reading List - 826

https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html

  

###  Carnegie Mellon University   
[ 15-826: Multimedia and Data Mining](https://www.cs.cmu.edu/~christos/courses/826.F25/)   
Fall 2025 - Christos Faloutsos   
Reading list 
### NOTICE:
Several of the links are internal to CMU. 
### Required texts
  * [MM-Textbook] C. Faloutsos  _Searching Multimedia Databases by Content_ , Springer, 1996. Evaluation draft (internal to CMU - [pdf](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/BOOK/book.pdf))
  * [Graph-Textbook] Deepayan Chakrabarti and Christos Faloutsos [_Graph Mining: Laws, Tools and Case Studies_](https://link.springer.com/book/10.1007/978-3-031-01903-6), Springer, 2012. Evaluation draft (internal to CMU - [pdf](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/BOOK/book_graph_mining_prepub.pdf)).  



### Recommended texts
  * [HKP] Jiawei Han, Jian Pei and Hanghang Tong, [ Data Mining: Concepts and Techniques](https://hanj.cs.illinois.edu/bk4/), 4th ed., Morgan Kaufmann, 2023 ([amazon link](https://www.amazon.com/Data-Mining-Concepts-Techniques-Management/dp/0128117605)).  

  * [PTVF] William H. Press Saul A. Teukolsky William T. Vetterling Brian P. Flannery _Numerical Recipes in C_ Cambridge University Press, [ ](http://apps.nrbook.com/c/index.html) [ 1992, 2nd Edition, free on-line. ](http://s3.amazonaws.com/nrbook.com/book_C210.html) Latest is [ 3rd edition, 2007. ](http://numerical.recipes/)
  * Undergraduate DB textbook, for those who took a db class too long ago: 
    * Raghu Ramakrishnan, Johannes Gehrke, _"[Database Management Systems](http://pages.cs.wisc.edu/%7Edbbook/),"_ McGraw-Hill 2002 (3rd ed).


* * *
## Foils:
In pdf, from the [course schedule](https://www.cs.cmu.edu/~christos/courses/826.F25/schedule.html) page.
## A. Multimedia Indexing
  * **Secondary key and spatial access methods**
    * Jon Louis Bentley, [Multidimensional binary search trees used for associative searching,](http://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/p509-bentley.pdf) Comm. of the ACM (CACM), Volume 18 , Issue 9, pp. 509-517, (September 1975)
    * A. Guttman [_R-Trees: a Dynamic Index Structure for Spatial Searching_](http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/r-trees.PDF), Proc. ACM SIGMOD, June 1984, pp. 47-57, Boston, Mass.
    * J. Orenstein, [_Spatial Query Processing in an Object-Oriented Database System_](http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/z-order.PDF), Proc. ACM SIGMOD, May, 1986, pp. 326-336, Washington D.C.
    * [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf), chapters 4 and 5.
  * **Fractals**  

    * Christos Faloutsos and Ibrahim Kamel, [_Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension_](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS.OLDER/pods94.ps.gz), Proc. ACM SIGACT-SIGMOD-SIGART PODS, May 1994, pp. 4-13, Minneapolis, MN.
    * Bernd-Uwe Pagel, Flip Korn and Christos Faloutsos, _[Deflating the Dimensionality Curse using Multiple Fractal Dimensions](http://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/PUBLICATIONS/icde2K-knn.pdf)_ , ICDE 2000, San Diego, CA, Feb. 2000.   

    * Power laws, lognormals etc: M. E. J. Newman, [Power laws, Pareto distributions and Zipf's law](https://arxiv.org/abs/cond-mat/0412004v3) Contemporary Physics 46, 323-351 (2005) (local [pdf copy](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/0412004-newman05.pdf))
  * **Text and LSI**
    * [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf), chapter 6
    * Peter W. Foltz and Susan T. Dumais, [_Personalized Information Delivery: an Analysis of Information Filtering Methods_](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/CMU-ONLY/dumaisCACM92.pdf), Comm. of ACM (CACM), 35, 12, Dec. 1992, pp. 51-60.
    * SVD: In [PTVF](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#nr) ch. 2.6; [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf) Appendix D
    * PageRank: Sergey Brin, Lawrence Page _The Anatomy of a Large-Scale Hypertextual Web Search Engine_ (1998) (local [pdf](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/google-anatomy.pdf))
    * HITS: Jon M. Kleinberg _Authoritative Sources in a Hyperlinked Environment_ JACM, 46,5 (1999) (local [pdf](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/kleinberg99authoritative.pdf)) 
    * Tensors survey: Papalexakis, Faloutsos, Sidiropoulos [ Tensor for Data Mining and Data Fusion: Models, Applications, and Scalable Algorithms](https://dl.acm.org/citation.cfm?id=2915921) ACM Trans. on Intelligent Systems and Technology, 8,2, Oct. 2016. [(local copy)](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/a16-papalexakis.pdf)
    * Tensors: [[Graph-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#Textbook2)] Ch.16.  

  * **Time sequences**
    * [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf), chapters 7, 8 and 10.
  * **DSP and image databases**
    * Myron Flickner, Harpreet Sawhney, Wayne Niblack, Jon Ashley, Qian Huang, Byron Dom, Monika Gorkani, Jim Hafner, Denis Lee, Dragutin Petkovic, David Steele and Peter Yanker [_Query by Image and Video Content: the QBIC System_](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/CMU-ONLY/QBIC95.pdf) IEEE Computer 28, 9, Sep. 1995, pp. 23-32. 
    * FastMap: [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf) chapter 11; Also in: C. Faloutsos and K.I. Lin [_FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets_](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS.OLDER/sigmod95.pdf) ACM SIGMOD 95, pp. 163-174[.](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS.OLDER/sigmod95.ps.gz)
    * DFT/DCT: In [PTVF](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#nr) ch. 12.1, 12.3, 12.4; in [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf) Appendix B.
    * Wavelets: In [PTVF](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#nr) ch. 13.10; in [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf) Appendix C
    * Karhunen-Loeve: in [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf) Appendix D.
    * JPEG: Gregory K. Wallace, [_The JPEG Still Picture Compression Standard_](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/CMU-ONLY/jpeg.pdf), CACM, 34, 4, April 1991, pp. 31-44
    * MPEG: D. Le Gall, _[MPEG: a Video Compression Standard for Multimedia Applications](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/CMU-ONLY/mpeg.pdf)_ CACM, 34, 4, April 1991, pp. 46-58
    * Laurens van der Maaten, Geoffrey Hinton, [_Visualizing Data using t-SNE_](https://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf), JMLR 9(86):2579−2605, 2008. [ local copy. ](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/tsne_vandermaaten08a.pdf)
    * Leland McInnes, John Healy, James Melville _,[UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://arxiv.org/abs/1802.03426)_, arxiv, 2018 [ local copy.](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/umap_1802.03426.pdf)  

    * Fractal compression: M.F. Barnsley and A.D. Sloan, [_A Better Way to Compress Images_](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/CMU-ONLY/ImageCompression.pdf), BYTE, Jan. 1988, pp. 215-223.
    * [MM-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#cf), chapter 9


## B. Data mining
  * Graph mining and social networks: 
    * Michalis Faloutsos, Petros Faloutsos and Christos Faloutsos, [_On Power-Law Relationships of the Internet Topology_](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/sigcomm99.ps.gz), SIGCOMM 1999.
    * R. Albert, H. Jeong, and A.-L. Barabasi, _[Diameter of the World Wide Web](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/Diameter_of_the_web.pdf)_ Nature, **401** , 130-131 (1999).
    * Reka Albert and Albert-Laszlo Barabasi _[Statistical mechanics of complex networks](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/Statistical_mechanics_of_complex_networks.pdf)_ , Reviews of Modern Physics, **74** , 47 (2002).  

    * Haveliwala, Taher H. (2003) [Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/Haveliwala_www2003.pdf). Technical Report. Stanford InfoLab. (Extended version of the WWW2002 paper on Topic-Sensitive PageRank.)
    * D. Chakrabarti, S. Papadimitriou, D. Modha and C. Faloutsos, [Fully Automatic Cross-Associations](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/kdd04-cross-assoc.pdf), in KDD 2004 (pages 79-88), Washington, USA
    * Hanghang Tong, Christos Faloutsos [Center-Piece Subgraphs: Problem Definition and Fast Solutions](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/kdd06CePS.pdf), KDD 2006, Philadelphia, PA  

    * Jure Leskovec, Jon Kleinberg, Christos Faloutsos [Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/kdd05-power.pdf), KDD 2005, Chicago, IL, USA, 2005.
    * J. Leskovec, D. Chakrabarti, J. Kleinberg, and C. Faloutsos, [Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/pkdd05-kronecker.pdf), in PKDD 2005, Porto, Portugal
    * Danai Koutra, Tai-You Ke, U. Kang, Duen Horng Chau, Hsing-Kuo Kenneth Pao, and Christos Faloutsos. [ Unifying guilt-by-association approaches: theorems and fast algorithms. ](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/pkdd11-koutra-unifying.pdf) ECML/PKDD'11, Athens, Greece. 
    * [[Graph-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#Textbook2)], Ch.18: virus propagation
    * [[Graph-Textbook](https://www.cs.cmu.edu/~christos/courses/826.F25/readinglist.html#Textbook2)], Ch.19: Case studies: Random walk with restarts, image captioning.  

  * Time series forecasting 
    * Chungmin Melvin Chen and Nick Roussopoulos, [Adaptive Selectivity Estimation Using Query Feedbacks](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/query-feedbacks.pdf), SIGMOD 1994.  

    * Byong-Kee Yi, Nikolaos D. Sidiropoulos, Theodore Johnson, H.V. Jagadish, Christos Faloutsos and Alex Biliris, [_Online Data Mining for Co-Evolving Time Sequences_](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/muscles-icde2k.pdf), ICDE 2000, Feb. 2000.
    * Steven L. Brunton, Joshua L. Proctor, and J. Nathan KutzAuthors _, Discovering governing equations from data by sparse identification of nonlinear dynamical systems_ , PNAS 113 (15) 3932-3937, March 28, 2016, <https://doi.org/10.1073/pnas.1517384113> ([ local copy](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/brunton-et-al-sindy.pdf)).  

  * Statistics background: In [PTVF](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#nr) pp. 620-621 and ch. 14.4-14.5;
  * AI background / Classification 
    * [[HKP](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#Jiawei)] chapter 6  

    * Rakesh Agrawal, Sakti Ghosh, Tomasz Imielinski, Bala Iyer and Arun Swami [_An Interval Classifier for Database Mining Applications_](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/rakesh-vldb92.ps.gz) VLDB Conf. Proc. Vancouver, BC, Canada, Aug. 1992, pp. 560-573.
    * M. Mehta, R. Agrawal and J. Rissanen, _`[SLIQ: A Fast Scalable Classifier for Data Mining](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/sliq.ps.gz)'_, Proc. of the Fifth Int'l Conference on Extending Database Technology, Avignon, France, March 1996.
  * Data Mining in Databases: 
    * Association Rules: 
      * [[HKP](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#Jiawei)] chapter 4
      * Rakesh Agrawal, Tomasz Imielinski and Arun Swami _[Mining Association Rules Between Sets of Items in Large Databases](https://www.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/courses/826-resources/PAPERS+BOOK/rakesh-AR-sigmod93.ps.gz)_ Proc. ACM SIGMOD, Washington, DC, May 1993, pp. 207-216
      * Ahmed El-Kishky, Yanglei Song, Chi Wang, Clare R. Voss, Jiawei Han: [_Scalable Topical Phrase Mining from Text Corpora_](https://dl.acm.org/doi/10.14778/2735508.2735519). Proc. VLDB Endow. 8(3): 305-316 (2014)  

    * Cluster analysis: [[HKP](https://www.cs.cmu.edu/~christos/courses/826.F25/reading_list.html#Jiawei)] chapters 8-9.  

  * Miscellaneous (ICA, approximate counting) 
    * Jia-Yu Pan, Christos Faloutsos, Masafumi Hamamoto and Hiroyuki Kitagawa: [_AutoSplit: Fast and Scalable Discovery of Hidden Variables in Stream and Multimedia Databases,_](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/PAKDD04AutoSplit.pdf) PAKDD, Sydney, Australia, May 2004.
    * Christopher Palmer, Phillip Gibbons and Christos Faloutsos, [_ANF: A Fast and Scalable Tool for Data Mining in Massive Graphs_](https://www.cs.cmu.edu/%7Echristos/PUBLICATIONS/kdd02-anf.pdf), KDD 2002, Edmonton, Alberta, Canada, July 2002
    * _[Efficient and Tunable Similar Set Retrieval](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/Research-Gionis-et-al.pdf),_ by Aristides Gionis, Dimitrios Gunopulos and Nikos Koudas, ACM SIGMOD, Santa Barbara, California, May 21-24, 2001.
    * _[New sampling-based summary statistics for improving approximate query answers](https://www.cs.cmu.edu/%7Echristos/courses/826-resources/PAPERS+BOOK/p331-gibbons.pdf),_ by Phillip B. Gibbons and Yossi Matias, ACM SIGMOD, pp 331 - 342, Seattle, Washington, 1998.
    * Ahmed Metwally, Divyakant Agrawal, Amr El Abbadi: _[Efficient Computation of Frequent and Top-k Elements in Data Streams](https://link.springer.com/chapter/10.1007/978-3-540-30570-5_27)._ ICDT 2005: 398-412  



* * *
## RECOMMENDED OPTIONAL READING
Additional, **optional** citations, that may be useful for your project:
## Multimedia indexing
  * Fractals 
    * B. Mandelbrot [_Fractal Geometry of Nature_](http://books.google.com/books?id=qHEzHAAACAAJ&dq=fractal+geometry+of+nature&ei=1RSLR_zJFIrqiwHTzYjEBQ) W.H. Freeman, 1977. (The classic book on fractals).
    * Manfred Schroeder, [_Fractals, Chaos, Power Laws: Minutes From an Infinite Paradise_](https://www.amazon.com/Fractals-Chaos-Power-Laws-Infinite/dp/0716723573) W.H. Freeman and Company, 1991. (**An excellent introduction to fractals**)


## Data mining
  * Time sequences 
    * George E.P. Box, Gwilym M. Jenkins and Gregory C. Reinsel, [_Time Series Analysis: Forecasting and Control_](https://www.amazon.com/Time-Analysis-Forecasting-Control-3rd/dp/0130607746) 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_](http://books.google.com/books?hl=en&id=36OH9a5hpzQC&dq=weigend+gershenfeld&printsec=frontcover&source=web&ots=YQg_hDOVnD&sig=PP2c7nUSfAShnU0Veaw2PvIWgd4#PPP1,M1) Addison Wesley, 1994. (Time series forecasting: non-linear/chaotic approaches)
  * Graph mining: 
    * [_Mining the Web: Discovering Knowledge from Hypertext Data_](https://www.cse.iitb.ac.in/%7Esoumen/mining-the-web/), by [Soumen Chakrabarti](https://www.cse.iitb.ac.in/%7Esoumen/) ,  Morgan-Kaufmann Publishers
    * [_Linked: The New Science of Networks_](https://www.amazon.com/Linked-Science-Networks-Albert-Laszlo-Barabasi/dp/0738206679) by Albert-Laszlo Barabasi (fun reading - very thought provoking)


* * *
_Last modified: Aug. 26, 2025, by Christos Faloutsos_