Institute of Information Science, Academia Sinica

Since the release of XML 1.0 recommended by W3C in 1998, the development of XML technologies have grown into a big family of specifications. Nowadays, XML is widely used as the standard for data representation and information exchange over the Web. Over the past several years, our research team in the Data Mining and Knowledge Engineering Lab at National Chung Hsing University worked on efficient indexing schemes for XML documents and proposed several indexing methods such as Path Clustering Indexing Method (PCIM), Node Clustering Indexing Method (NCIM), CIS-X (Compacted Indexing Scheme for XML). These indexing methods all have small index files and fast query evaluation time for complex queries.
In order to support efficient update operations on XML documents, we developed a new indexing scheme called UCIS-X (Updatable Compacted Indexing Scheme for XML) based on CIS-X. The proposed method can support almost all update operations defined on the W3C XQuery Update Facility 1.0 without index rebuilding. The experimental results on the three data sets DBLP, XMark, and Nasa show that UCIS-X has very short index building time, high compression ratio for index files, and fast evaluation time both for query operations and update operations compared to other indexing schemes such as ORDPATH, which is implemented in Microsoft SQL ServerTM 2005.