TCS -TR-A-10-43

TCS Technical Report

Faster Bit-Parallel Algorithms for Unordered
Pseudo-Tree Matching and Tree Homeomorphism

byYusaku Kaneta and Hiroki Arimura

Division of Computer Science
Report Series A
May 7, 2010

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

arim@ist.hokudai.ac.jp

Phone:
Fax:+81-011-706-7680+81-011-706-7680

Faster Bit-Parallel Algorithms for Unordered
Pseudo-Tree Matching and Tree Homeomorphism
Yusaku Kaneta and Hiroki Arimura
Hokkaido University, N14, W9, Sapporo 060-0814, Japan{y-kaneta,arim}@ist.hokudai.ac.jp

Abstract. In this paper, we consider the unordered pseudo-tree matching problem, which
is a problem of, given two unordered labeled trees P and T , ﬁnding all occurrences of P in
T via such many-one embeddings that preserve node labels and parent-child relationship.
This problem is closely related to tree pattern matching problem for XPath queries withchild axis only. If m > w , we present an eﬃcient algorithm that solves the problem inO(nm log w/w) time using O(hm/w + m log w/w) space and O(m log w) preprocessing ona unit-cost arithmetic RAM model with addition, where m is the number of nodes in P ,n is the number of nodes in T , h is the height of T , and w is the word length. We also
discuss a modiﬁcation of our algorithm for the unordered tree homeomorphism problem,
which corresponds to a tree pattern matching problem for XPath queries with descendant
axis only.

1

Introduction

Tree matching is a fundamental problem in computer science, and it has a wide range
of applications in XML/Web database, schema validation, information extraction,
document analysis, image processing, and semi-structured data processing. In particular, tree matching and tree inclusion problems have attracted much attention
and have been extensively studied [2, 6, 7, 12]. In this paper, we study non-standard
version of the unordered tree matching and inclusion problems, called the unorderedpseudo-tree matching problem (UPTM) [14] and the unordered tree homeomorphism
problem (UTH) [4], respectively, where embedding mappings can be many-one.
As main results, we present an eﬃcient algorithm that solves UPTM problem
with the following complexities (Theorem 1):– O(nm log w/w) time using O(hm/w + m log w/w) space and O(m log w) preprocessing if m > w. (the large pattern case)– O(n log m) time using O(h+log m) space and O(m log m) preprocessing if m ≤ w.
(the small pattern case)where m and n are the sizes of pattern tree P and text tree T , h is the height of T ,and w = Θ(log n) is the word length of RAM. We also show that UTH problem issolvable in the same time and space complexities as above (Theorem 2).
A key of our algorithm is a data structure for the small pattern case (m ≥ w)
based on bit-parallel computation of set operations, including tree aggregation thatchecks the branching of internal nodes. Developing bit-assignment technique basedon separator trees, we improve the time complexity of the tree aggregation from
O(m) time and space to O(log m) time and space . Combining this result to dynamic
programming tree matching algorithms and a module decomposition technique of[8], we have claimed results for both UPTM and UTH.

2

Yusaku Kaneta and Hiroki Arimura

For the UPTM, our O(nm log w/w) time and O(hm log w/w) space algorithm
improves the complexity of the previous O(n·r·leaves(P )depth(P )/w) = O(nm3 /w)
time and O(n · leaves(P )depth(P )/w) = O(nm2 /w) space algorithm1 by Yamamoto
and Takenouchi [14] in the worst case. For the UTH, our algorithm is one of theﬁrst bit-parallel algorithm for the problem and slightly faster than the previousO(nm·depth(P )) time and O(depth(T )·branch(T )) space algorithm1 by Gotz, Koch,and Martens [4]. These results for UPTM and UTH correspond to evaluation offragments of Core XPath queries consisting with child axis only and with descendant
axis only [4], respectively.
Tree matching problems with many-one embeddings have been studied in thearea of FO and MSO logics over combinatorial structures such as strings, trees,and graphs as well as in database and Web systems [4]. These problems have lessconstraints than the other tree matching problems, but this does not necessarilymean that many-one matching problems are easiest among them. Hence, we hopethat these result becomes steps towards development of eﬃcient query mechanism
for such data intensive applications.
Organization of this paper is as follows. Section 2 prepares deﬁnitions and notations. Section 3 shows a fast bit-parallel algorithm for UPTM. Section 4 gives anextension to UTH. In Section 5, we conclude.

2

Preliminaries

In this section, we give basic deﬁnitions and notation on our unordered tree matchingproblems according to [4, 6, 14]. For a set S, we denote by |S| the cardinality of S. Let
N+ = {1, 2, . . .}. We deﬁne an interval from i to j by [i..j] = {i, i + 1, . . . , j} ⊆ N+ ,where i ≤ j. We deﬁne the smallest interval including set S ⊆ N+ by Int(S) =[min S, max S] ⊆ N+ . For an array A = A[1] · · · A[n] and i ≤ j, we deﬁne A[i..j] =A[i] · · · A[j]. For a binary relation R ⊆ A2 on a set A, we denote by R+ ⊆ A2 thetransitive closure of R.

2.1

Unordered trees

Let Σ = {a, b, a1 , a2 , . . .} be a ﬁnite alphabet of labels. In this paper, we will mainly
consider unordered trees, which are the labeled, rooted trees, where the ordering
among their siblings is irrelevant.
Let P be an unordered tree of m nodes whose labels are drawn from Σ. We
denote by V (P ) the node set, by E(P ) the edge set, and by root(P ) the root of P .
For each node x, labelP (x) ∈ Σ denotes the label of x in P and P (x) denotes thesubtree of P rooted at x.
If (x, y) ∈ E(P ) then we say that x is a parent of y and y is a child of x. If there
exists some downward path from x to y, i.e., (x, y) ∈ E(P )∗ , then we say that x isan ancestor of y and y is a descendant of x and write x ≼ y. If x ≼ y and x ̸= ythen we say that x is a proper ancestor of y and y is a proper descendant of x. If
both of x ̸≼ y and y ̸≼ x hold then x and y are incomparable each other and write
1

