PSC 2020

Pointer-Machine Algorithms for
Fully-Online Construction of Suffix
Trees and DAWGs on Multiple Strings
Shunsuke Inenaga
Kyushu University, Japan

Fully-Online Indexing of Multiple Strings


Goal: Indexing multiple strings in a fully-online
manner where each string can grow any time.
Motivation: Indexing multi online/streaming data.
Sensing data, trajectory data, SNS, etc.

index

sensorss1

T1 abcaab

s2

T2 cc

s3

T3 bcdaxuserFully-Online Indexing of Multiple Strings


Goal: Indexing multiple strings in a fully-online
manner where each string can grow any time.
Motivation: Indexing multi online/streaming data.
Sensing data, trajectory data, SNS, etc.

index

sensors
s1
s2
s3

a

T1 abcaab
T2 ccaT3 bcdaxuserFully-Online Indexing of Multiple Strings

Goal: Indexing multiple strings in a fully-online
manner where each string can grow any time.
Motivation: Indexing multi online/streaming data.
Sensing data, trajectory data, SNS, etc.

index

sensorscs1

T1 abcaabc

s2

T2 ccas3

T3 bcdaxuserFully-Online Indexing of Multiple Strings


Goal: Indexing multiple strings in a fully-online
manner where each string can grow any time.
Motivation: Indexing multi online/streaming data.
Sensing data, trajectory data, SNS, etc.

index

sensorss1

T1 abcaabc

s2

T2 ccas3

T3 bcdax

bc?

user

Overview of This Work







We will consider suffix trees and DAWGs as indexing
structures for fully-online multiple strings.
For suffix trees, we propose a Weiner-type algorithm
where strings grow from right to left.
For DAWGs, we propose a Blumer et al.-type algorithm
where strings grow from left to right.
Our model of computation is the pointer machine thatis strictly weaker than the word RAM.

Suffix Trees

The suffix tree of multiple strings is apath-compressed trie that represents
all suffixes of the strings.

[Weiner 1973]

T1 = cabaa$
T2 = abaab#$aabac abaa #$ b#ba$b$
#

#
$aa#b
#

$

Suffix Links

If av is a node and a is a character,then suffix_link(av) = v.

T1 = cabaa$
T2 = abaab#$aabac abaa #$ b#ba$b$##$aasuffix links

#b
#

$

Suffix Links

If av is a node and a is a character,then suffix_link(av) = v.

T1 = cabaa$
T2 = abaab#cabaa$$aaabaa$bac abaa #$ b#baa$b$##$aaaa

suffix links

#b
#

$

Hard Weiner Links
T1 = cabaa$
T2 = abaab#cabaa$$aacabaa$ba

The reversed suffix links withcharacter labels are called
hard Weiner links.

c abaa #$ b#baa$ab$##$aaaa

hard Weiner links

#b
#

$

Not all links are shown.

Soft Weiner Links
T1 = cabaa$
T2 = abaab#
There is no nodefor cabaa.

$acabcaSoft Weiner links are“generalized” Weiner links.

c abaa #$ b#

ba$ab$##$aa

hard Weiner links#soft Weiner linksb#$

Not all links are shown.

Soft Weiner Links
T1 = cabaa$
T2 = abaab#c aSoft Weiner links are“generalized” Weiner links.

baSoft Weiner linkbof node v withbalabel c points toa$
the child node of aalocus for cv.
$acca #$ b
#b$
#

#$aa

hard Weiner links#

soft Weiner linksb#$

Not all links are shown.

Soft Weiner Links
T1 = cabaa$
T2 = abaab#$cacacbcca

Soft Weiner links are“generalized” Weiner links.

c abaa #$ b#

ba$ab$##$aab

hard Weiner links#

soft Weiner linksb#$

Not all links are shown.

DAWGsThe DAWG of multiple strings is alinear-size automaton that recognizes
all substrings of the strings.

[Blumer et al. 1987]

S1 = $aabac
S2 = #baabaaaccbaccab$aab#bbacaaaba

Duality of Suffix Trees and DAWGsA) There is a one-to-one correspondence between
the nodes of the suffix tree of strings andthe nodes of the DAWG of the reversed strings.
19 nodesSuffix Tree of

