Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








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

URL of the conference:

http://www.siam.org/meetings/alenex05/

URL for downloading the paper:

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
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
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 04:59:53 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
DKMS05.pdf