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


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
Publication date2013
ISBN (Print)978-3-642-39205-4
ISBN (Electronic)978-3-642-39206-1
Publication statusPublished - 2013
Event40th International Colloquium on Automata, Languages and Programming (ICALP 2013) - Riga, Latvia
Duration: 8 Jul 201312 Jul 2013


Conference40th International Colloquium on Automata, Languages and Programming (ICALP 2013)
Internet address
SeriesLecture Notes in Computer Science


  • Algorithms
  • Automata theory
  • Query processing
  • Forestry

Cite this