In the results, leaves(P ), depth(P ), and branch(P ) is the number of leaves, the maximum depth, andthe maximum branching in a tree P . The parameter r = O(m) is the maximum number of the samelabel on paths in P .

Faster Bit-Parallel Algorithms for Unordered Tree Matching Problems

3x♯y. For nodes x and y in P , if x♯y and x precedes y in the preorder travesal of P ,then we say that x precedes y in P (or, x is to the left of y) and write x  y. If x♯ythen either x  y or y  x holds.
For unordered tree P , we denote by |P | and by height(P ) the number of nodes
in P and the height of P . We denote the sets of all leaves and all internal nodes
in P , respectively, by internal(P ) and leaves(P ). Clearly, V (P ) = internal(P ) ⊎leaves(P ). Let x be any node in P . The arity of x, denote by α(x) ≥ 0, is thenumber of children of x. For every 1 ≤ i ≤ α(x), we denote the i-th child of node x
by x[i], and the list of the children of x by children(x) = x[1] · · · x[α(x)].

2.2Unordered tree matching problem

Let P = P [1..m] be an unordered tree of size m, called a pattern tree, and T =P [1..n] be an unordered tree of size n, called a text tree. In this subsection, we
introduce the unordered pseudo-tree matching and unordered tree homeomorphism
problems. For other variations of tree matching problems as in [2, 4, 6, 7, 12, 14],
please consult Appendix A.1.
Definition 1 (conditions for tree matching and inclusion). For any (possibly
many-one) mapping ϕ : V (P ) → V (T ), we deﬁne the following conditions:(E0) ϕ preserves node labels. That is, for every node x ∈ V (P ), labelP (x) = labelT (ϕ(x))
holds.
(E1) ϕ preserves the parent-child relationship. That is, for every node x, y ∈ V (P ),(x, y) ∈ EP ⇒ (ϕ(x), ϕ(y)) ∈ ET holds.
(E1’) ϕ preserves the ancestor-descendant relationship. That is, for every node x, y ∈V (P ), (x, y) ∈ EP ⇒ ϕ(x) ≺ ϕ(y) holds.
Let F be a class of mappings. Then, a pattern P maps to a node v ∈ V (T )in T w.r.t. class F if ϕ(root(P )) = v for some ϕ ∈ F. Then, the node v is called
an occurrence of P in T w.r.t. class F. Then, the tree pattern matching problem
w.r.t. F (F-matching problem) is the problem of, given a pattern tree P and a text
tree T , ﬁnding all occurrences of P in T w.r.t. class F.
An embedding from P to T is a possibly many-one mapping ϕ : V (P ) → V (T )with (E0). A unordered pseudo-tree matching (UPTM) [14] is a many-one version ofunordered tree matching, i.e., an embedding ϕ with (E0) and (E1). A unordered tree
homeomorphism (UTH) [4] is a many-one version of unordered tree inclusion, i.e.,
an embedding ϕ with (E0) and (E1’). We denote by U P T M (P, T ) and U T H(P, T )the sets of all pseudo-tree matching and all tree homeomorphism from P to T . The
unordered pseudo-tree matching problem (UPTM) and the unordered tree homeomorphism problem (UTH) are tree matching problem related to the above classes ofmappings.

3

Faster Bit-parallel Algorithm for Unordered Pseudo
Tree Matching

In this section, present eﬃcient algorithm BP-MatchUPTM based on bit-parallel
pattern matching method for the pseudo-tree matching problem. Let P = P [1..m]be a pattern tree of size m and T = T [1..n] be a text tree of size n.

4Yusaku Kaneta and Hiroki Arimura

algorithm MatchUPTM(P [1..m]: a pattern tree, T [1..n]: a text tree):Global Variables: P and T ;Output: all occurrences of P in T w.r.t. unordered pseudo-tree matching (UPTM);
1: VisitUPTM(root(T ));procedure VisitUPTM(v: text node)
Return Value: R = EmbP,T (v);
2: S ← Constant(∅); {See Deﬁnition 2}
3: for i = 1, . . . α(v) do
4:
S ← Union(S, VisitUPTM(v[i]));5: R ← Constant([1..m]);
6: R ← LabelMatchP (R, labelT (v)); {See Deﬁnition 2}
7: R ← TreeAggrP (R, S); {See Deﬁnition 2}
8: if Member(R, root(P )) then {See Deﬁnition 2}
9:output “A match is found at a node v.”;
10: return R;
Fig. 1. An algorithm for the unordered pseudo-tree matching problem.

3.1

Decomposition formula and a bottom-up algorithm

In Fig. 1, we show an algorithm MatchUPTM for Unordered Pseudo Tree Matching.
Our matching algorithm computes, for every text node v in T , the set EmbP,T (v) ofintegers in V (P ) = [1..m], called the embedding set, deﬁned by:
EmbP,T (v) = { x ∈ [1..m] | (∃ϕ) ϕ ∈ U P T M (P (x), T ) ∧ ϕ(x) = v }.

(1)

Clearly, For every x ∈ [1..m], x ∈ EmbP,T (v) if and only if the corresponding subtree
P (x) has an occurrence at the current node v. By deﬁnition, we see that P matches
T at node v iﬀ root(P ) ∈ Emb(P, v). Now, we have the next lemma, which is crucial
to the correctness of our algorithm.
Lemma 1 (decomposition formula for UPTM). For every x ∈ V (P ) and v ∈V (T ), x ∈ EmbP,T (v) if and only if(i) labelP (x) = label∪ T (v), and(ii) children(x) ⊆ 1≤j≤α(v) EmbP,T (v[j]).
From Lemma 1 above, we show in Fig. 1 a bottom-up procedure VisitUPTM tocompute EmbP,T (v) by using the post-order traversal of T . To describe the procedure
VisitUPTM, we need the following operators.
Definition 2 (set manipulation operators). We deﬁne operators Constant, Union,
Member, LabelMatch (label matching), and TreeAggr (tree aggregation) on subsetsof [1..m] as follows, where R, S ⊆ [1..m], x ∈ [1..m], and α ∈ Σ:
– Constant(S) ≡ S. This operation returns the set S itself.
– UnionP (S, R) ≡ S ∪ R. this returns the set-union of R and S ⊆ [1..m].
– MemberP (R, x) ≡ S ∪R. Given a set R and an element x, this operation returns“yes” if x ∈ R and “no” otherwise.
– LabelMatchP (R, α) ≡ { k ∈ R | labelP (k) = α }. Given any set R and label α,this operation returns the set elements in R satisfying (i) of Lemma 1.
– TreeAggrP (R, S) ≡ { k ∈ R | childrenP (k) ⊆ S }. Given any sets R, S, thisoperation returns the set of elements in R satisfying (ii) of Lemma 1.

