Paper Info
Title
A bit-parallel tree matching algorithm for patterns with horizontal VLDC's
Abstract
The tree pattern matching problem is, given two labeled trees P and T, respectively called pattern tree and target tree, to find all occurrences of P within T. Many studies have been undertaken on this problem for both the cases of ordered and unordered trees. To realize flexible matching, a kind of variable-length-don't-care's (VLDC's) have been introduced. In particular, the path-VLDC's appear in XPath, a language for addressing parts of an XML document. In this paper, we introduce horizontal VLDC's, each matches a sequence of trees whose root nodes are consecutive siblings in ordered trees. We address the tree pattern matching problem for patterns with horizontal VLDC's. In our setting, the target tree is given as a tagged sequence such as XML data stream. We present an algorithm that solves the problem in O(mn) time using O(mh) space, where m and n are the sizes of P and T, respectively, and h is the height of T. We adopt the bit-parallel technique to obtain a practically fast algorithm.
Year
DOI
Venue
2005
10.1007/11575832_43
SPIRE
Keywords
Field
DocType
trees p,flexible matching,bit-parallel tree,tree pattern,target tree,fast algorithm,xml data stream,unordered tree,xml document,pattern tree,horizontal vldc,pattern matching
Discrete mathematics,Combinatorics,Range tree,Tree rotation,Computer science,Parallel algorithm,K-ary tree,XPath,Tree structure,Pattern matching,Blossom algorithm
Conference
Volume
ISSN
ISBN
3772
0302-9743
3-540-29740-5
Citations 
PageRank 
References 
2
0.38
15
Authors
3
Name
Order
Citations
PageRank
Hisashi Tsuji120.38
Akira Ishino2547.31
Masayuki Takeda390279.24