Reducing Space Requirements for Disk Resident Suffix Arrays
Alistair Moffat, Simon J Puglisi, Ranjan Sinha, X Zhou, H Yokota, K Deng, Q Liu
DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PROCEEDINGS | SPRINGER-VERLAG BERLIN | Published : 2009
Suffix trees and suffix arrays are important data structures for string processing, providing efficient solutions for many applications involving pattern matching. Recent work by Sinha et al. (SIGMOD 2008) addressed the problem of arranging a suffix array on disk so that querying is fast, and showed that the combination of a small trie and a suffix array-like blocked data structure allows queries to be answered many times faster than alternative disk-based suffix trees. A drawback of their LOF-SA structure, and common to all current disk resident suffix tree/array approaches, is that the space requirement of the data structure, though on disk, is large relative to the text – for the LOF-SA, ..View full abstract
This work was supported by the Australian Research Council.