CS 525: Advanced Database Organization - Spring 2020

Previous Semesters


Some links with information related to the course: More info will be added during the course.

Research Papers

Below is a list of research papers related to the course organized by topic.

Storage and Buffering

The five-minute rule twenty years later, and how flash memory changes the rules
G. Graefe
DAMOS  (2007)
The five-minute rule ten years later, and other computer storage rules of thumb
J. Gray and G. Graefe
SIGMOD  (1997)
The 5 minute rule for trading memory for disc accesses and the 10 byte rule for trading memory for CPU time
J. Gray and F. Putzolu
SIGMOD  395--398  (1987)
Query evaluation techniques for large databases
G. Graefe
ACM Computing Surveys  25  73--169  (1993)
ARC: A Self-Tuning, Low Overhead Replacement Cache
N. Megiddo and D. Modha
Proceedings of the 2nd USENIX Conference on File and Storage Technologies    115--130  (2003)
The LRU-K page replacement algorithm for database disk buffering
E. J. O'neil and P. E. O'neil and G. Weikum
SIGMOD Record  22  297--306  (1993)
Principles of database buffer management
W. Effelsberg and T. Haerder
ACM Transactions on Database Systems (TODS)  9  560--595  (1984)

Index Structures

Performance of B-tree concurrency control algorithms
V. Srinivasan and M. J. Carey
SIGMOD    416--425  (1991)
On optimistic methods for concurrency control
H. T. Kung and J. T. Robinson
ACM Transactions on Database Systems (TODS)  6  213--226  (1981)
Concurrency of operations on B-trees
R. Bayer and M. Schkolnick
Acta informatica  9  1--21  (1977)
Granularity of locks and degrees of consistency in a shared data base
J. N. Gray and R. A. Lorie and G. R. Putzolu and I. L. Traiger
IBM Research Division      (1976)
Database Cracking
S. Idreos and M. Kersten and S. Manegold
CIDR    (2007)
Dynamic hash tables
P. A. Larson
Communications of the ACM  31  446--457  (1988)
Extendible hashing---a fast access method for dynamic files
R. Fagin and J. Nievergelt and N. Pippenger and H. R. Strong
ACM Transactions on Database Systems (TODS)  4  315--344  (1979)
Linear hashing: A new tool for file and table addressing
W. Litwin
VLDB  6  212--223  (1980)
Performance of linear hashing schemes for primary key retrieval
Y. Manolopoulos and N. Lorentzos
Information Systems  19  433--446  (1994)
R-trees: a dynamic index structure for spatial searching
A. Guttman
The VLDB Journal    47--57  (1984)
Self-selecting, self-tuning, incrementally optimized indexes
G. Graefe and H. Kuno
EDBT    371--381  (2010)
The R-tree: A dynamic index for multi-dimensional objects
T. Sellis and N. Roussopoulos and C. Faloutsos
The VLDB Journal    507--518  (1987)
The R*-tree: an efficient and robust access method for points and rectangles
N. Beckmann and H. P. Kriegel and R. Schneider and B. Seeger
ACM SIGMOD Record  19  322--331  (1990)
Log-logarithmic worst-case range queries are possible in space theta(N).
D. Willard
INFO. PROC. LETT.  17  81--84  (1983)
An efficient digital search algorithm by using a double-array structure
J.-I. Aoe
Software Engineering, IEEE Transactions on  15  1066--1077  (1989)
Histogram-aware sorting for enhanced word-aligned compression in bitmap indexes
O. Kaser and D. Lemire and K. Aouiche
Workshop on Data warehousing and OLAP    1--8  (2008)
Trie memory
E. Fredkin
Communications of the ACM  3  490--499  (1960)