19 nodesT1 = cabaa$
T2 = abaab#

DAWG of

S1 = $aabac
S2 = #baaba

Duality of Suffix Trees and DAWGsB) There is a one-to-one correspondence between
the Weiner links of the suffix tree of strings andthe edges of the DAWG of the reversed strings.

Suffix Tree of

T1 = cabaa$
T2 = abaab#

DAWG of

S1 = $aabac
S2 = #baaba

Previous and This Work (Suffix Trees)
Right-to-Left Fully-Online Suffix Tree Construction Timealgorithm

single string

multiple strings

modelWeinerO(n log σ)Ω(n1.5)pointermachineTakagi et al.

O(n log σ)O(n log σ)

word RAM

This workO(n (log σ + log d))O(n (log σ + log d))pointermachinen : total string length , σ : alphabet size, d : max. # in-coming Weiner links

Both O(n log σ) ⊆ O(n log n) and O(n (log σ + log d)) ⊆ O(n log n) hold The new algorithm achieves the same worst-case complexity
on a weaker model of computation (pointer machine).

Previous and This Work (DAWGs)
Left-to-Right Fully-Online DAWG Construction Timealgorithm

single string

multiple strings

model

Blumer et al.

O(n log σ)Ω(n1.5)pointermachine

Takagi et al.

O(n log σ)O(n log σ)

word RAM

This workO(n (log σ + log d))O(n (log σ + log d))pointermachinen : total string length , σ : alphabet size, d : max. # in-coming Weiner links

Takagi et al.’s method only maintains an implicit representation of DAWG.
 The new algorithm is the first non-trivial algorithm that maintains
an explicit representation of DAWG for fully-online multiple stings.

Pointer Machine [cf. Tarjan 1979] The pointer machine is an abstract model of computation

where the state of computation is stored as a digraph.
Each node contains a const. number of data and pointers.

 The pointer machine supports instructions (1)-(3):(1) creating / deleting nodes and pointers;(2) manipulating data;(3) performing comparisons,but it does NOT support word RAM instructions (4)-(5):(4) address arithmetics;(5) unit-cost bit-wise operations.

 Still, the pointer machine serves as a good basis formodelling linked structures such as trees and graphs.

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFind the lowest ancestor v ofleaf T that has Weiner linkwith character a.

vaaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFind the lowest ancestor v ofleaf T that has Weiner linkwith character a.

v

aaTWeiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFind the lowest ancestor v ofleaf T that has Weiner linkwith character a.

v

aaTWeiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFollow the Weiner link
labeled a from v.

v

aaTWeiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFollow the Weiner link
labeled a from v.

v

aaTWeiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFollow the Weiner link
labeled a from v.

v

aaTWeiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaFollow the Weiner link
labeled a from v.

v

aaTWeiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaSplit the incoming edgeat string depth |av| = |v|+1.
v

aaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaaaaav

Split the incoming edge
at string depth |av| = |v|+1.
v

aaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aRedirect soft Weiner links.

aaaaaavv

aaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aRedirect soft Weiner links.

aaavaav

aaaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaav

Insert new leaf for aT
as a child of av.
aav

aaaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
aaaav

Insert new leaf for aT
as a child of av.
aav

aaaTaT

Weiner’s Algorithm (Blumer et al. version)
Update string T to aT.
BEFOREAFTERaaaaaaaaav

avv

aaaaa

TaaTaT

Weiner’s Algorithm (Blumer et al. version)ri : # of redirected
Weiner links
at ith iteration.

Online single string: ∑𝑛𝑛𝑖𝑖=1 𝑟𝑟𝑖𝑖 ∈ 𝑂𝑂(𝑛𝑛)[Blumer et al. 1985]
Fully-online multiple strings : ∑𝑛𝑛𝑖𝑖=1 𝑟𝑟𝑖𝑖 ∈ Ω(𝑛𝑛1.5 ) [Takagi et al. 2020]

Weiner’s Algorithm (Blumer et al. version)ri : # of redirected
Weiner links
at ith iteration.