Faster Bit-Parallel Algorithms for Unordered Tree Matching Problems
original pattern tree P
in multi-ary form

transformed pattern tree P'
in binary form

9

9

4

5

1
1

2

3

6

first cut-edges
cut-edges

4

8

5

11
10

5

8

7
2

3

6

7

Fig. 2. An original pattern tree P and its binarization P ′ , where white and shadowed circles indicate
original (real) nodes and dummy (virtual) nodes, respectively. The number in each circle indicates thenode id.

In the procedure VisitUPTM, we use the last two operators LabelMatch and
TreeAggr to check (i) and (ii) of Lemma 1. Later, the above set operations will
be implemented in bit-parallel manner in Sec. 3.2.
By representing sets R and S ⊆ [1..m] in lists of integers, it is easy to see thatthese operators can be implemented to run in O(m) time and space. Then, we havethe following lemma.
Lemma 2. For the unordered pseudo-tree matching problem, For every pattern tree
P and a text tree T , the algorithm MatchUPTM in Fig. 1 correctly finds all occurrences of P in T . Moreover, the algorithm can be implemented to run in O(mn) timeand O(hm) additional space, where m is the size of P , n and h are the size and theheight of T , respectively.
The algorithm MatchUPTM can run in streaming setting using a stack of lengthO(hm), where T is given as an input stream consisting of a sequence of balanced
open and close parentheses on alphabet Σ ∪ { ā | a ∈ Σ } as in XML databases [4,10, 11].

3.2

Bit-parallel implementation: overview

In the following subsections, we give the bit-parallel version of the algorithm MatchUPTM,
called BP-MatchUPTM, that runs in in O(nm log w/w) time and O(hm/w+m log w/w)
space, where m is the size of pattern tree P , n and h are the size and the height oftext tree T , and w = Θ(log n) is the word length of underlying computer. Let us ﬁx
a pattern P = P [1..m] of size m on a ﬁnite alphabet Σ. In what follows, we assume
that |Σ| = O(1).
In the bit-parallel implementation of MatchUPTM, we introduce a data structure
A for representing a subset S of the universe [1..m] that eﬃciently supports thecollection of set manipulation operators in Deﬁnition 2 in Sec. 3.1.
In A, we represent any subsets of V (P ) by bitmasks X ∈ {0, 1}m with length m
as m-bit integers from 0 to 2m − 1. To do this, we need an assignment Bit : V (P ) →[1..m] of the unique bit-position Bit(x) in the interval [1..m] to each node x in P .
Basic set operations. Once the assignment Bit is given, for any node set S ⊆V (P ), we extend this Bit by BIT (S) = { Bit(x) | x ∈ S } ⊆ [1..m]. At this moment,
we leave Bit undeﬁned and the appropriate deﬁnition for Bit will be given later in
the next subsection. For any subset X ⊆ [1..m], we deﬁne N U M (X) ∈ {0, 1}m to be6

Yusaku Kaneta and Hiroki Arimura
branching components of original pattern P

C8= {6,7,8} 8 &67childrentree aggregation operations
level k6

x parent
9 &C9= {4,5,8,9}

7

4

5

8

x[1]

x[2]

x[3]

x[i1] x[i2]
8
&

4

5

x[i3]

x

8

9
&

Fig. 3. Branching components of a pattern tree P and the corresponding tree aggregation operation in
bit-parallel computation.

the bitmask for X. Among the set operators in Deﬁnition 2, the following operators
are easy to implement.
Lemma 3. Let S, R ⊆ V (P ) be any sets, and X, Y ∈ {0.1}m be the corresponding
bitmasks, respectively. Then, the following codes correctly implements the operators.
Moreover, all operations are executed in O(1) time if m ≤ w.
– Preprocess: Constant(S) ≡ N U M (BIT (S));– Runtime: UnionP (X, Y ) ≡ (X | Y );– Runtime: MemberP (X, x) ≡ if (X ∩ BIT ({x})) > 0 then 1 else 0;
Label matching operation. The label matching operation can be implemented using a set of character masks as in SHIFT-AND method for exact match [1,13, 9] or Move operation for regular expression match [3]Lemma 4. The operator LabelMatch can be correctly implemented by the following
codes, where { LAB[α] ∈ {0, 1}m | α ∈ Σ } is a set of bitmasks for P . Moreover theoperation can be executed in O(1) time if m ≤ w.
– Preprocess: For each α ∈ Σ, LAB[α] = |x∈V (P ),labelP (x)=α N U M (Bit(x));– Runtime: LabelMatchP (X, α) ≡ (X & LAB[α]);Tree aggregation operation. Remaining task is to show how to eﬃciently
implement TreeAggr operation in bit-parallel computation. For each node x in P , wedeﬁne the branching component for x in P by the connected component Cx = {x} ∪children(x) of P consisting of parent x and its children. If no confusion arises, we
identify Cx and the induced depth-one subtree P (Cx ) rooted at x, called a branchingtree. We denote by CP = {Cx | x ∈ internal(P )} the set of all branching componentsof P .
For example, pattern P of Fig. 2 has three branching components C4 = {1, 2, 3, 4},
C8 = {4, 5, 8, 9}, and C9 = {6, 7, 8}. The upper half of Fig. 3 shows C8 and C9 with
their branching trees.
Then, the tree aggregation operation means gathering the values of children ofx and then copying their conjunction to the value of parent x (See Fig. 3). We wantto compute tree aggregation simultaneously for all internal node x in P . To do this,Faster Bit-Parallel Algorithms for Unordered Tree Matching Problems

