Suggested Final Project Topics

Why they’re worth studying: It’s possible to think about vEB trees in a number of different ways. You

can either think of them as binary tries sliced through the middle, or as an optimization on a raw bitvector

scan. That first approach is a novel perspective on tree searches and can be generalized to the van Emde

Boas layout, a way of arranging nodes in a binary search tree to minimize cache misses. That second ap-

proach makes it possible to view vEB trees as an optimized version of the blocking decomposition strat-

egy you’ve seen used for RMQ and elsewhere. Studying vEB trees with these perspectives in mind would

be a great way to come full circle with the techniques we’ve covered this quarter.

Strees

The Stree is a highly optimized implementation of a vEB tree engineered to specifically be fast for 32-bit

integer keys. The Stree was introduced in a paper by Dementiev et al as a way of exploring whether it was

possible to adapt the general-purpose vEB tree into something that could practically, not just theoreti-

cally, outcompete a balanced BST. By combining a number of different strategies together into a unified

whole, they were able to achieve this goal.