More efficient algorithm for ordered tree inclusion

被引：23

作者：

Chen, WM ^{[1
]}

机构：

[1] IPSI, GMD, D-64293 Darmstadt, Germany

来源：

JOURNAL OF ALGORITHMS | 1998年 / 26卷 / 02期

关键词：

D O I：

10.1006/jagm.1997.0899

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given two ordered trees S and J the tree inclusion problem is to determine whether it is possible to obtain S from J by deleting nodes. Recently, this problem has been recognized as an important primitive in query processing for structured text databases. In this paper we present an O(\leaves(S)\\J\) time and O(\leaves(S)\min(depth(J), \leave(J)\)) space algorithm for ordered tree inclusion, by means of a sophisticated bottom-up-matching strategy. Our algor algorithm improves the previous best one (Kilpelainen, 1992, Ph.D, thesis, Dept. Computer Science, Univ. Helsinki) that requires O(\S\J\) time and O(\S\min(depth(J), \leaves(J)\)) space. (C) 1998 Academic Press.

引用

页码：370 / 385

页数：16

共 11 条

[1]

ALONSO L, 1993, P MATH FDN COMP SCI, P211

[2]

Gonnet G. H., 1987, Proceedings of the Thirteenth International Conference on Very Large Data Bases: 1987 13th VLDB, P339

[3] ORDERED AND UNORDERED TREE INCLUSION [J].