Flexible Workload-directed Clustering of XML Documents

We investigate physical data clustering in XML database and repository systems that store XML documents using a native format. We formulate the XML clustering problem as a tree partitioning problem and propose a single pass tree partitioning algorithm, XC, which is based on Lukes' tree partitioning algorithm. XC is an approximate algorithm with substantial improvements over Lukes' algorithm in both memory and time usage. XC also operates under specified memory-use constraints. We discuss a prototype end-to-end data clustering system that uses XC. The prototype scans an XML document, assigns edge-weights according to the application workload, and maps clusters of XML nodes to disk pages, all in a single parser-controlled pass over the XML data. We experimentally evaluated XC by comparing it with a depth-first scan and store scheme (DFS). Experimental results indicate that while the DFS scheme is faster and consumes slightly less disk pages, XC is a superior clustering algorithm in terms of partition quality. The results also indicate that XC can exploit application workload information to generate XML clustering solutions that lead to substantial reduction in page faults for the workload under consideration.

A shorter version of this paper appeared in Lecture Notes in Computer Science.

By: Rajesh Bordawekar; Oded Shmueli

Published in: Lecture Notes in Computer Science, volume 3186, (no ), pages 204-18 in 2004


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .