Analysis of Tree Edit Distance on XML Data
Date Issued
2007
Date
2007
Author(s)
WU, YU-FANG
DOI
en-US
Abstract
The problem of comparing tree structures occurs in various areas in computer science and engineering, including the application to XML data processing. To solve this problem, tree edit distance is a common and significant measurement defining the difference between two tree structures quantitatively. Efficient tree edit distance embedding algorithms are therefore of significant importance in comparing large streaming XML document trees. In this thesis, we propose a new algorithm to obtain edit distance between unlabeled ordered trees derived from streaming XML data. In comparison with the previous work, our contribution lies in simplifying the procedure of obtaining the tree edit distance without increasing the time and space complexities. The upper and lower bounds as well as the error probability of our algorithm are also analyzed in this thesis.
Subjects
樹狀結構編輯距離
演算法
串流
無標記有序樹狀結構
Tree Edit Distance
XML
Algorithm
Streaming
Unlabeled Ordered Trees
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-96-R93921142-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):7045a0c4e670147d16ae0672b9c7733e