ISSN 2186-7437

NII Shonan Meeting Report

No. 2013-10

Compact Data structures for Big Data
Kunihiko Sadakane
Wing-Kin Sung
September 27–30, 2013

National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo, Japan

Compact Data structures for Big Data
Organizers:
Kunihiko Sadakane (National Institute of Informatics)
Wing-Kin Sung (National University of Singapore)
September 27–30, 2013
Big Data are structured and unstructured datasets whose size is in the orderof billions or trillions. Because of their diversity and size, it is diﬃcult to store,
search and analyze them. This meeting therefore focuses on algorithms anddata structures for eﬃcient manipulation of Big Data. Especially, the meetingis devoted to compact data structures for managing Big Data.
Typical examples of big data are genomic sequences and gene expression
data, Web and SNS data, sensor data in intelligent transport systems, etc.
Traditional data structures do not scale to handle such data, and therefore weshould design new data structures to handle them.
Although the amount of data explodes, the amount of the underlying information inside the data may not be exploded because it is observed that many
big datasets are redundant. In the Web, many webpages were copies of others.
In global positioning system (GPS), GPS position data change continuously,
which can be compressed using diﬀerential encoding. In genomics, although different individuals have diﬀerent genomes, the individual genomes have highly
similarity. Therefore we can compress such data by identifying the similar parts.
After the data is compressed, other issues are how to access and search themeﬃciently. Traditional data structures are not designed to handle compresseddata and they may not manipulate Big Data well because the size of the data
structures exceeds the limit of memory usage, or searching time increases dueto their size. To handle these problems, researchers have worked on developing compact data structures. Such data structures are also called compressedor succinct data structures. They are much smaller than standard data structures, while keeping the same access time to data in theory. However actual
performance of such compact data structures for storing Big Data is unknown
or unsatisfactory.
The aim of this workshop is to bring together researchers active in the areasof compact data structures to exchange ideas for handling Big Data. We will
discuss methods for compressing and storing Big Data. We will also discuss
how to design time- and space-eﬃcient data structures for them. Throughdiscussion and sharing of knowledge, we hope to promote collaborations andfurther improve data structures for Big Data.

1

Participants
Rajeev Raman
Venkatesh Raman
Srinivasa Rao Satti
Ian Munro
Moshe Lewenstein
Gonzalo Navarro
Francisco Claude
Travis Gagie
Simon Gog
Jesper Larsson
Sebastiano Vigna
Giuseppe Ottaviano
Ankur Gupta
Hiroshi Sakamoto
Shirou Maruyama
Tetsuo Shibuya
Taku Onodera
Takuya Akiba
Hiroki Arimura
Shin-ichi Minato
Takuya Kida
Shuhei Denzumi
Yasuo Tabei
Koji Tsuda
Anish Shrestha
Martin FrithTakeaki Uno
Alexander Bowe
Atsushi Koike
Wing-Kin Sung
Kunihiko Sadakane

University of Leicester
The Institute of Mathematical Sciences
Seoul National University
University of Waterloo
Bar-Ilan University
University of Chile
Universidad Diego Portales / Akori
University of Helsinki
The University of Melbourne
IT University of Copenhagen
Università degli Studi di Milano
University of Pisa
Butler University
KyutechPreferred Infrastructure
University of Tokyo
University of Tokyo
University of Tokyo
Hokkaido University
Hokkaido University
Hokkaido University
Hokkaido University
Japan Science and Technology Agency
AIST
University of Tokyo
CBRC, AIST
NII
NII
NII
National University of Singapore
NII

2

Schedule
September 27, 2013
9:00 - 10:30
Ian Munro
Rajeev Raman
Moshe Lewenstein

Session 1
Succinct data structures for representing equivalence classes
Encodings for top-k and range selection
Two Dimensional Range Minimum Queries and Fibonacci Lattices

11:00 - 12:00
Sebastiano Vigna
Simon Gog

Session 2
Quasi-Succinct Indices
Integer Alphabet-based Self-Indexes at Terabyte Scale

14:00 - 15:40
Travis Gagie
Martin Frith

Session 3
An Alignment-Based Index for Genomic Datasets
Bio-sequence similarity search with spaced suﬃx arrays andsubset suﬃx arrays
Succinct de Bruijn Graphs
Detecting Superbubbles in Assembly Graphs

Alexander Bowe
Taku Onodera
16:00 - 18:00

