Track: XML and Web Data
Paper Title:
Querying and Maintaining a Compact XML Storage
Authors:
Abstract:
As XML database sizes grow, the amount of space used for storing the data and
auxiliary supporting data structures becomes a major factor in query and update
performance. This paper presents a new storage scheme for XML data
that supports all navigational operations in near constant time.
In addition to supporting efficient queries, the space requirement of the
proposed scheme is within a constant factor of the information theoretic
minimum, while insertions and deletions can be performed in near constant time
as well. As a result, the proposed structure features a small memory footprint
that increases cache locality, whilst still supporting standard APIs, such as
DOM, and necessary database operations, such as queries and updates,
efficiently. Analysis and experiments show
that the proposed structure is space and time efficient.
