March 25, 2018 12:30


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.

More Information

Date April 10, 2018 (Tue) 14:00 - 15:00


〒103-0027 Nihonbashi 1-chome Mitsui Building, 15th floor, 1-4-1 Nihonbashi,Chuo-ku, Tokyo