Doorkeeper

Elias-Fano Encoding

Tue, 10 Apr 2018 14:00 - 15:00

AIP Nihonbashi Office

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

Register

Registration is closed

Get invited to future events

Free admission

Description

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.

About this community

RIKEN AIP Public

RIKEN AIP Public

Public events of RIKEN Center for Advanced Intelligence Project (AIP)

Join community