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

XCQ : a framework for XML compression and querying

Authors Lam, Wai-Yeung
Issue Date 2003
Summary 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.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2003
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.