MPhil Thesis Defence


"XCQ: A Framework for XML Compression and Querying"

By

Mr. Wai-Yeung Lam


Abstract

XML has already become the defacto standard for specifying and exchanging
data on the Web. However, XML is by nature verbose and thus XML documents
are usually large in size. The size problem of XML documents usually
hinders their practical usage, since it substantially increases the costs
of storing, processing and exchanging data. As XML documents are stored in
plain-text format, a promising way to relieve the size problem is to
compress the XML data using existing text compression technologies, such
as gzip and bzip. However, due to the fact that an XML document presents
its structure and data in a self-describing manner through its associated
DTD and the tags in the document, respectively, one can make use of this
knowledge to help facilitate better compression as well as generate more
usable compressed data to support querying.

This thesis proposes the XML Compression and Querying (XCQ) Framework,
which is designed for XML compression and compressed XML querying. Herein
we show that by utilizing the structural information from the input XML
document and its associated DTD during the compression process, XCQ can
achieve better compression ratio than that of gzip as well as generate
more usable compressed data that is able to be queried without running a
full decompression. This thesis presents in detail the techniques
developed for implementing the XCQ Framework. These techniques include:
(1) the DTD Tree and SAX Event Stream Parsing} (DSP), which is designed
for efficient compression of valid XML documents without involving user
expertise, (2) the Partitioned Path-Based Data Grouping (PPG) compressed
document format, which supports querying over compressed XML data by
performing partial decompression, (3) the Block Statistic Signature (BSS)
indexing, which is designed for indexing block-oriented compressed data
that aims at using minimal system resources, and (4) the access method
that is used for realizing partial decompression when processing
selection, structural, structure-based aggregation, and path-based
aggregation queries over a compressed XML document.

We discuss the underlying ideas and design considerations that have led us
to develop these techniques and designs. We demonstrate with comprehensive
examples of how the XCQ Framework works and how compressed documents are
queried by partial decompression. We then present our implementation of a
prototype that realizes the XCQ Framework. Finally, we test the prototype
using a diversified set of experiments. The results show that the
prototype achieves a compression ratio comparable to that of XMill while
supporting better compression and querying performances than XGrind.


Date:				Friday, 28 November 2003

Time:				2:00p.m.-4:00p.m.

Venue:				Room 3405
				Lifts 17-18

Committee Members:		Dr. Wilfred Ng (Supervisor)
				Prof. Dik-Lun Lee (Chairman)
				Prof. Hongjun Lu


**** ALL are Welcome ****