Suggested Topics for Projects

GiST : To implement some of the suggested structures you can use the gist library developed at UC Berkeley.
Read the paper and visit the web page for the GiST project to download the library.

Spatial indexing:

Implement one of the following spatial access methods:

R+-tree : T. Sellis, N. Roussopoulos and C. Faloutsos. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In Proc. VLDB 87.
Hilbert R-tree : I. Kamel and C. Faloutsos. Hilbert R-tree: an Improved R-tree Using Fractals. In Proc. VLDB 94.
hB-tree : D. Lomet, and B. Salzberg. The hB-tree: A Multiattribute Indexing Method with Good Guaranteed Performance. In ACM TODS TODS 15(4): 625-658 (1990).

Temporal indexing:

Implement one of the following temporal access methods:

Snapshot Index : V. Tsotras, N. Kangerlaris. The Snapshot Index: An I/O-optimal access method for timeslice queries. In IS 20(3): 237-260 (1995).
Multiversion B-tree : B. Becker, S. Gschwind, T. Ohler, B. Seeger, Peter Widmayer. An Asymptotically Optimal Multiversion B-Tree. In VLDB Journal 5(4): 264-275 (1996).
Multiversion Access Structures : P. Varman, R. Verma. An Efficient Multiversion Access Structure. In IEEE TKDE 9(3): 391-409 (1997).

Spatiotemporal Indexing:

Implement one of the following structures:

Historical R-tree : M. Nascimento, J.R. Silva. Towards Historical R-trees. In Proc. ACM SAC 1998. (hand copy is available in my office)
Time Parametrized R-tree : S. Saltenis, C. Jensen, S. Leutenegger, M. Lopez. Indexing the Positions of Continuously Moving Objects. In Proc. SIGMOD 2000.
STR-tree and TB-tree : D. Pfoser, C. Jensen, Y. Theodoridis. Novel Approaches in Query Processing for Moving Objects. In Proc. VLDB 2000.

High Dimensional Indexing:

Implement one of the following methods:

TV-tree : K.-I. Lin, H. Jagadish, C. Faloutsos. The TV-Tree: An Index Structure for High-Dimensional Data. In Proc. VLDB Journal 3(4): 517-542 (1994).
X-tree : S. Berchtold, D. Keim, H.-P. Kriegel. The X-tree : An Index Structure for High-Dimensional Data. In Proc. VLDB 1996.
VA-file : R. Weber, H.-J. Schek, S. Blott. A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces. In Proc. VLDB 1998.
Locality Sensitive Hashing (LSH) : A. Gionis, P. Indyk, R. Motwani. Similarity Search in High Dimensions via Hashing. In Proc. VLDB 1999.