Indexing Structured Documents with Suffix Arrays

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.