Midterm study guide

All aids allowed, EXCEPT laptops (for the wireless connection).
Duration: 1h 20 minutes
Place: in class, during class time, 1:30-2:50pm, on Tu 2/27.
Extra office hour by instructor: Thu 2/22, 11am-12noon (in addition to the usual Wed 1-2).

Several of the links are internal to CMU and U. Pitt.

[Textbook] C. Faloutsos Searching Multimedia Databases by Content, Kluwer Academic Press, 1996. Evaluation draft (internal to CMU - gzipped postscript and pdf)

Undergraduate DB textbook, for those who took a db class too long ago:
- Raghu Ramakrishnan, Johannes Gehrke, "Database Management Systems," McGraw-Hill 2002 (3rd ed).

MATERIAL TO BE EXAMINED

All the material covered, up to the review lecture of Thu 2/22. Specifically:

From the course schedule, all the foils, up to and including '165_graph_mining.pdf' and '170_fractals2.pdf'. Notice that the file names for the foils are numbered in increasing order.

Primary key access methods
- Litwin, W., (1980), Linear Hashing: A New Tool for File and Table Addressing, VLDB, Montreal, Canada, 1980.
- Textbook, chapters 2-3
Secondary key and spatial access methods
- 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..
- Textbook, chapters 4 and 5.
Fractals
- Ibrahim Kamel and Christos Faloutsos, Hilbert R-tree: An improved R-tree using fractals Proc. of VLDB Conference, Santiago, Chile, Sept. 12-15, 1994, pp. 500-509.
- 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.

Jure Leskovec, Jon Kleinberg, Christos Faloutsos Graphs over Time: Densification Laws, Shrinking Diameters and Possible Explanations, KDD 2005, Chicago, IL, USA, 2005.

Last modified: 02/20/2007, by Christos Faloutsos