September 28, 2013
9:00 - 11:00
Srinivasa Rao Satti
Venkatesh Raman
Ankur Gupta
Gonzalo Navarro
11:30 - 12:30
Francisco Claude
Giuseppe Ottaviano
14:00 - 16:20
Anish Shrestha
Yasuo Tabei
Tetsuo Shibuya
Jesper Larsson
Takuya Akiba

16:20 - 18:00

Session 4
Discussions

Session 5
Selection from Read-Only Memory with Limited Workspace
Improved Selection Algorithms for Integers in Read-only Memory and Restore Models
Online Multiselection
Document Retrieval on General Sequences
Session 6
Adaptive Data Structures for Permutations and Binary Relations
Compressed tries and top-k string completion
Session 7
New Challenges to Processing DNA Data from Modern-day
Sequencers
Succinct data structures for scalable similarity search in ChemBioinformatics
Fast Indexing Method for Protein 3-D Structure Searching
Encoding and modeling for set compression
Fast Exact Shortest-Path Distance Queries on Large Networks
by Pruned Landmark Labeling
Session 8
Discussions

3

September 29, 2013
9:00 - 11:00
Hiroshi Sakamoto
Shirou Maruyama
Hiroki Arimura
Takuya Kida
11:30 - 12:00
Shin-ichi Minato

September 30, 2013
9:00 - 10:30
Shuhei Denzumi
Koji Tsuda
Takeaki Uno
10:30 - 12:00

Session 9
An application of stream compression
Fully-Online Grammar Compression
Faster Broad-Word Pattern Matching Algorithms for Regular
Expressions and Trees
Data Compression using Variable-to-Fixed Length Codes
Session 10
ZDD-Based Representation for Large-Scale Sparse Datasets
and Z-Skip-Links for Fast Traversal

Session 11
DenseZDD: A Fast and Compact Data Structure for Family of
Sets & PathSeqBDD: A DAG Index based on Sequence BDD
Enumeration Algorithms and Statistical Signiﬁcance
Similarity based Approach for Compression of Noisy Data
Session 12
Discussions

4Overview of Talks
Succinct Data Structures for Representing Equivalence Classes
Ian Munro, University of Waterloo
Given a partition of an n element set into equivalence classes, we consider
time-space tradeoﬀs for representing it to support the query that asks whether
two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same component in
an undirected graph or in the same strongly connected component in a directed
graph.

Encodings for Top-k and Range Selection
Rajeev Raman, University of Leicester
We study the problem of encoding the positions the top-k elements of anarray A[1..n] for a given parameter 1 ≤ k ≤ n. Speciﬁcally, for any i andj, we wish create a data structure that reports the positions of the largest
k elements in A[i..j] in decreasing order, without accessing A at query time.
This is a natural extension of the well-known encoding range-maxima query
problem, where only the position of the maximum in A[i..j] is sought, and ﬁnds
applications in document retrieval and ranking. We give (sometimes tight)
upper and lower bounds for this problem and some variants thereof.

Two Dimensional Range Minimum Queries and Fibonacci
Lattices
Moshe Lewenstein, Bar-Ilan University
Given a matrix of size N , two dimensional range minimum queries (2DRMQs) ask for the position of the minimum element in a rectangular range
within the matrix. We study trade-oﬀs between the query time and the additional space used by indexing data structures that support 2D-RMQs. Using anovel technique—the discrepancy properties of Fibonacci lattices—we give an
indexing data structure for 2D-RMQs that uses O(N/c) bits additional spacewith O(c log c(log log c)2 ) query time, for any parameter c, 4 ≤ c ≤ N . Also,
when the entries of the input matrix are from {0, 1}, we show that the query
time can be improved to O(c log c) with the same space usage.

Quasi-Succinct IndicesSebastiano Vigna, Università degli Studi di Milano
Compressed inverted indices in use today are based on the idea of gap compression: documents pointers are stored in increasing order, and the gaps between successive document pointers are stored using suitable codes which represent smaller gaps using less bits. Additional data such as counts and positions
is stored using similar techniques. A large body of research has been built inthe last 30 years around gap compression, including theoretical modeling of5

the gap distribution, specialized instantaneous codes suitable for gap encoding,and ad hoc document reorderings which increase the eﬃciency of instantaneouscodes. This paper proposes to represent an index using a diﬀerent architecture
based on quasi-succinct representation of monotone sequences. We show that,besides being theoretically elegant and simple, the new index provides expected
constant-time operations and, in practice, signiﬁcant performance improvementson conjunctive, phrasal and proximity queries.

