Overcoming the memory bottleneck in suffix tree construction

Martin Farach, Paolo Ferragina, S. Muthukrishnan

    Research output: Contribution to journalConference articlepeer-review

    Abstract

    The suffix tree of a string is the fundamental data structure of string processing. Recent focus on massive data sets has sparked interest in overcoming the memory bottlenecks of known algorithms for building suffix trees. Our main contribution is a new algorithm for suffix tree construction in which we choreograph almost all disk accesses to be via the sort and scan primitives. This algorithm achieves optimal results in a variety of sequential and parallel computational models. Two of our results are: In the traditional external memory model, in which only the number of disk accesses is counted, we achieve an optimal algorithm, both for single and multiple disk cases. This is the first optimal algorithm known for either model. Traditional disk page access counting does not differentiate between random page accesses and block transfers involving several consecutive pages. This difference is routinely exploited by expert programmers to get fast algorithms on real machines. We adopt a simple accounting scheme and show that our algorithm achieves the same optimal tradeoff for block versus random page accesses as the one we establish for sorting.

    Original languageEnglish (US)
    Pages (from-to)174-183
    Number of pages10
    JournalAnnual Symposium on Foundations of Computer Science - Proceedings
    StatePublished - 1998
    EventProceedings of the 1998 39th Annual Symposium on Foundations of Computer Science - Palo Alto, CA, USA
    Duration: Nov 8 1998Nov 11 1998

    ASJC Scopus subject areas

    • Hardware and Architecture

    Fingerprint Dive into the research topics of 'Overcoming the memory bottleneck in suffix tree construction'. Together they form a unique fingerprint.

    Cite this