Elias-Fano Encoding

Title: Elias-Fano Encoding
Subtitle: A powerful tool for data structure design

Abstract: The so-called succinct data structures have acquainted a lot of attention in recent years for their double promising goal: compress data with performance close to the information theoretic lower bound while supporting fast access to data paying a negligible, lower-order term, space factor. The first part of the talk will introduce the Elias-Fano encoding of monotone integer sequences. Then, we will see a recent application of such encoding to the design of a new data structure, called the Elias-Fano Trie, able of handling billions of N-grams in compressed space with excellent practical performance.