English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Simple Linear Work Suffix Array Construction

Kärkkäinen, J., & Sanders, P. (2003). Simple Linear Work Suffix Array Construction. In Automata, languages and programming: 30th International Colloquium, ICALP 2003 (pp. 943-955). Berlin, Germany: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Kärkkäinen, Juha1, Author           
Sanders, Peter1, Author           
Baeten, Jos C.M., Editor
Lenstra, Jan Karel, Editor
Parrow, Joachim, Editor
Woeginger, Gerhard J., Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: A suffix array represents the suffixes of a string in sorted order. Being a simpler and more compact alternative to suffix trees, it is an important tool for full text indexing and other string processing tasks. We introduce the \emph{skew algorithm} for suffix array construction over integer alphabets that can be implemented to run in linear time using integer sorting as its only nontrivial subroutine:\\ 1. recursively sort suffixes beginning at positions $i\bmod 3\neq 0$.\\ 2. sort the remaining suffixes using the information obtained in step one.\\ 3. merge the two sorted sequences obtained in steps one and two.\\ The algorithm is much simpler than previous linear time algorithms that are all based on the more complicated suffix tree data structure. Since sorting is a well studied problem, we obtain optimal algorithms for several other models of computation, e.g.\ external memory with parallel disks, cache oblivious, and parallel. The adaptations for BSP and EREW-PRAM are asymptotically faster than the best previously known algorithms.

Details

show
hide
Language(s): eng - English
 Dates: 2004-06-152003
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 201844
Other: Local-ID: C1256428004B93B8-901BAE3BF9EE93A5C1256D090050B9C2-KarkkainenSanders2003
 Degree: -

Event

show
hide
Title: ICALB 2003
Place of Event: Eindhoven, The Netherlands
Start-/End Date: 2003-06-30 - 2003-07-04

Legal Case

show

Project information

show

Source 1

show
hide
Title: Automata, languages and programming : 30th International Colloquium, ICALP 2003
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 943 - 955 Identifier: ISBN: 3540404937

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2719 Sequence Number: - Start / End Page: - Identifier: -