Indexing is a game of tradeoffs: Organize your data now and be rewarded with lower read latencies later. The question of whether, how, or when to organize has led to a proliferation of many different, often highly-specialized index structures.
In this talk, I present an alternative that replaces the holistic tradeoff decisions made by classical index structures with smaller, localized organizational transformations. This approach, which we call Just-in-Time Data Structures (JITDs), is based on a grammar for data structure instances. A sentence in this grammar corresponds to a specific physical layout, and many classical data structures can be described as syntactic restrictions on this grammar. Mirroring a just-in-time compiler, a JITD incrementally replaces phrases in a sentence (i.e., physical sub-structures) with different, ideally more efficient ones.
This replacement happens in the background, without blocking reader threads for longer than an atomic pointer swap. JITDs are competitive with existing, commonly-used data structures in common-case scenarios, while exhibiting better performance in dynamic settings. I will present our foundational work on JITDs, and outline some of our more recent work on automatic rewrite policy optimization.
This work is supported by NSF Awards IIS-1617586 and CNS-1629791.
Bio: Oliver Kennedy is an assistant professor at the University at Buffalo. He earned his PhD from Cornell University in 2011 and now leads the Online Data Interactions (ODIn) lab, which operates at the intersection of databases and programming languages. Oliver is the recipient of an NSF CAREER award, UB's Exceptional Scholar Award, and the UB SEAS Early Career Teacher of the Year Award.
Several of his papers have been invited to "Best of" compilations from SIGMOD and VLDB. The ODIn lab is currently exploring uncertain data management, just-in-time data structure design, and "small data" management.