English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Better External Memory Suffix Array Construction

Dementiev, R., Kärkkäinen, J., Mehnert, J., & Sanders, P. (2005). Better External Memory Suffix Array Construction. In Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005) (pp. 86-97). Philadelphia, USA: SIAM.

Item is

Files

show Files
hide Files
:
DKMS05.pdf (Any fulltext), 232KB
 
File Permalink:
-
Name:
DKMS05.pdf
Description:
-
OA-Status:
Visibility:
Private
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
-
License:
-

Locators

show

Creators

show
hide
 Creators:
Dementiev, Roman1, Author           
Kärkkäinen, Juha1, Author           
Mehnert, Jens1, Author           
Sanders, Peter1, Author           
Demetrescu, Camil, Editor
Sedgewick, Robert, Editor
Tamassia, Roberto, Editor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 Abstract: Suffix arrays are a simple and powerful data structure for text processing that can be used for full text indexes, data compression, and many other applications in particular in bioinformatics. However, so far it looked prohibitive to build suffix arrays for huge inputs that do not fit into main memory. This paper presents design, analysis, implementation, and experimental evaluation of several new and improved algorithms for suffix array construction. The algorithms are asymptotically optimal in the worst case or on the average. Our implementation can construct suffix arrays for inputs of up to 4GByte in hours on a low cost machine where all previous implementations we are aware of would fail or take days. We also present a simple and efficient external algorithm for checking whether an array of indexes is a suffix array. As a tool of possible independent interest we present a systematic way to design, analyze, and implement \emph{pipelined} algorithms.

Details

show
hide
Language(s): eng - English
 Dates: 2006-06-162005
 Publication Status: Issued
 Pages: -
 Publishing info: Philadelphia, USA : SIAM
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 279183
Other: Local-ID: C1256428004B93B8-3A3C24F177ACF9B2C1256FAC0057E187-DKMS05
 Degree: -

Event

show
hide
Title: Untitled Event
Place of Event: Vancouver, British Columbia, Canada
Start-/End Date: 2005-01-22

Legal Case

show

Project information

show

Source 1

show
hide
Title: Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics (ALENEX/ANALCO 2005)
Source Genre: Proceedings
 Creator(s):
Affiliations:
Publ. Info: Philadelphia, USA : SIAM
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 86 - 97 Identifier: ISBN: 0-89871-596-2