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.