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.

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.

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.

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