HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5785
Title: XCQ : a framework for XML compression and querying
Authors: Lam, Wai-Yeung
Issue Date: 2003
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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2003
xvii, 171 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 2003 Lam
URI: http://hdl.handle.net/1783.1/5785
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.