leaf number

1

2

3

4

5

6

7

8

9

10 11

pattern node

6

7

8

5

11

3

2

10

1

4

9

8

5

4

9

level

0
1
2

3
6

7

2

1

7

4

8

Fig. 4. Tree aggregation on interval [1..m] based on a monotone bit-assignment Bit.

we require bit assignment Bit : V (P ) → [1..m] and a decomposition of C with someproperties described below.
First, to implement the tree aggregation operation in correct and eﬃcient way,
we require the assignment Bit to have the following properties:
Definition 3 (monotone bit assignment). A bit assignment mapping Bit :V (P ) → [1..m] is said to be monotone w.r.t. the ancestor relation ≼ for P if for any
x, y ∈ V (P ), (x ≻ y) ⇒ (Bit(x) < Bit(y)) holds.
See Fig. 4, for an example of monotone bit-assignment. Next, we give a decomposition of CP as follows. For any component Cx ∈ CP , we denote by Ix =Int(BIT (Cx )) the smallest interval in [1..m] containing all bit positions of Cx . Then,
two components Cx and Cy (x ̸= y) overlap if Ix ∩ Iy ̸= ∅. A subset D ⊆ CP is said
to be overlap-free if there are no pairs of components in D that overlap each other.
Definition 4 (overlap-free decomposition). A partition CP = C[1] + · · · + C[K]for some k ≥ 1 is said to be an overlap-free decomposition of CP w.r.t. Bit if forevery k = 1, . . . , K, the k-th subset C[k] is overlap-free w.r.t. Bit. Then, K is called
the height and C[k] is called the k-th layer of the partition.
Suppose that there exists some monotone bit assignment Bit and some overlapfree decomposition CP = C[1] + · · · + C[K] of CP for some Bit. Then, tree aggregation
is implemented in bit-parallel way as follows.
Definition 5 (Preprocess). We ﬁrst precompute the following bitmasks:– LEAF = |x∈leaves(P ) N U M (BIT ({x})).
– For every level k = 1, . . . , K, and for each Cx in C[k], we deﬁne• DST [k][x] = N U M (BIT ({x}))). The position of parent x.
• SRC[k][x] = N U M (BIT (children(x))). The positions of children(x).
• IN T [k][x] = N U M (Int(BIT (Cx ))). The interval for Cx .
• SEED[k][x] = N U M (min BIT (Cx )). The “seed” position.
– For every level k = 1, . . . , K, and for each M ask ∈ {DST, SRC, IN T, SEED},• M ask[k] = |Cx ∈C[k] M ask[k][x].
Lemma 5 (Runtime). Suppose that CP = C[1] + · · · + C[K] of CP is an overlapfree decomposition with height K ≥ 1 for a monotone bit assignment Bit w.r.t. ≼.
Then, the code in Fig. 5 correctly implements the tree aggregation operator for thecomponent Cx . Moreover, this procedure runs in O(K) time if m ≤ w.
Therefore, the remaining thing is how to ﬁnd a good overlap-free decomposition
CP with small height as well as monotone bit-assignment Bit. We discuss this issue
in the next subsection.

8

Yusaku Kaneta and Hiroki Arimura

procedure TreeAggrP (X, Y ):1: Z ← Constant(∅);
2: For every level k = 1, . . . , K do:
3:
BLK ← (Y & SRC[k]) | (IN T [k] & (∼ (SRC[k] | DST [k])));
4:Z ← Z | ((BLK + SEED[k]) & DST [k]);5: Z ← X & (Z | LEAF );6: return Z;
Fig. 5. An algorithm for implementing TreeAggr operator

3.3

Construction of a monotone bit-assignment and an overlapfree decomposition based on separator trees

In this subsection, we show how to ﬁnd both a monotone bit-assignment Bit andan overlap-free decomposition CP with height O(log m). For this purpose, we use adata structure called a separator tree.
Binarization of P . Let P be a pattern tree of m nodes. We note that P
is a multi-ary tree whose internal node may have arity α(x) > 2. First, before
constructing separator tree composition, we apply a standard transformation, calledbinarization to P for obtaining a binary version P ′ of P . The binarization transforms
each branching component Cx = {x} ∪ {x[1], · · · , x[α]} with the root x and α(x)children into a new component Cx′ a binary subtree with the same root and the same
number of children by inserting α(x) − 2 dummy internal nodes of out-degree two.
In general, the resulting binary tree P ′ has size at most 2m. In what follows, letm′ = O(m) be the size of P ′ .
Fig. 2 shows an example of the binarization P ′ of the original pattern P , where
the component C4 = {1, 2, 3, 4} with root 4 is transformed into C4′ = {1, 2, 3, 4, 10}with the same root 4.
Construction of a separator tree for P . Secondly, we build a separator tree
M from a binarization P ′ of pattern tree. A separator tree is a binary tree obtained
from P ′ by iteratively removing edges in E(P ′ ). The following well-known lemma is
suﬃcient for our purpose:
Lemma 6 (Jordan [5]). Let S be a binary tree. Then, there exists a node in S
such that |S(v)| ≤ (2/3)|S| and |S(v̄)| ≤ (2/3)|S|, where S(v) is the subtree of S
rooted at v and S(v̄) is the tree obtained by pruning S(v) from S.
Suppose that each node w of M has the ﬁelds Uw for a subset of V (P ′ ), andew for a cut-edge. Applying the above theorem recursively, we construct a separator
tree M from P ′ as follows.
– We start with a new node as the root of M. We associate V (P ′ ) to the root by
setting Uroot(M) = V (P ′ ). We visit root(M), and repeat the following process.
– Suppose that |Uw | = 1. Then, the associated node set Uw is a singleton {x}, andthe current node w is a leaf. We stop the process.
– Otherwise, |Uw | > 1. Then, we ﬁnd an edge e = (x, y) ∈ E(P ′ ) according toLemma 6 so that removal of e splits the associated component Uw into two
subcomponents Uw1 and Uw0 of almost equal sizes no more than (2/3)|Uw |, where
Uw1 is the subcomponent containing root(P ′ ) and Uw0 is the other subcomponent.
Record the cut-edge e for w as ew . Create the left and the right children, wL andFaster Bit-Parallel Algorithms for Unordered Tree Matching Problems

