Please use this identifier to cite or link to this item:

An I/O-efficient data structure for querying XML with inherited attributes

Authors Lau, Ching Hin
Issue Date 2009
Summary XML documents have a tree-like hierarchical structure design and XML has become popular as the standard data format for exchanging information over the Internet. Recent research has explored issues on querying different types of metadata associated with an XML document, including annotations, quality assessments, security policies, etc. The metadata considered by many of these approaches can be modeled as values from a totally ordered domain (e.g. recency using timestamps). A natural model for annotating XML data with metadata is to associate metadata explicitly only with selected element nodes in the XML data tree. For elements where the metadata is not explicitly specified, it is inherited from the nearest ancestor where it is explicitly specified. We show that such a metadata model can be converted to a 3-sided 2D range query problem. Thus, we present an external binary priority search tree which is a data structure for querying XML with inherited attributes I/O-efficiently. We can build our structure in O(N/B log2N) I/Os, answer a query in O(log2N + T / B) I/Os and return an update in O(log2N) I/Os, where B is the disk block size, N is the size of the XML document, and T is the size of the query output. We have also demonstrated the practical efficiency of our index structure with experiments on benchmark XML data.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2009
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 339 B HTML
Copyrighted to the author. Reproduction is prohibited without the author’s prior written consent.