Suggested Final Project Topics

Why they're worth studying: R-trees sit right at the intersection of theory and practice. There are a

number of variations on R-trees (Hilbert R-trees, R* trees, etc.) used in real-world systems. If you're in-

terested in exploring geometric data structures and potentially implementing some of your own optimiza-

tions on a traditional data structure, you may want to give these a try!

A Caveat: While the original paper on R-trees is a good introduction to the topic, there’s been a lot of

work in advancing R-trees since then. Much of the efficiency gains reported are practical improvements

rather than theoretical improvements, meaning that a study of R-trees will likely require you to do your

own investigations to determine which optimizations are worthwhile and why. You should be prepared to

do a good amount of independent work verifying the claims that you find, since computer hardware has

changed a lot since R-trees first hit the scene.

Ropes

Ropes are an alternative representation of strings backed by balanced binary trees. They make it possible

to efficiently concatenate strings and to obtain substrings, but have the interesting property that accessing

individual characters is slower than in traditional array-backed strings.