Invited Talk

Space-efficient representations of complex objects

Rajeev Raman (University of Leicester, UK)

In the last 10-15 years there has been a great increase in our understanding of space-efficient representations of ``simple'' objects such as trees and strings (or simple graph classes) but with increasingly more powerful operations, the objects we often wish to represent in real life are more complex. In this talk I will touch upon some ``lesser-known'' objects including binary relations, DAGs and posets and the techniques we can use to represent and operate upon them efficiently.

Slide

Succinct Trees: Theory and Practice

Kunihiko Sadakane (National Institute of Informatics)

Trees are one of the most fundamental data structures. Many succinct representations of ordered and labeled trees and succinct indices for queries have been proposed. In this talk, I will discuss how these were extended and simplified. I will also discuss practical implementations of succinct trees.

Slide

Succinct Data Structures for Analyzing Document Collections

Daisuke Okanohara (Preferred Infrastructure)

I present an overview of state-of-the-art techniques in analyzing document collections using succinct data structures including compressed full-text indicies, range color query, and top-k query. Throughout, I put emphasis on practical aspect of these techniques and implementation details.

Slide

Program

12/1

10:50-11:00 Welcome

11:00-12:00 3 talks (20minx3)
Keisuke Goto, Hideo Bannai, Shunsuke Inenaga and Masayuki Takeda
Fast q-gram Mining on SLP Compressed Strings

Mahito Sugiyama, Tadashi Yoshioka and Akihiro Yamamoto
High-throughput Data Stream Classification on Trees

Ryohei Saito, Tetsuji Kuboyama, Yuta Yamakawa, and Hiroshi Yasuda
Task Summarization for User Behavior Clustering

12:00-13:30 Lunch

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

15:00-15:30 Coffee Break

15:30-17:00 Kunihiko Sadakane (90min)

12/2

9:30-10:30 3 talks (20min x 3)
Yasuo Tabei and Koji Tsuda
Fast Similarity Search for Large-scale Graph Databases with Wavelet Trees

Yoshiyuki Yamamoto, Kouichi Hirata and Tetsuji Kuboyama
On Computing Tractable Variations of Unordered Tree Edit Distance with Network Algorithms

Shoichi Higuchi, Tomohiro Kan, Yoshiyuki Yamamoto and Kouichi Hirata
An A* Algorithm for Computing Edit Distance between Rooted Labeled Ordered Trees

10:30-11:00 Coffee Break

11:00-12:30 Daisuke Okanohara (90min)

12:30-13:30 Lunch

13:30-14:50 4 talks (20 x 4)
Takuya Akiba, Kentaro Imajo and Daisuke Okanohara
Engineering Parallel String Sorting Algorithms

Yuichi Kameda and Akihiro Yamamoto
Mining Closed Weighted Itemsets for Numerical Transaction Databases

Masaya Nakahara, Shirou Maruyama, Tetsuji Kuboyama and Hiroshi Sakamoto
Grammar-Based Compression for Frequent Pattern Mining

Keisuke Otaki and Akihiro Yamamoto
Preserving Privacy with Dummy Data in Set Operations on Itemsets

14:50-15:00 Farewell