Integer Alphabet-based Self-Indexes at Terabyte Scale
Simon Gog, The University of Melbourne
We show that succinct data structures can be engineered to support theseterabyte-scale data sets. We present a new version of the succinct data structure library (SDSL) which provides the functionality to index large IR data
sets. The library provides wavelet trees, compressed suﬃx arrays, FM-Indexes
and compressed suﬃx trees which support both integer and byte alphabets.
All data structures are carefully engineered to support space and time eﬃcientconstruction and fast runtime performance.

An Alignment-Based Index for Genomic Datasets
Travis Gagie, University of HelsinkiWith current hardware and software, a standard computer can now hold in
RAM an index for approximate pattern matching on about half a dozen human genomes. Sequencing technologies have improved so quickly, however, thatscientists will soon demand indexes for thousands of genomes. Whereas mostresearchers who have addressed this problem have proposed completely new
kinds of indexes, we recently described a simple technique that scales standard
indexes to work on more genomes. Our main idea was to ﬁlter the dataset with
LZ77, build a standard index for the ﬁltered ﬁle, and then create a hybrid ofthat standard index and an LZ77-based index. In this talk we describe how to
our technique to use alignments instead of LZ77, in order to simplify and speed
up both preprocessing and random access.

Bio-sequence Similarity Search with Spaced Suﬃx Arrays
and Subset Suﬃx Arrays
Martin Frith, CBRC, AISTFor many decades, the main way of analyzing biological sequences has been
by comparing and aligning them. This remains true today. Modern tasks include: comparing whole genomes; aligning bisulﬁte-converted DNA reads to a
genome; aligning long, high-error sequences from single molecule sequencers;aligning ancient or degraded DNA; comparing metagenomic DNA to a protein
database. Over the decades, statistically powerful alignment techniques havebeen developed. These include: log likelihood ratio scoring matrices, pair hidden Markov models, and probabilistic alignment. Unfortunately, these methods

6are rarely used with modern deep sequencing data, perhaps because of a mistaken belief that they are too slow. This talk will demonstrate that they canbe made fast enough, and that they oﬀer great beneﬁts. A statistical approachis especially useful in cases that beneﬁt more from statistical modeling, suchas: larger divergence between sequences, extreme AT-richness (e.g. DNA from
Plasmodium or Dictyostelium), and bisulﬁte-converted DNA.

Succinct de Bruijn Graphs
Alexander Bowe, NII
We propose a new succinct de Bruijn graph representation. If the de Bruijn
graph of k-mers in a DNA sequence of length N has m edges, it can be represented in 4m+o(m) bits. This is much smaller than existing ones. The numbersof outgoing and incoming edges of a node are computed in constant time, andthe outgoing and incoming edge with given label are found in constant time andO(k) time, respectively.

Detecting Superbubbles in Assembly Graphs
Taku Onodera, University of Tokyo
We introduce a new concept of a subgraph class called a superbubble foranalyzing assembly graphs, and propose an eﬃcient algorithm for detecting it.
Most assembly algorithms utilize assembly graphs like the de Bruijn graph or
the overlap graph constructed from reads. From these graphs, many assembly
algorithms ﬁrst detect simple local graph structures (motifs), such as tips andbubbles, mainly to ﬁnd sequencing errors. These motifs are easy to detect,but they are sometimes too simple to deal with more complex errors. The
superbubble is an extension of the bubble, which is also important for analyzing
assembly graphs. Though superbubbles are much more complex than ordinary
bubbles, we show that they can be eﬃciently enumerated. We propose an
average-case linear time algorithm (i.e., O(n + m) for a graph with n vertices
and m edges) for graphs with a reasonable model, though the worst-case timecomplexity of our algorithm is quadratic (i.e., O(n(n + m))).

Selection from Read-Only Memory with Limited Workspace
Srinivasa Rao Satti, Seoul National University
In the classic selection problem the task is to ﬁnd the kth smallest of
N elements. We study the complexity of this problem on a space-bounded
random-access machine: The input is given in a read-only array and the capacity of workspace is limited. We prove that the linear-time prune-and-searchalgorithm—presented in most textbooks on algorithms—can be adjusted to use
O(N ) bits instead of Θ(N ) words of extra space. Prior to our work, the best
known algorithm by Frederickson could perform the task with O(N ) bits ofextra space in O(N log∗ N ) time. In particular, our result separates the spacerestricted random-access model and the multi-pass streaming model (since we
can bypass the Ω(N log ∗ N ) lower bound known for the latter model).

