AN I/O-EFFICIENT DATA STRUCTURE FOR QUERYING XML WITH INHERITED ATTRIBUTES

MPhil Thesis Defence


Title: "AN I/O-EFFICIENT DATA STRUCTURE FOR QUERYING XML WITH INHERITED ATTRIBUTES"

By

Mr. Ching-Hin Lau


Abstract

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 
meta-data associated with an XML document, including annotations, quality 
assessments, security policies, etc. The meta-data 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 meta-data is to 
associate meta-data explicitly only with selected element nodes in the XML data 
tree. For elements where the meta-data is not explicitly specified, it is 
inherited from the nearest ancestor where it is explicitly specified. We show 
that such a meta-data model can be converted to a 3-sided 2D range query 
problem. Thus, we present an external binary priority search which is a data 
structure for querying XML with inherited attributes I/O-efficiently. We can 
build our structure in O(N/B log N) I/Os, answer a query in O(log N + T/B) 
I/Os and return an update in O(log N) 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 
extensive experiments.


Date:			Tuesday, 23 June 2009

Time:			10:00am-12:00noon

Venue:			Room 3501
 			Lifts 25-26

Committee Members:	Dr. Ke Yi (Supervisor)
 			Dr. Wilfred Ng (Chairperson)
 			Dr. Lei Chen


**** ALL are Welcome ****