Invited Talk

Tutorial on Succinct Data Structures

Rajeev Raman (University of Leicester, UK)

The talk gives an introduction to succinct data structures and some applications. The focus will be on bit-vectors, trees (including cardinal and ordinal trees) and some applications.

Space-efficient data structures for strings and sequences

Roberto Grossi (University of Pisa, Italy)

The talk describes some succinct and compressed data structures for strings and sequences. The first part of the talk is devoted to wavelet trees for a sequences of symbols, providing also the ground for discussing a number of applications. The second part involves prefix searching on a set of strings, and describes some succinct data structures for storing a set of strings. The third part of the talk considers a sequence of strings (not to be confused with a set of strings) and introduces the wavelet trie supporting extra functionalities with respect to the wavelet tree. The discussed results are joint works with P. Ferragina, A. Gupta, G. Ottaviano, K. Sadakane, R. Shah, J.S. Vitter, B. Xu.

Succinct data structures for the range minimum query problem

Srinivasa Rao Satti (Seoul National University, South Korea)

The two-dimensional range maximum query (2D-RMQ) problem is to pre-process a static two-dimensional array A of ordered values so that subsequent queries, asking for the the position of the smallest element in the sub-matrix defined by a (user-specified) range of rows and range of columns, can be answered efficiently. The talk presents various time-space trade-offs between the space used to store the structure and the time required to answer a query. It will also focus on determining the "effective entropy" of 2D-RMQ, i.e., how many bits are needed to encode A so that 2D-RMQ queries can be answered without access to A.

The results are part of joint work with Gerth Brodal, Pooya Davoodi, Mordecai J. Golin, John Iacono, Danny Krizanc, Moshe Lewenstein, Rajeev Raman and Sunil Shende.

Program

11/30

10:50 - 11:00 Welcome

11:00 - 12:00 2 talks (30 min x 2)
Fast Exact Distance Queries on Large Networks by Pruned Shortest-Path Trees
Takuya Akiba, Yoichi Iwata, and Yuichi Yoshida

Fast and Succinct Indices Based on Zero-Suppressed Binary Decision Diagrams
Shuhei Denzumi, Jun Kawahara, Koji Tsuda, Hiroki Arimura, and Shin-ichi Minato

12:00 - 13:30 Lunch

13:30 - 15:00 Rajeev Raman (90min)

15:00 - 15:30 Coffee Break

15:30 - 17:00 Roberto Grossi (90 min)

12/1

9:00 - 10:30 3 talks (30min x 3)

Space-Efficient Grammar-Based Compression
Yoshimasa Takabatake, Yasuo Tabei, and Hiroshi Sakamoto

Implementation of Succinct de Bruijn Graphs
Alexander Bowe, Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya

Succinct Multibit Tree for Large-Scale Chemical Fingerprint Searches
Yasuo Tabei

10:30 - 11:00 Coffee Break

11:00 - 12:30 Srinivasa Rao Satti (90min)

12:30 - 13:30 Lunch

13:30 - 15:00 3 talks (30min x 3)

Binary Classification Using Fast Gaussian Filtering Algorithm
Kentaro Imajo, Keisuke Otaki, and Akihiro Yamamoto

Finding Large Elements in Factorized Tensors
Michael E. Houle, Hisashi Kashima, and Michael Nett

Speeding Up Compact Trie Structures on Word RAM and Its Applications
Takuya Takagi, Takashi Uemura, and Hiroki Arimura

15:00 - 15:30 Coffee Break

15:30 - 16:30 Panel Discussion (Future Directions)
Raman, Grossi, Satti, Minato, Tsuda

12/2
10:00 - 17:00 Whole-day Discussion at Miyazaki Kanko Hotel