7

Improved Selection Algorithms for Integers in Read-only
Memory and Restore Models
Venkatesh Raman, The Institute of Mathematical Sciences
We consider the classical selection and sorting problems in a model where
the initial permutation of the input has to be restored after completing thecomputation. While the requirement of the restoration is stringent compared tothe classical versions of the problems, this model is more relaxed than a readonly memory where the input elements are not allowed to be moved within the
input array. We ﬁrst show that for a sequence of n integers, selection (ﬁnding
the median or more generally the k-th smallest element for a given k) can bedone in O(n) time using O(lgn) words of extra space in this model. In contrast,
no linear-time selection algorithm is known which uses polylogarithmic space inthe read-only memory model.

Online Multiselection
Ankur Gupta, Butler University
We introduce a new online algorithm for the multiselection problem which
performs a sequence of selection queries on a given unsorted array. We showthat our online algorithm is 1-competitive in terms of data comparisons. In
particular, we match the bounds (up to lower order terms) from the optimal
oﬄine algorithm proposed by Kaligosi et al. [ICALP 2005]. We provide experimental results comparing online and oﬄine algorithms. These experiments
show that our online algorithms require fewer comparisons than the best-known
oﬄine algorithms. Interestingly, our experiments suggest that our optimal online algorithm (when used to sort the array) requires fewer comparisons thanboth quicksort and mergesort.

Document Retrieval on General Sequences
Gonzalo Navarro, University of Chile
Document retrieval is one of the best established information retrieval activities since the sixties, pervading all search engines. Its aim is to obtain, froma collection of text documents, those most relevant to a pattern query. Current technology is mostly oriented to “natural language” text collections, where
inverted indices are the preferred solution. As successful as this paradigm has
been, it fails to properly handle some East Asian languages and other scenarios where the “natural language” assumptions do not hold. In this survey wecover the recent research in extending the document retrieval techniques toa broader class of sequence collections, which has applications bioinformatics,
data and Web mining, chemoinformatics, software engineering, multimedia information retrieval, and many others. We focus on the algorithmic aspects ofthe techniques, uncovering a rich world of relations between document retrieval
challenges and fundamental problems on trees, strings, range queries, discretegeometry, and others.

8Adaptive Data Structures for Permutations and Binary Relations
Francisco Claude, Universidad Diego Portales / Akori
We present new data structures for representing binary relations in an adaptive way, that is, for certain classes of inputs we achieve space below the general
information theoretic lower bound, while achieving reasonable space complexities in the worst case. Our approach is derived from a geometric data structure[Arroyuelo et al., TCS 2011]. When used for representing permutations, it
converges to a previously known adaptive representation [Barbay and Navarro,
STACS 2009]. However, this new way of approaching the problem shows that we
can support range searching in the adaptive representation. We extend this approach to representing binary relations, where no other adaptive representations
using this chain decomposition have been proposed.

Compressed Tries and Top-k String Completion
Giuseppe Ottaviano, University of Pisa
In this talk we will discuss space-eﬃcient representations of string sets. Aftera brief review of succinct tree representations, we will show how to use pathdecomposition trees of the compacted trie of a string set to obtain a spaceeﬃcient and fast string set representation. We will then show how to adapt thetechnique to scored string sets, where each string is assigned a score, in orderto support top-k completion queries, that is, given a query string p, return thek highest-scored strings that are preﬁxed by p.

New Challenges to Processing DNA Data from Modernday Sequencers
Anish Shrestha, University of Tokyo
Aligning short DNA sequences (“reads”) to a reference genome is usually
one of the ﬁrst steps in processing DNA data from modern-day sequencers.
This task is likely to get more complicated because of several developments: (1)reads are getting longer, whereas most of the widely-used methods today are
customized for short reads, (2) while sequencers are capable of longer reads, they
still remain extremely error-prone, (3) multiple reference genomes are available
for some species, and it is desirable to incorporate this extra information during
alignment, (4) sequencer throughput is increasing, (5) there are increasingly
many species whose reference genomes are not available.

