Abstract
XML Indexing and Storage System (XISS) is a system designed to store XML
data and answer regular path expressions (RPE) efficiently. XISS
decomposes incoming RPE into simple steps and solves each step one of the
following three algorithms: EA-join, EE-join and KC-join. An numbering
scheme based on "extend preorder traversal" is used for enabling those
join algorithms. These algorithms are based on two stage merge sort and
hence can be evaluated efficiently.
Index Fabric is an index to XML data based on Patricia. The element and
attribute names are coded in special characters called "designators".
Each data node is associated with a key constructed by concatenating the
designators of its path and its data value. The nodes are inserted into a
Patricia trie based on their key values. They also provide a B-tree like
layered approach to reduce the disk access in trie lookup.
