Indexing Structured Documents with Suffix Arrays
Yosvanys Aponte B'ez, Rafael C. Carrasco Jimenez · 2012
Path indexes based on suffix trees have shown to be highly efficient structures when dealing with digital collection that consists of structured documents, since they provide a fast response to queries including structural requirements. Nevertheless, when the collection consists of highly heterogeneous documents, suffix trees may be too memory demanding. In such cases, the use of a suffix array as the underlying data storage permits a considerable reduction in space requirements, partially because suffix arrays are a remarkably light data structure and partially because they do not store redundant information regarding the textual content. We describe how a suffix array can be used as the data structure which stores the structural index in a retrieval system and provides a virtual index of all sub paths in the digital collection. We also show how an auxiliary ternary search tree can accelerate the resolution of structural queries with only a marginal increase in memory usage.