Succinct Data Structures for Scalable Similarity Search in
ChemBioinformatics
Yasuo Tabei, Japan Science and Technology Agency
Analyzing functional interactions between small compounds and proteinsis indispensable in genomic drug discovery. Since rich information on various

9compound-protein interactions is available in recent molecular databases, strong
demands for making best use of such databases require to invent powerful methods to help us ﬁnd new functional compound-protein pairs on a large scale. We
present succinct data structures that eﬃciently performs similarity search indatabases for chemical compounds and compound-protein pairs with respect
to both binary ﬁngerprints and real-valued properties. Our methods achieveboth time and space eﬃciency by developing the data structures called succinct
multibit trees and interval-splitting trees, which eﬃciently prune the uselessportions of search space. We experimentally test our methods on the ability toretrieve similar compounds and compound-protein pairs for a query from large
databases with over 30 million compounds and 200 million compound-protein
pairs and show that our methods perform signiﬁcantly better than other possible
approaches.

Fast Indexing Method for Protein 3-D Structure Searching
Tetsuo Shibuya, University of Tokyo
Searching for protein structure-function relationships using three-dimensional(3D) structural coordinates represents a fundamental approach for determining
the function of proteins with unknown functions. In this talk, we introduce
a new indexing algorithm for for fast protein 3-D structure similarity queries.
The new method runs in O(m + N/m0.5 ) time, after O(N log N ) preprocessing,where N is the database size and m is the query length. It is about 2 to 50 times
faster than the previous practically best-known O(N ) algorithm, which was also
proposed by us, even if we include the preprocessing time. It is almost 20-1000
times faster than the naive comparison algorithm, according to experiments on
a huge SCOP database.

Encoding and Modeling for Set Compression
Jesper Larsson, IT University of Copenhagen
This talk addresses the compressing unordered sets of distinct items. Specifically, some available options for deﬁning a context for probabilistic coding is
discussed. Existing methods for compressing sets of integers in a ﬁxed range(or equivalently, ﬁxed-length bitstrings) are recapitulated, and a novel methodthat allows use of statistics for individual elements described.

Fast Exact Shortest-Path Distance Queries on Large Networks by Pruned Landmark Labeling
Takuya Akiba, University of Tokyo
We propose a new exact method for shortest-path distance queries on largescale networks. Our method precomputes distance labels for vertices by performing a breadth-ﬁrst search from every vertex. Seemingly too obvious and too
ineﬃcient at ﬁrst glance, the key ingredient introduced here is pruning during
breadth-ﬁrst searches. While we can still answer the correct distance for any
pair of vertices from the labels, it surprisingly reduces the search space and sizes
10

of labels. Moreover, we show that we can perform 32 or 64 breadth-ﬁrst searches
simultaneously exploiting bitwise operations. We experimentally demonstratethat the combination of these two techniques is eﬃcient and robust on various
kinds of large-scale real-world networks. In particular, our method can handlesocial networks and web graphs with hundreds of millions of edges, which are
two orders of magnitude larger than the limits of previous exact methods, withcomparable query time to those of previous methods.

An Application of Stream Compression
Hiroshi Sakamoto, Kyutech
Our research group propose the framework of stream compression for speedingup network migration using grammar compression. We design algorithm andprove its upper/lower bound expressiveness.

Fully-Online Grammar Compression
Shirou Maruyama, Preferred Infrastructure
We present a fully-online algorithm for constructing straight-line programs(SLPs). A naive array representation of an SLP with n variables on an alphabetof size σ requires 2n lg(n + σ) bits. As already shown in [Tabei et al., CPM13],
in oﬄine setting, this size can be reduced to n lg(n + σ) + 2n + o(n) , which is
asymptotically equal to the information-theoretic lower bound. Our algorithm
achieves the same size in online setting, i.e., characters of an input string are
given one by one to update the current SLP.

Faster Broad-Word Pattern Matching Algorithms for Regular Expressions and Trees
Hiroki Arimura, Hokkaido University
In this talk, we present the recent progress of bit-parallel pattern matchingalgorithms for regular expressions and trees. We focus on a variant of bit-parallel
approaches called broad-word pattern matching, which uses Boolean and arithmetic operations on w-bit registers based on parallelism inside a computer word.
We show eﬃcient algorithms for the regular expression matching problem forexpressions with small height, and variations of the tree matching and inclusion
problems under many-to-one matching.

