Time and space efficient evaluation of XPath expressions on Continuously Evolving XML documents

Abstract

Continuously Evolving XML (CEXML) documents have a wide range of applications ranging from software configuration management to scientific information management. CEXML document consists of multiple versions of an XML document as it evolves over time. Evaluating time and space efficient XPath expressions on CEXML is critically important yet challenging. Our framework is a novel adaptation of interval based indexing which incorporates several unique features. First, we significantly reduce storage and indexing costs by selectively indexing a subset of versions of a CEXML document. Second, we use indices in conjunction with inter version edits information for evaluating XPath expressions. Third, we propose a method to prune edits that need to be processed while evaluating an XPath expression on a given version. This thesis also presents a detailed experimental study demonstrating the scalability and efficiency of the proposed framework in terms of indexing costs, query latencies and storage costs.