MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Dementiev, Roman
Kärkkäinen, Juha
Mehnert, Jens
Sanders, Peter		dblp
dblp
dblp
dblp
Not MPG Author(s):
Kärkkäinen, Juha
Editor(s):
Demetrescu, Camil
Sedgewick, Robert
Tamassia, Roberto		dblp
dblp
dblp
BibTeX cite key*:
DKMS05
Title, Booktitle
Title*:
Better External Memory Suffix Array Construction
DKMS05.pdf (231.19 KB)
Booktitle*:
Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics
(ALENEX/ANALCO 2005)
Event, URLs
Conference URL::
http://www.siam.org/meetings/alenex05/
Downloading URL:
http://i10www.ira.uka.de/dementiev/files/DKMS05.pdf

http://www.siam.org/meetings/alenex05/papers/08rdementiev.pdf
Event Address*:
Vancouver, British Columbia, Canada
Language:
English
Event Date*
(no longer used):
Organization:
Society for Industrial and Applied Mathematics (SIAM), ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)
Event Start Date:
22 January 2005
Event End Date:
22 January 2005
Publisher
Name*:
SIAM
URL:
http://www.siam.org/
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
86-97
Year*:
2005
VG Wort Pages:
14
ISBN/ISSN:
0-89871-596-2
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{DKMS05,
AUTHOR = {Dementiev, Roman and K{\"a}rkk{\"a}inen, Juha and Mehnert, Jens and Sanders, Peter},
 EDITOR = {Demetrescu, Camil and Sedgewick, Robert and Tamassia, Roberto},
 TITLE = {Better External Memory Suffix Array Construction},
 BOOKTITLE = {Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics
(ALENEX/ANALCO 2005)},
 PUBLISHER = {SIAM},
 YEAR = {2005},
 ORGANIZATION = {Society for Industrial and Applied Mathematics (SIAM), ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)},
 PAGES = {86--97},
 ADDRESS = {Vancouver, British Columbia, Canada},
 MONTH = {January},
 ISBN = {0-89871-596-2},
}

Entry last modified by Christine Kiesel, 06/16/2006
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Roman Dementiev		Created
02/18/2005 16:59:53
Revisions
8.
7.
6.
5.
4.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
16.06.2006 08:49:06
13.06.2006 15:38:42
13.06.2006 10:18:34
02.06.2006 13:43:57
02.06.2006 13:42:50

File Attachment Icon
DKMS05.pdf