Sparse suffix tree construction in small space

Philip Bille, Johannes Fischer, Inge Li Gørtz, Tsvi Kopelowitz, Benjamin Sach, Hjalte Wedel Vildhøj

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

We consider the problem of constructing a sparse suffix tree (or suffix array) for b suffixes of a given text T of length n, using only O(b) words of space during construction. Attempts at breaking the naive bound of Ω(nb) time for this problem can be traced back to the origins of string indexing in 1968. First results were only obtained in 1996, but only for the case where the suffixes were evenly spaced in T. In this paper there is no constraint on the locations of the suffixes. We show that the sparse suffix tree can be constructed in O(nlog2 b) time. To achieve this we develop a technique, which may be of independent interest, that allows to efficiently answer b longest common prefix queries on suffixes of T, using only O(b) space. We expect that this technique will prove useful in many other applications in which space usage is a concern. Our first solution is Monte-Carlo and outputs the correct tree with high probability. We then give a Las-Vegas algorithm which also uses O(b) space and runs in the same time bounds with high probability when b = O(√n). Furthermore, additional tradeoffs between the space usage and the construction time for the Monte-Carlo algorithm are given.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming : 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I
PublisherSpringer
Publication date2013
Pages148-159
ISBN (Print)978-3-642-39205-4
ISBN (Electronic)978-3-642-39206-1
DOIs
Publication statusPublished - 2013
Event40th International Colloquium on Automata, Languages and Programming (ICALP 2013) - Riga, Latvia
Duration: 8 Jul 201312 Jul 2013
http://www.icalp2013.lu.lv/

Conference

Conference40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
CountryLatvia
CityRiga
Period08/07/201312/07/2013
Internet address
SeriesLecture Notes in Computer Science
Volume7965
ISSN0302-9743

Keywords

  • Algorithms
  • Automata theory
  • Query processing
  • Forestry

Cite this