Data Compression using Variable-to-Fixed Length Codes
Takuya Kida, Hokkaido University
A VF code is an encoding scheme that uses a ﬁxed-length code, and thus,
one can easily access the compressed data. However, conventional VF codes
usually have an inferior compression ratio to that of variable-length codes. We
propose a new VF coding method that applies a ﬁxed-length code to the set ofrules extracted by the Re-Pair algorithm. We also present several experimental

11results to show that the proposed coding achieves comparable performance towell-known compression tools based on variable-length codes.

ZDD-Based Representation for Large-Scale Sparse Datasets
and Z-Skip-Links for Fast Traversal
Shin-ichi Minato, Hokkaido University
This talk gives a brief explanation of the data structures called BDD (Binary
Decision Diagram) and ZDD (Zero-suppressed BDD), for eﬃciently manipulating large-scale sparse datasets. We also discuss “Z-SkipLink,” an additional
data structure for fast traversal of ZDDs.

DenseZDD: A Fast and Compact Data Structure for Familyof Sets & PathSeqBDD: A DAG Index based on Sequence
BDD
Shuhei Denzumi, Hokkaido University
Zero-suppressed Binary Decision Diagram (ZDD) is a data structure to manipulate families of sets. Current ZDDs require a huge amount of memory andmembership operations are slow. We introduce DenseZDD, a compressed index
for a static ZDD. Our technique not only indexes set families compactly but
also executes fast membership operations. Sequence Binary Decision Diagram(SeqBDD) is a data structure to manipulate sets of strings. There have been
many indexes for linear texts. However, indexes for directed acyclic graphs(DAGs) have not been studied enough. We introduce PathSeqBDD, a complete
inverted ﬁle for a DAG based on SeqBDD. Our technique allows us to retrieve
frequencies and occurrences of patterns for given DAGs.

Enumeration Algorithms and Statistical SigniﬁcanceKoji Tsuda, AIST
More than three transcription factors often work together to enable cells to
respond to various signals. The detection of combinatorial regulation by multiple transcription factors, however, is not only computationally nontrivial but
also extremely unlikely because of multiple testing correction. The exponential
growth in the number of tests forces us to set a strict limit on the maximum arity.
Here, we propose an eﬃcient branch-and-bound algorithm called the “limitlessarity multiple-testing procedure” (LAMP) to count the exact number of testablecombinations and calibrate the Bonferroni factor to the smallest possible value.
LAMP lists signiﬁcant combinations without any limit, whereas the family-wiseerror rate is rigorously controlled under the threshold. In the human breast
cancer transcriptome, LAMP discovered statistically signiﬁcant combinationsof as many as eight binding motifs. This method may contribute to uncover
pathways regulated in a coordinated fashion and ﬁnd hidden associations inheterogeneous data.

12

Similarity based Approach for Compression of Noisy Data
Takeaki Uno, NII
We approach genome sequence compression from the use of similarity. The
noisy data such as genome sequence does not accept usual compression techniques, such as word frequency and run length. However, those data often
contain long or short similarity much inside. So, we extract these similarity andrepresent the data by diﬀerence from similar ones. By the computational experiments for genome strings, we show that our method is very eﬃcient comparedto the existing best method.

13

Discussion
On September 27th, 2013, we have a 2-hour discussion session. We partition
our people into three groups, every group discuss three topics on compact data
structures for big data. The topics are: (1) Theory aspect on compact data
structure, (2) Practical implementation aspect on compact data structure, and(3) Applications on compact data structure. After that, the whole team came
together and summarized the ﬁnding.
From the feedback of the participants, people tends to work on one single
topic in the past and they got to know better the relationship among the three
topics. Below, we summarize the points we discussed.
(1) Theory aspect: We discussed what are the new problems on compact
data-structures. It seems that we don’t have some good data-structures
for compact set. It may be an interesting problem to work on in the future.
People also asked if there is any compact way to store prime numbers.
(2) Practical aspect: We discussed how to deliver the practical implementations of diﬀerent compact data-structures. It may be good if we can makea standard package for people to download do use. Another issue is on
how to give credit to practical implementations. Currently, there is little
conferences for practical implementations.
(3) Application aspect: Compact data-structure ﬁnds a lot of applications inbioinformatics. For example, BWA and Bowtie successfully applied BWT(or FM-index) to align short reads on the reference genome. However,there is not enough communication between application people and theory
people. More discussions are needed to build the connection.

14