Carnegie Mellon University
15-826 Multimedia and Data Mining
Fall 2025 - C. Faloutsos

Final exam study guide
Final version (Nov. 23, 2025)

Important Preliminaries:

Material in red background: finalized since the draft of 11/21. Everything else is unchanged.
Material in yellow background: is important.
No aids allowed, except

two, standard 8'' x 11.5'' pages, with your notes (you may use both sides) and
pocket calculators: strongly recommended (logarithms)

Time and place:
- Sun 12/14, 1-4pm, VIRTUAL, on the usual zoom# . Please double-check the 'hub': https://www.cmu.edu/hub/docs/final-exams.pdf
- Make-up exam: on Tue 12/9, 5-8pm, virtual (on the usual zoom#). Contact instructor, if you prefer the make-up slot.
Duration: 3 hours
The exam will be comprehensive, with at least 80% of the points on the material after the midterm.
Office hours (all on the usual zoom#):
- Tue Dec. 2, 2-3pm
- Wed Dec. 3, 2-3pm (extra)

Reminders:

Drill questions (similar to the exam questions - internal to CMU). Ignore the questions that are out of scope (like hashing etc).
Sample exam is here (needs CMU VPN), and the solutions.
Also check the discussion on canvas.

Material to be examined

All the material we covered, up to and including time series forecasting. Specifically:

1. Slides

From the course schedule, all the slides up to and including conclusions 010_intro-db.pdf - 600_Conclusions.pdf. Notice that the file-names are numbered in increasing order. This range includes the lecture on time series forecasting, and the early lectures on graph mining (420_*.pdf, 435*.pdf, 436_*.pdf)

Excluded: Hashing (030_hashing.pdf).
Excluded: Graph mining generators and tools (430_GraphMining_generators_tools.pdf).
Excluded: Graph mining - Belief propagation (440_GraphMining_BP.pdf).

2. Multimedia Indexing

Secondary key and spatial access methods
- Jon Louis Bentley, Multidimensional binary search trees used for associative searching, 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, Proc. ACM SIGMOD, June 1984, pp. 47-57, Boston, Mass.
- J. Orenstein, Spatial Query Processing in an Object-Oriented Database System, Proc. ACM SIGMOD, May, 1986, pp. 326-336, Washington D.C.
- MM-Textbook, chapters 4 and 5.
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.
- Bernd-Uwe Pagel, Flip Korn and Christos Faloutsos, Deflating the Dimensionality Curse using Multiple Fractal Dimensions, ICDE 2000, San Diego, CA, Feb. 2000.
- Power laws, lognormals etc: M. E. J. Newman, Power laws, Pareto distributions and Zipf's law Contemporary Physics 46, 323-351 (2005) (local pdf copy)
Text and LSI
- MM-Textbook, chapter 6
- Peter W. Foltz and Susan T. Dumais, Personalized Information Delivery: an Analysis of Information Filtering Methods, Comm. of ACM (CACM), 35, 12, Dec. 1992, pp. 51-60.
- SVD: In PTVF ch. 2.6; MM-Textbook Appendix D
- Chungmin Melvin Chen and Nick Roussopoulos, Adaptive Selectivity Estimation Using Query Feedbacks, SIGMOD 1994.
- PageRank: Sergey Brin, Lawrence Page The Anatomy of a Large-Scale Hypertextual Web Search Engine (1998) (local pdf);
- HITS: Jon M. Kleinberg Authoritative Sources in a Hyperlinked Environment JACM, 46,5 (1999) (local pdf)
- HITS and PageRank: [Graph-Textbook] Ch.15.
- Tensors: [Graph-Textbook] Ch.16.
- ICA: Jia-Yu Pan, Christos Faloutsos, Masafumi Hamamoto and Hiroyuki Kitagawa: AutoSplit: Fast and Scalable Discovery of Hidden Variables in Stream and Multimedia Databases, PAKDD, Sydney, Australia, May 2004.
Time sequences
- MM-Textbook, 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 IEEE Computer 28, 9, Sep. 1995, pp. 23-32.
- Journal of Intelligent Inf. Systems, 3, 3/4, pp. 231-262, 1994 An earlier, more technical version of the IEEE Computer '95 paper.
- FastMap: MM-Textbook 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 ACM SIGMOD 95, pp. 163-174.
- DFT/DCT: In PTVF ch. 12.1, 12.3, 12.4; in MM-Textbook Appendix B.
- Wavelets: In PTVF ch. 13.10; in MM-Textbook Appendix C
- Karhunen-Loeve: in MM-Textbook Appendix D.
- JPEG: Gregory K. Wallace, The JPEG Still Picture Compression Standard, CACM, 34, 4, April 1991, pp. 31-44
- MPEG: D. Le Gall, MPEG: a Video Compression Standard for Multimedia Applications CACM, 34, 4, April 1991, pp. 46-58
- Laurens van der Maaten, Geoffrey Hinton, Visualizing Data using t-SNE, JMLR 9(86):2579−2605, 2008. local copy.
- Leland McInnes, John Healy, James Melville, UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction, arxiv, 2018 local copy.
- Fractal compression: M.F. Barnsley and A.D. Sloan, A Better Way to Compress Images, BYTE, Jan. 1988, pp. 215-223.
- MM-Textbook, chapter 9

3. Data mining

Graph mining and social networks
- Patterns in graphs [Graph-Textbook, ch 3-8]
- Michalis Faloutsos, Petros Faloutsos and Christos Faloutsos, On Power-Law Relationships of the Internet Topology, SIGCOMM 1999.
- R. Albert, H. Jeong, and A.-L. Barabasi, Diameter of the World Wide Web Nature, 401, 130-131 (1999).
- Haveliwala, Taher Haveliwala (2003) Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search. Technical Report. Stanford InfoLab. (Extended version of the WWW2002 paper on Topic-Sensitive PageRank.)
- Jure Leskovec, Jon Kleinberg, Christos Faloutsos Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, KDD 2005, Chicago, IL, USA, 2005.

Reminders - textbooks etc:

Recall that several of the links are internal to CMU and need VPN.

Required texts

[MM-Textbook] C. Faloutsos Searching Multimedia Databases by Content, Kluwer Academic Press, 1996. Evaluation draft (internal to CMU - pdf)
[Graph-Textbook] Deepayan Chakrabarti and Christos Faloutsos Graph Mining: Laws, Tools and Case Studies, Morgan Claypool, 2012. Evaluation draft (internal to CMU - pdf).

Recommended texts

[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

Last modified: Nov. 23, 2025, by Christos Faloutsos; added 'excluding BP' on Dec. 02, 2025.

Carnegie Mellon University 15-826 Multimedia and Data Mining Fall 2025 - C. Faloutsos

Final exam study guide Final version (Nov. 23, 2025)