To avoid the Ω(n1.5) work, we reduce the sub-problem of
redirecting Weiner links to the ordered split-insert-find problem.

Ordered Split-Insert-Find
The ordered split-insert-find problem is to maintaina data structure on ordered sets which supports the following
operations and queries efficiently:• Make-set, which creates a new list that consists only of asingle element;• Split, which splits a given set into two disjoint sets, so thatone set contains only smaller elements than the other set;
• Insert, which inserts a new single element to a given set;
• Find, which answers the name of the set that a givenelement belongs to.

Reduction to Ordered Split-Insert-Find
Maintain the set of string depths of origin nodes of Weiner links

s1s2
s3
s4

s5
s6{s1, s2, s3, s4, s5, s6}

Reduction to Ordered Split-Insert-Find
Maintain the set of string depths of origin nodes of Weiner links

s1s1

s2

{s1, s2, s3}

s2s3s3s4s4

s5s5s6s6{s1, s2, s3, s4, s5, s6}{s4, s5, s6}

Reduction to Ordered Split-Insert-Find
BEFOREAFTERbbbbccbavccbav is the parent of new leaf aT

Reduction to Ordered Split-Insert-Find
BEFOREAFTERbc

New node av copies
out-going Weinerlinks from its child.

bbbbcbavcccbav is the parent of new leaf aT

Reduction to Ordered Split-Insert-Find
BEFOREAFTERbbcbbcbbavcccb
Insert |av|Insert |av|

av is the parent of new leaf aT

Ordered Split-Insert-Find by AVL-trees
For each suffix tree node u, we maintain an AVL tree such thateach AVL tree node stores the string depth of the origin node of
an in-coming Weiner link.
Works on thepointer machine.

s1
s2
s3

AVL tree for node us4s5u

s6

Ordered Split-Insert-Find by AVL-trees
Now, each Weiner link to a suffix tree node u points tothe corresponding node in the AVL tree for node u.
The root of this AVL tree is connected to suffix tree node u.
as1aaaAVL tree for node us2s3

aau

as4s5s6TOrdered Split-Insert-Find by AVL-trees
An AVL tree of d elements supports operations
Make-set, Split, Inert, and Find in O(log d) time each.
 O(log d)-time maintenance of Weiner links.
BEFOREAFTERaAVL treefor node avs2s1s3av

Tus5s4 s6s2s3aaaT

s1aaas4s5a s6

AVL tree for node uTSplitting an AVL-tree Let X be an AVL tree for the set {s1, ..., sd} of integers.
 Given an element sj in the set, we split the AVL tree X into

two AVL trees, X1 for {s1, ..., sj} and X2 for {sj+1, ..., sd}.

 This split operation can be done in O(log d) time

(next slide).

X2X
X1

Splitting an AVL-tree
 Consider the search path for sj in the AVL tree X．
 By splitting X with this path, we obtain- green nodes and subtrees containing elements at most sj- orange nodes and subtrees containing elements larger than sj
 Using monotonicity, we can merge each of them in O(log d) time.

Xsj

Main Results
Theorem 1
There is a pointer-machine algorithm which builds thesuffix tree of right-to-left fully-online multiple strings inO(n (log σ + log d)) time and O(n) space.
Each suffix-tree edge traversal takes O(log σ) time.
Theorem 2
There is a pointer-machine algorithm which builds theDAWG of left-to-right fully-online multiple strings inO(n (log σ + log d)) time and O(n) space.
Each DAWG-edge traversal takes O(log σ + log d) time.
n : total string length , σ : alphabet size, d : max. # in-coming Weiner links

Conclusions and Open Question
We proposed pointer-machine algorithms for fully-online
construction of suffix trees and DAWGs on multiple strings
running in O(n (log σ + log d)) time and O(n) space.
We have not found an instance where the n log d term in
our time complexity becomes Θ(n log n) or ω(n).
We have only found a bad instance which requires
sub-linear Ω 𝑛𝑛 log 𝑛𝑛 work to maintain the AVL trees.

Would it be possible to construct suffix trees / DAWGs forfully-online multiple strings in O(n log σ) time on thepointer machine?