Suggested Final Project Topics

Learned Index Structures

A learned index structure is a hybrid between a classical data structure (often, a B-tree or a Bloom filter)

and a deep learning model. The idea is to have the deep model learn some sort of common patterns

present in input data sets and make an educated guess of how to handle an element, falling back on the

classical data structure to avoid errors.

Why they’re worth studying: Learned index structures are a fairly recent (2017) idea and it’s unclear

whether they’re here to stay or just a passing fad. Investigating how these data structures perform in prac-

tice, and potentially adding your own contributions to the field, would be a great way to get a sense of the

shape of things to come.

The CR-Precis

The count sketch and count-min sketch work by using randomly-selected hash functions to distribute ele-

ments (and, in the case of the count sketch, to choose the sign to associate with each element). A natural

question then arises: can you get the same sort of guarantees from a similar data structure that doesn’t use

any randomization? Amazingly, the answer is yes, and it’s thanks to the magic of number theory.