Multi-dimensional Indexing For XML Data

The Extensible Markup Language (XML) is becoming a dominant standard for exchanging and retrieving data over the internet. As XML in data exchanging grows, various XML indexing techniques have been proposed for fast and efficient query processing. A survey of theses techniques [9] categorized them into sequence-based indexes, structural indexes, dimension-based indexes and keyword-based indexes based on their properties. In this thesis, we focus on the multi-dimensional XML indexing; more precisely, it can be categorized as a 2-dimension based indexing, which is used in this paper. We studied the properties of multi-dimensional XML indexing and created an implementation to evaluate its performance. It performs well with arbitrary path expressions and retrieves results from a relational database, which is stable and safe. We also compare the performance of the 2-dimensional indexing with the structure based indexing, which stores summary information of XML documents' tree nodes in main memory.