Document retrieval from suffix arrays on disk

Abstract

The research papers about suffix arrays have grown many, and asymptotically better algorithms are being developed. There are, however, two areas that seem to have been a little forgotten - searching in external memory and document retrieval from a suffix array. We present and compare four different methods for document retrieval from an external suffix array. Our results show that only one yields adequate results in the presence of many documents, namely embedding document information into the suffix array. We also touch on the subject of searching external suffix arrays, presenting and discussing four techniques.