Raymond Wong (National ICT Australia and University of New South Wales)
Franky Lam (National ICT Australia and University of New South Wales)
William Shui (National ICT Australia and University of New South Wales)
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.
Slot:
New Brunswick, Thursday, May 10, 2007, 10:30am to 12 noon.