TY - GEN
T1 - A bit-parallel tree matching algorithm for patterns with horizontal VLDC's
AU - Tsuji, Hisashi
AU - Ishino, Akira
AU - Takeda, Masayuki
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=33646720695&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646720695&partnerID=8YFLogxK
U2 - 10.1007/11575832_43
DO - 10.1007/11575832_43
M3 - Conference contribution
AN - SCOPUS:33646720695
SN - 3540297405
SN - 9783540297406
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 388
EP - 398
BT - String Processing and Information Retrieval - 12th International Conference, SPIRE 2005, Proceedings
T2 - 12th International Conference on String Processing and Information Retrieval, SPIRE 2005
Y2 - 2 November 2005 through 4 November 2005
ER -