994e11 [1-11]

level 0

11
5

8

4
1

level 16e6 [6,7,8]
e7 [7,8]

6level 3e5 [5-11]
5

7

8

1

2

3

an internal nodecorresponding toa first cut-edge e(also to a branch tree)

ei

leaf
numbers

e10 [1,4,9,10]

10
2

3

7

level 2ei

e8 [5-8,11]

8

0

4

e3 [2,3,10]
e2 [2,10]

3
2

10

6

7

other internal nodecorresponding to a
cut-edge e

x

4

5

e1 [1,4,9]e4 [4,9]

1

8

4

9

9

10

a leaf node corresponding
to a pattern node x

Fig. 6. A separator tree M for the binarization P ′ of a pattern tree. Circles and squares indicate internal
nodes and leaf nodes in M, respectively. At each node w, the associated set of numbers in a pair of brackets
indicates the connected component associated to w. Each edge (x, y) is denoted as ey indexed by its lower
end point y.

wR , and associate the component Uw1 to wR and Uw0 to wL . Then, recursively visit
both of wL and wR .
Lemma 6 ensures that the height of M is O(log m) and the construction requires O(m log m) time. Furthermore, we can observe that (1) there exists a one-one
correspondence between internal(M) and E(P ′ ), and (2) there exists a one-one
correspondence between leaves(M) and V (P ′ ).
Now, we compute a bit assignment Bit : V (P ′ ) → [1..m] as follows. We orderleaves(M) from left to right. Then, we number all leaves in leaves(M), which are
original (real) nodes in P , from left to right consecutively from 1 to m (not m′ ). We
just skip and unnumber dummy (virtual) nodes included in binarization. Then, wedeﬁne bit-assignment Bit : V (P ) → [1..m] such that for each node x in P , if x is
the i-th leaf in this listing over leaves(M), then Bit(x) = i. For the proof of thenext lemma, see Appendix A.2.
Lemma 7. The bit assignment Bit constructed above from M is monotone w.r.t. theancestor relation ≼ for P .
By using Bit based on leaf numbering of M, we associate an interval Iw to eachnode w in M by Iw = Int(BIT (Uw )). Then, we give a technical lemma.
Lemma 8. For any nodes u, w in M, the following properties hold:(1) BIT (Uw ) ⊆ Iw .
(2) If u ≽ w then Iu ⊆ Iw .
(3) If u♯w then Iu ∩ Iw = ∅.
Finally, we construct a overlap-free decomposition for CP as follows. We traverse
the separator tree M from the root to leaves top-down. Initially, we visit root and
Uroot contains the whole CP . Assume that we are going down and visiting a node w

10

Yusaku Kaneta and Hiroki Arimura

in M. Let Cx ∈ CP be the unique component in CP that contains ew in the induced
tree P (Cx ). Then, there are two cases. If this happens at the ﬁrst time with Cx ,that is, ew is the first cut-edge for Cx on the path from the root to w, then wemark the current node w and associate to w the Cx by Comp(w) = Cx . Otherwise,
this is at least second time cut or so. Then, we skip w and continue the traversal
for descendants. After the traversal, we perform breadth-ﬁrst search for level k = 0
to K = depth(M). Then, we construct a decomposition CP = C[1] + · · · + C[K]such that C[k] = { Cx | Cx = Comp(w), w is a marked internal node in M } for eachk = 0, . . . , K. For the proof of the next lemma, see Appendix A.3.
Lemma 9. An overlap-free decomposition CP = C[1] + · · · + C[K] of CP w.r.t. Bit
can be computed by the above procedure in O(m log m) time and O(log m) space.

3.4

Complexity analysis

Combining the algorithm MatchUPTM of Fig. 1 in Sec. 3.1 and the bit-parallel
implementation of the set manipulation operations in Sec. 3.2, and results in Sec. 3.3,
we now have a modiﬁed version of the algorithm, called BP-MatchUPTM for the
UPTM problem.
Lemma 10. The operation TreeAggrP can be implemented to run O(log m) timeusing O(m log m) preprocessing and O(log m) space if m ≤ w.
Proof. The claim follows from Lemma 7, Lemma 9, and Lemma 5.

⊓⊔

By applying the module decomposition technique of Myers [8] and Bille [3], wehave the main theorem of this paper below:
Theorem 1. The algorithm BP-UPTreeMatch solves the unordered pseudo-tree matching problem with the following complexities:– In the large pattern case (m > w): O(nm log w/w) time using O(hm/w+m log w/w)
space and O(m log w) preprocessing.
– In the small pattern case (m ≤ w): O(n log m) time using O(h + log m) spaceand O(m log m) preprocessing.
where m and n are the sizes of pattern tree and text tree, h is the height of T , andw = Θ(log n) is the length of computer word.

4

Extension for unordered tree homeomorphism

