CSc 538
Project Topic List

Topics are divided into categories based on the subjects we've covered over the last few weeks. Each topic lists one or more starting references to help you begin. Remember, this starting paper will be of central use to you in understanding the topic, but by no means should it be the only resource you consult.

Dynamic hashing

Distributed hash tables (DHT) (taken)

H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica.,
"Looking Up Data in P2P Systems", Communications of the ACM, Vol. 46, No. 2, Feb. 2003

Physical database organization

Partition Attributes Across (PAX) model
Ailamaki, DeWitt, et al, "Weaving Relations for Cache Performance", VLDB 2001.

Data morphing
Hankins, Patel, "An Adaptive Cache-Conscious Storage Technique", VLDB 2003.

Fractured mirrors
Ramamurthy, DeWitt, Su, "A Case for Fractured Mirrors", VLDB 2002.

Fates storage manager
Shao, Schindler, Schlosser, Ailamaki, "Clotho: Decoupling memory page
layout from storage organization", VLDB 2004.

Indexes and other access methods

CSB⁺ trees
Rao, Ross, "Making B⁺ Trees Cache Conscious in Main Memory", SIGMOD 2000.

pB⁺ trees and fpB⁺ trees
Chen et al, "Improving Index Performance through Prefetching", SIGMOD 2001.
Chen, Gibbons, Mowry, Valentin, "Fractal Prefetching B⁺ Trees:
Optimizing both Cache and Disk Performance", SIGMOD 2002.

Making B-trees cooperate with caches
Bender, Demaine, et al, "Cache-oblivious B-trees", FOCS 2000.
Graefe and Larson, "B-Tree Indexes and CPU Caches", ICDE 2001.

Join algorithms

Dynamic hash join
DeWitt and Naughton, "Dynamic Memory Hybrid Hash Join", Tech Report

Double pipelined hash join
Ives, Florescu, Friedman, Levy, Weld, "An Adaptive Query Execution System
for Data Integration", SIGMOD Record, 28(2): 299-310, June 1999.

Xjoin
Urhan and Franklin, "Xjoin: A Reactively Scheduled Pipelined Join Operator",
IEEE Data Engineering Bulletin, 23(2):7-18, 2000.

Hash-merge join (taken)
Mokbel, Lu, and Aref, "Hash-Merge Join: A Non-blocking Join Algorithm for
Producing Fast and Early Join Results", ICDE pp. 251-263, 2004.

Progressive merge join
Dittrich, Seeger, Taylor, and Widmayer, "Progressive Merge Join: A Generic and Non-blocking
Sort-based Join Algorithm", VLDB, pp.299-310, 2002.

Radix-partitioned hash-join
Manegold, Boncz et al, "Cache-conscious Radix-Decluster Projections", VLDB 2004.

Adaptive query processing

Eddies (taken)
Avnur and Hellerstein, "Eddies: Continuously adaptive query processing", SIGMOD 2000.
Hellerstein, et al, "Adaptive query processing: Technology in evolution", IEEE Database
Engineering Bulletin, June 2000.

The STAIRs system (taken)
Deshpande and Hellerstein, "Lifting the Burden of History from
Adaptive Query Processing", VLDB 2004.