ON THE EVALUATION OF TREE PATTERN QUERIES

Yangjun Chen

2006

Abstract

The evaluation of Xpath expressions can be handled as a tree embedding problem. In this paper, we propose two strategies on this issue. One is ordered-tree embedding based and the other is unordered-tree embedding based. For the ordered-tree embedding, our algorithm needs only O(|T| x |P|) time and (|T| x |P|) space, where |T| and |P| stands for the numbers of the nodes in the target tree T and the pattern tree P, respectively. For the unordered-tree embedding, we give an algorithm that needs (|T| x |P|)x 22k) time, where k is the largest out-degree of any node in P.

Paper Citation

in Harvard Style

Chen Y. (2006). ON THE EVALUATION OF TREE PATTERN QUERIES . In Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT, ISBN 978-972-8865-69-6, pages 79-85. DOI: 10.5220/0001308700790085

in Bibtex Style

@conference{icsoft06,
author={Yangjun Chen},
title={ON THE EVALUATION OF TREE PATTERN QUERIES},
booktitle={Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT,},
year={2006},
pages={79-85},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001308700790085},
isbn={978-972-8865-69-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT,
TI - ON THE EVALUATION OF TREE PATTERN QUERIES
SN - 978-972-8865-69-6
AU - Chen Y.
PY - 2006
SP - 79
EP - 85
DO - 10.5220/0001308700790085