Compact Complete Inverted Files for
Texts and Directed Acyclic Graphs
Based on Sequence Binary Decision Diagram
Shuhei Denzumi1, Koji Tsuda2, 3,Shin-ichi Minato1,2, and Hiroki Arimura1
1) Hokkaido University
2) JST ERATO Minato Discrete Structure Manipulation System Project3) AIST CBRC

Background
Text index is an important data structure for sequence mining
Many text indices have been proposed
Most of their inputs are ordinary linear text

Index for directed acyclic graph (DAG)
Regular expression without infinite repeat, genome with mutations
DAG can represent huge number of strings
Construct indices after expanding it is nonsense
We want to make indices directly from input DAGsCAATGTGCGCA

T

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Complete Inverted Files
Factor automata of automata [Mohri et al., 2007]
Automata for all factors of strings represented by a given automata
Determine whether a pattern occurs as a factor or notComplete Inverted Filesfind(p): Return TRUE if a pattern p occurs as a substring of the input
freq(p): Frequency of p in the input
locate(p): Positions of occurrences of p in the input

General Compressed Suffix Array (GCSA) [Siren et al., 2011]
Complete inverted file for DAG
Very compact because of using succinct data structure
Require special property for the input DAG
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Sequence BDD (SeqBDD)
Sequence Binary Decision Diagram [Loekito et al., 2009]
Acyclic graphs for finite sets of strings
One kind of binarized automata
Member of Binary Decision Diagram (BDD) family
BDD is a graph structure for Boolean functions

Characteristic
Using hash tables
Automatically share all equivalent subgraphs
String set operations by simple recursive algorithms
Union, Intersection, Difference, …
Enumerate all prefixes, suffixes, substrings, and subsequences
Analyzing time/space complexity is difficult

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Definition
Σ: alphabet (totally ordered by ≺)Internal node: a , b , … , z, T/F - terminal node: T / F
1/0 - edge:/SeqBDD: directed acyclic graph
Internal node S, τ(S) ↦ 〈S.lab, S.1, S.0〉
aS.lab: label
SS.1: 1-child
S.lab
abS.0: 0-child
Ordering rule

S.1

S.0

aN.lab ≺ (N.0).laba ≺ b ≺ … ≺ zTF

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Semantics
A path from the root node to the True-terminal nodecorrespond to a strings in the set that SeqBDD represent
Example: SeqBDD for {aa, aba, ba}aEach edge has different meaning
1-edge means choosing the symbol
0-edge means ignoring the symbol
Remember 0-ordering ruleaba

Comparison to automata
T-terminal is finite state
F-terminal is garbage state

TF

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Index for text

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013DAWG
We use end positions (In ccababa, aba occurs at 5 and 7)
Directed Word Acyclic Graph (DAWG) [Blumer et al., 1987]
Complete inverted file for text
Each DAWG node has occurrence information

DAWG for a text ccababa
3,5,7abb0,…,7c1,2ca24,6a3b4aa5,75b6a7Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Main idea
Consider integers as symbols in the alphabet
We can deal with positions as a string
If aba occurs at 5 and 7, the index include aba5 and aba7 as strings

Size complexity of DAG index is not analyzed
Size of DAWG is linear
However, size of occurrence information of DAG index is unknown
We want to reduce the sizeUse binary representation of integers
SeqBDD can share equivalent subgraphs automatically
Lists of raw integers are difficult to be shared
We define a new alphabet Σb=Σ∪{0, 1}, ∀a∈Σ, a ≺ 0 ≺ 1.
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Example
Input text: ccababa
cTc

ababa

1

1

1

1

1

1

0

0

1

1

10

10

101

T

T

T

T

T

TT

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Example
Input text: ccababa
cca11b1aba1110010T
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Example: text index
Input text: ccababa

abbcac{0,…,7} {1,2}

ab{3,5,7} {4,6} {5,7}ababa{2}

{3}

{4}

{5}

{6}

{7}

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Example: integer part
Input text: ccababa{0,…,7}{1,2} {3,5,7}

1

1{4,6}

{5,7}

1

10

1

10

100

10

1

10

1T

T

T

T

T

101

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Index for DAG

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Definition of location
Each node has unique node ID

9Use node IDs as well as positions

For a pattern p
There are some paths that represent pLocation of p is
the end nodes of the paths
Frequency of p is
the number of such end nodesExample
baa: 2 paths and 2 end nodes
aa: 4 paths and 2 end nodes

5a8a4321bab76aaaTCompact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Definition of location
Each node has unique node ID

9Use node IDs as well as positions

For a pattern pThere are some paths that represent pLocation of p is
the end nodes of the pathsFrequency of p is
the number of such end nodes

Examplebaa: 2 paths and 2 end nodes
aa: 4 paths and 2 end nodes

5a8a4321bab76aaa

TCompact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Construct DAG index
Compute union of all nodes
All substrings in a DAG
are the union ofsets of strings
that are representedby all nodes

Append node IDAs well as ordinary text,
we append binary string partto each node

95a8a4321bab76aaaTCompact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Construct DAG index
Compute union of all nodes
All substrings in a DAG
are the union ofsets of strings
that are represented 5by all nodes
aAppend node ID
As well as ordinary text,
we append binary string partto each node
before computing union

98a432

bb{5}

a{3}

a{2}

{9}
76a{7}

a{6}{1}Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

aExample
Input:
95a8

a4
32
1baaab{1,2,5,6}

ab{1,5}a{2,3}a{2}b76aab{1,…,9}a{3,7}

a{2,6}T{1}

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

ExperimentCompact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Setting
Data sets
SeqBDD for word bigrams from bible.txt
SeqBDD for genome sequences truncated fromoriginal sequence every 150/500 symbols

Environment
3.1 GHz Intel Xeon CPU
1 TB DDR2 memory

On SAPPOROBDD package [unpublished]
Each node use 50 ~ 55 bytes
including space for hash tables
Construct DAG index for given SeqBDDs
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Construction time
Looks O(n log n) time
Roughly three seconds per 1 million input nodes
DAG index construction time

5Ecoli150

Computation time (s)4Ecoli500

3BibleAll

2100500000

1000000

1500000

Input SDD size

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Index size
Linear or O(n log n) order
Three times larger than the input SeqBDDs
DAG index size

5000000

Ecoli150

Output PosFSDDdag size

4000000

Ecoli500

3000000BibleAll

2000000

1000000

00

5000001000000

1500000

Input SDD size

Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Conclusion
Complete inverted files for directed acyclic graph
Manipulate occurrence information as strings
Use binary representation for integers
Construct on Sequence BDD environment
Share equivalent subgraphs

ResultTime complexity of construction looks like O(n log n)Space complexity of index is linear or O

Future work
Use more precise definition of frequency and location
Compare with other data structures
Compact Complete Inverted Files for Texts and Directed Acyclic Graphs Based on Sequence Binary Decision Diagramsby Shuhei Denzumi, Koji Tsuda, Shin-ichi Minato, and Hiroki Arimura, 2013-09-04 (WED), Prague Stringology Conference 2013

Thank you!