In this section, we give a modiﬁed algorithm for the unordered tree homeomorphism
problem (UTH). Let v be any node in T . Then, the set Desc-EmbP,T (v), called thedescendant embedding set and the auxiliary set Sub-EmbP,T (v) are deﬁned by:
Desc-EmbP,T (v) = { x ∈ [1..m] | (∃ϕ ∈ U T H(P (x), T ) ϕ(x) = v }.
Sub-Emb

P,T(v) = { x ∈ [1..m] | (∃ϕ ∈ U T H(P (x), T )(∃w ≽ v) ϕ(x) = w }.

Lemma 11. For any P and T , we have the following properties:(2)

Faster Bit-Parallel Algorithms for Unordered Tree Matching Problems

11P,T(1) For every x ∈ V (P ) and v ∈ V (T ), x ∈ Desc-Emb(v) if and only if (i)∪labelP (x) = labelT (v), and (ii) children(x) ⊆ 1≤j≤α(v) Sub-EmbP,T (v[j]).
∪(2) For any v in T , Sub-EmbP,T (v) = Desc-EmbP,T (v) ∪ 1≤j≤α(v) Sub-EmbP,T (v).

From the above decomposition lemma, we can develop a bit-parallel algorithm
equipped with the bit-parallel implementation of operators including TreeAggr asshown in Sec. 3. For details, please consult Appendix A.5.
Theorem 2 (complexity of the unordered tree homeomorphism problem).
A modified version of algorithm, BP-MatchUTH, solves the unordered tree homeomorphism problem (UTH) with the following complexities:– In the large pattern case (m > w): O(nm log w/w) time using O(hm/w+m log w/w)
additional space and O(m log w) preprocessing.
– In the small pattern case (m ≤ w): O(n log m) time using O(h+log m) additional
space and O(m log m) preprocessing.
where m and n are the sizes of pattern tree and text tree, and w = Θ(log n) is thelength of computer word.

5

Conclusion

In this paper, we consider the unordered pseudo-tree matching problem and the unordered tree homeomorphism problem. As results, we present eﬃcient algorithms forboth problems that runs in O(nm log w/w) time using O(hm/w + m log w/w) spaceand O(m log w) preprocessing with m > w on a unit-cost arithmetic RAM modelwith addition. As future work, application to tree pattern matching for practicalsubclasses of XPath and XQuery queries are interesting problems.

References
1. R. Baeza-Yates and G. H. Gonnet, A new approach to text searching, CACM, 35(10), 74–82, 1992.
2. P. Bille, I. L. Gortz, The tree inclusion problem: in optimal space and faster, In Proc. ICALP’05,
66–77, 2005.
3. P. Bille, New algorithms for regular expression matching, In Proc. ICALP’06, 643–654, 2006.
4. M. Gotz, C. Koch, W. Martens, Eﬃcient algorithms for descendant-only tree pattern queries, Inf. Syst.,
34(7), 602–623, 2009.
5. C. Jordan, Sur les assemblages de lignes, Journal für reine und angewandte Mathematik, 70, 185–190,
1869.
6. P. Kilpelainen, Tree Matching Problems with Applications to Structured Text Databases, Ph.D thesis,
Report A-1992-6, DCS, University of Helsinki, 1992.
7. P. Kilpelainen, H. Mannila, Ordered and unordered tree inclusion, SIAM J. Computing, 24(2), 340-356,
1995.
8. E. W. Myers, A four-russian algorithm for regular expression pattern matching, JACM, 39(2), 430–448,
1992.
9. G. Navarro, and M. Raﬃnot, Flexible pattern matching in strings: practical on-line search algorithms
for texts and biological sequences, Cambridge, 2002.
10. H. Tsuji, A. Ishino, M. Takeda, A bit-parallel tree matching algorithm for patterns with horizontal
VLDC’s, In Proc. SPIRE 2005, 388–398, 2005.
11. W3C, Extensive Markup Language (XML) 1.0 (Second Edition), W3C Recommendation, 06 October
2000. http://www.w3.org/TR/REC-xml
12. G. Valiente, Constrained tree inclusion, Journal of Discrete Algorithms, 3(2/4), 431–447, 2005.
13. S. Wu, U. Manber, Fast text searching: allowing errors, CACM, 35(10), 83–91, 1992.
14. H. Yamamoto and D. Takenouchi, Bit-parallel tree pattern matching algorithms for unordered labeledtrees, In Proc. WADS’09, 554-565, 2009.

12

Yusaku Kaneta and Hiroki ArimuraA

Appendix

A.1

A taxonomy of tree matching problems

There are many variations of tree matching problems, as in [2, 4, 7, 12, 14] (See also
for survey [6]). Below, we summarize some of them. Let P = P [1..m] be an unordered
tree of size m, called a pattern tree, and T = P [1..n] be an unordered tree of size n,called a text tree.
Definition 6 (conditions for tree matching and inclusion). For any (possibly
many-one) mapping ϕ : V (P ) → V (T ), we deﬁne conditions (E0)–(E3) as follows:(E0) ϕ preserves node labels. That is, for every node x ∈ V (P ), labelP (x) = labelT (ϕ(x))
holds.
(E1) ϕ preserves the parent-child relationship. That is, for every node x, y ∈ V (P ),(x, y) ∈ EP ⇒ (ϕ(x), ϕ(y)) ∈ ET holds.
(E1’) ϕ preserves the ancestor-descendant relationship. That is, for every node x, y ∈V (P ), (x, y) ∈ EP ⇒ ϕ(x) ≺ ϕ(y) holds.
(E2) ϕ preserves the precedence relationship. That is, for every node x, y ∈ V (P ) with
x♯y, x  y ⇒ ϕ(x)  ϕ(y) holds.
(E3) ϕ is a one-one mapping. That is, for every node x, y ∈ V (P ), x ̸= y implies
ϕ(x) ̸= ϕ(y) holds.
Most variations of tree pattern matching problems are described in terms ofembeddings [2, 4, 7, 12, 14] as follows.
– A mapping ϕ is said to be an embedding from P to T if it satisﬁes condition (E0)above.
– An embedding ϕ is a tree matching if ϕ satisﬁes (E1), and a tree inclusion if ϕsatisﬁes (E1’) instead of (E1).
– ϕ is ordered if it satisﬁes (E2) and unordered otherwise.
– An embedding ϕ is one-one if ϕ satisﬁes (E3), and many-one otherwise. We often
omit the term one-one if it is clear from context.
By combination of the above conditions, we can describe a number of tree matching problems. For example, the ordered tree matching [7, 10] is a mapping with (E0),(E1), (E2), and (E3), and the ordered tree inclusion [2, 7] satisﬁes (E0), (E1’), (E2),and (E3). the unordered tree matching [7] is a mapping with (E0), (E1), and (E3),and the unordered tree inclusion [2, 7] satisﬁes (E0), (E1’), and (E3). Tree matchingproblems with many-one embeddings have been studied in the area of ﬁrst-orderand second-order logics over combinatorial structures such as strings, trees, cycles,
chains and graphs [4].
Definition 7 (unordered psuedo-tree matching [4]). A unordered pseudo-tree
matching from P to T is a possibly many-one, unordered, tree matching ϕ : V (P ) →V (T ), that is ϕ satisﬁes conditions (E0) and (E1). We denote by U P T M (P, T ) the
set of all pseudo-tree matching from P to T
Definition 8 (unordered tree homeomorphism). A unordered tree homeomorphism from P to T is a possibly many-one, unordered, tree inclusion ϕ : V (P ) →V (T ), that is ϕ satisﬁes conditions (E0) and (E1’). We denote by U T H(P, T ) the
set of all tree homeomorphism from P to T .

Faster Bit-Parallel Algorithms for Unordered Tree Matching Problems

13

We say that pattern P maps to a node v ∈ V (T ) in T w.r.t. U P T M (w.r.t. U T H,
resp.) if ϕ(root(P )) = v for some ϕ ∈ U P T M (P, T ) (ϕ ∈ U T H(P, T ), resp.). Then,the node v is called an occurrence of P in T .

A.2

Proof for Lemma 7

Lemma 7. The bit assignment Bit constructed above from M is monotone w.r.t. theancestor relation ≼ for P .
Proof. Suppose that x ≽ y and both of them are included in some component U in
M. Then, there exists an upward path π from x to y, and eventually, some edge in
π becomes a cut-edge at some node w in M. This split Uw into Uw0 and Uw1 suchthat x ∈ Uw0 and y ∈ Uw1 since the latter locates the upper part. We see that Uw0
precedes Uw1 in interval [1..m] by Bit. Thus, x ≽ y implies Bit(x) < Bit(y).
⊓
⊔

A.3

Proof for Lemma 9

Lemma 9. An overlap-free decomposition CP = C[1] + · · · + C[K] of CP w.r.t. Bit
can be computed by the above procedure in O(m log m) time and O(log m) space.
Proof. First, we can show that Cx = Comp(w) ⊆ Uw because initially any component Cx is included in Iroot = [1..m], and Cx is registered as Comp(w) whenever it issplitted at the ﬁrst time at some marked node w. Therefore, if Ix = Int(BIT (Cx ))and Iw = Int(BIT (Uw )), then we have Ix ⊆ Iw holds for every marked node w in
M. On the other hand, let Cx , Cx′ be any mutually distinct components associatedto some nodes w and w′ , respectively, in M. If both of Cx and Cy belong to C[k]for some k ≥ 0. then w and w′ also have the same depth k, and thus, w♯w′ holds.
From (3) of Lemma 8, it follows that Iu ∩ Iw . Hence, the result follows. The claimed
complexities are derived as follows. It is not hard to see that the time complexity
is O(m log m) time for constructing a separator tree M by recursive fasion using a
stack. For the space complexity, we use a stack of O(log m) depth to keep nodes of apath from the root to the current node, and also use O(log m) bitmasks for keeping
the necessary information. Therefore, the space complexity of O(log m) follows. ⊓⊔A.4

Proof for Theorem 1[Note: This section is under development. Hiroki Arimura, 2010/05/05]
Suppose a data structure A for set manipulation in Deﬁnition 2 with mask size
0 ≤ x ≤ w. In this paper, we assume that |Σ| = O(1) Below, we appreviate LabelMatch, TreeAggr, and Mask by LM, TA, and MK, respectively. For τ ∈ {LM, T A},
let Tτ (x), Sτ (x), and Pτ (x) be the time, space, and preprocessing of operation τ withmask of size x associated to A. Let SMK (x) be the space required to store mask ofsize x. Clearly, SMK (x) = ⌈m/w⌉ space in words.
General complexity. From the construction of the algorithm MatchUPTM in
Fig. 1 and Lemma 2, we have the next claim.
Lemma 12. The algorithm MatchUPTM can be implemented to run in the following
complexities:– T = O(n · {TLM (m) + TTA (m) + TOther (m)}) time,14

Yusaku Kaneta and Hiroki Arimura– S = O(h · SMK (m) + {SLM (m) + STA (m) + SOther (m)}) additional space, and– P = O(PLM (m) + PTA (m) + POther (m)) preprocessing,where m is the size of P , n and h are the size and the height of T , respectively.
The small pattern case. First, we consider the small pattern case such thatm ≤ w. By putting x = m and substituting Lemma 3, Lemma 4, and Lemma 5 forLemma 12, we have the following result.
Lemma 13. In the small pattern case (m ≤ w), the unordered pseudo-tree matchingproblem is solvable in– O(n log m) time using– O(h + log m) space and– O(m log m) preprocessing.
The large pattern case. In the large pattern case, we assume that m > w.
For the Constant, Union, Member operations, we have the following.
Lemma 14. In the large pattern case with m > w, we have the following.
Claim 1: The Constant, Union, Member operations can be implemented to run in– TOther (m) = O(⌈m/w⌉) time.
– SOther (m) = O(⌈m/w⌉) space.
– POther (m) = O(m) preprocessing.
Claim 2: The LabelMatch (LM) operation can be implemented to run in– TLM (m) = O(⌈m/w⌉) time.
– SLM (m) = O(|Σ| · ⌈m/w⌉) = O(⌈m/w⌉) space.
– PLM (m) = O(|Σ| · m) = O(m) prerocessing.
Claim 3: The TreeAggre (TA) operation can be implemented to run in– TTA (m) = O(⌈m/w⌉ log m) time.
– STA (m) = O(⌈m/w⌉ log m) space.
– PTA (m) = O(m log w) preprocessing.
Proof. We use the module decomposition technique in Myers [8]. By Jordan’s theorem [5] iteratively, we can split the original pattern tree P into h = O(m/w) small
subtrees of size at most w. Let P = {Q1 , . . . , Qh } be the set of resulting small subtrees, called components of P . For each component Q ∈ P, root(Q) corresponds
to a cut-edge (y, x) ∈ E(P ). For each component Q ∈ P, we assign a module MQ
to Q. Let parent(Q) = Qy be the component in P that contains y as its leaf andcalled the parent component of Q. Since the node x is missing in parent(Q), we
recover this by adding x to the module for parent(Q) so that every internal node in
MQ has both of left and the right child. For each node x in P , we call the positionof x as a parent the real position and the other as a child the dammy position in
the modules. Basically, we apply each operation Opr to each module Q separately.
Then, we copy the value of root(Q) at the child position to the real position of thenode in parent(Q) module by module. This takes at most h = O(⌈m/w⌉) time.

Faster Bit-Parallel Algorithms for Unordered Tree Matching Problems

15

For instance, we analyze the complexity of the tree aggregation operation as
follows. From Lemma 5, we apply the tree aggregation operation to each module
separately in TT A (w) = O(log w) time, ST A (w) = O(log w) space, and PT A (w) =O(w log w) preprocessing with module size m ≤ w as in small pattern case. By summing up the complexities for all modules, we ﬁnally obtain TT A (m) = O(⌈m/w⌉ log w) =O(m log w/w) time, ST A (m) = O(⌈m/w⌉ log w) = O(m log w/w) space, and PT A (m) =O(⌈m/w⌉w log w) = O(m log w) preprocessing. Similarly, analysis of other operations follows from Lemma 3 and Lemma 4. Hence, the result is proved.
⊓⊔
By substituting the complexities of Lemma 14 for Lemma 12, we have the following result.
Lemma 15. In the large pattern case (m > w), the unordered pseudo-tree matchingproblem is solvable in– O(nm log w/w) time using– O(hm/w + m log w/w) space and– O(m log w) preprocessing.
Combining above arguments in this subsection, we have the main result of thispaper.
Theorem 1. The algorithm BP-UPTreeMatch solves the unordered pseudo-tree
matching problem with the following complexities:– In the large pattern case (m > w): O(nm log w/w) time using O(hm/w +m log w/w) space and O(m log w) preprocessing.
– In the small pattern case (m ≤ w): O(n log m) time using O(h + log m) spaceand O(m log m) preprocessing.
where m and n are the sizes of pattern tree and text tree, h is the height of T , andw = Θ(log n) is the length of computer word.
⋄

A.5

Bit-parallel algorithm for unordered tree homeomorphism

In this section, we show detailed deﬁnitions and lemmas for Sec. 4. In the unordered
tree homeomorphism problem (UTH), we employ two sets Desc-EmbP,T (v) and
Sub-EmbP,T (v) ⊆ V (P ) = [1..m] for every node v in T deﬁned as follows.
Let v be any node in T . Then, the set Desc-EmbP,T (v), called the descendant
embedding set and the auxiliary set Sub-EmbP,T (v) are deﬁned by:
Desc-EmbP,T (v) = { x ∈ [1..m] | (∃ϕ ∈ U T H(P (x), T ) ϕ(x) = v }.

(3)

Sub-EmbP,T (v) = { x ∈ [1..m] | (∃ϕ ∈ U T H(P (x), T )(∃w ≽ v) ϕ(x) = w }.
Lemma 11 in Sec. 4 gives a decomposition formula for UTH as in one for UPTM
in Sec. 3.1.
We can obtain an algorithm MatchUTH for the unordered tree homeomorphism
problem (UTH) from the algorithm MatchUPTM by replacing Line 10 of the recursive subprocedure VisitUPTM with the following line:

16

Yusaku Kaneta and Hiroki Arimura

algorithm MatchUTH(P [1..m]: a pattern tree, T [1..n]: a text tree):Global Variables: P and T ;Output: all occurrences of P in T w.r.t. unordered tree homeomorphism (UTH);
1: VisitUTH(root(T ));procedure VisitUTH(v: text node)
Return Value: R ∪ S = Sub-EmbP,T (v);
2: S ← Constant(∅); {See Deﬁnition 2}
3: for i = 1, . . . α(v) do
4:
S ← Union(S, VisitUTH(v[i]));5: R ← Constant([1..m]);
6: R ← LabelMatchP (R, labelT (v)); {See Deﬁnition 2}
7: R ← TreeAggrP (R, S); {See Deﬁnition 2}
8: if Member(R, root(P )) then {See Deﬁnition 2}
9:output “A match is found at a node v.”;
10: return Union(R, S); {R ∪ S = Sub-EmbP,T (v)}Fig. 7. An algorithm for the unordered tree homeomorphism problem (UTH).

10: return R ∪ S;

{R ∪ S = Sub-EmbP,T (v)}In Fig. 7, we show an algorithm MatchUTH for for the unordered tree homeomorphism problem (UTH) and its recursive subprocedure VisitUTH.
From Lemma 11, the next lemma immediately follows, we see that the obtained
algorithm correctly solves the unordered tree homeomorphism problem in O(mn)time and O(hm) additional space. Furthermore, by similar arguments in the previous
section, we can develop a bit-parallel version, called BP-MatchUTH, of the above
algorithm MatchUTH equipped with the bit-parallel implementation of two operators
TreeAggr and LabelMatch.
Theorem 2. (complexity of the unordered tree homeomorphism problem)
A modiﬁed version of algorithm, BP-MatchUTH, solves the unordered tree homeomorphism problem (UTH) with the following complexities:– In the large pattern case (m > w): O(nm log w/w) time using O(hm/w +m log w/w) additional space and O(m log w) preprocessing.
– In the small pattern case (m ≤ w): O(n log m) time using O(h+log m) additional
space and O(m log m) preprocessing.
where m and n are the sizes of pattern tree and text tree, and w = Θ(log n) is thelength of computer word.
Proof. From the construction of the MatchUTH, it is not hard to see that the algorithm has the same complexity to MatchUPTM as given in Lemma 12. Hence, theresult immediately follows from Lemma 14.
⊓⊔