SuffIndex—An XML Index Structure Based on Suffix Tree

SuffIndex—an XML index structure based on suffix tree is proposed SuffIndex can efficiently be used for evaluation of XPath queries which have the form of ∥ element 1/element 2/…/element m The construction of SuffIndex is carried out by traveling source OEM data tree only once and introducing Sufflinks into SuffIndex so that the cost of construction is low At the same time, each node in SuffIndex has a hash table to store pointers to all its children and in each index node there is an extent set in which all items are the result of path query of form ∥ element 1/element 2/…/element m All these make the cost of querying ∥ element 1/element 2/…/element m into O（m）