MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Kärkkäinen, Juha
Sanders, Peter		dblp
dblp
Editor(s):
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.		dblp
dblp
dblp
dblp
Not MPII Editor(s):
Baeten, Jos C.M.
Lenstra, Jan Karel
Parrow, Joachim
Woeginger, Gerhard J.
BibTeX cite key*:
KarkkainenSanders2003
Title, Booktitle
Title*:
Simple Linear Work Suffix Array Construction
Booktitle*:
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Event, URLs
Conference URL::
http://www.win.tue.nl/icalp2003/
Downloading URL:
http://www.mpi-sb.mpg.de/~sanders/papers/index.html
Event Address*:
Eindhoven, The Netherlands
Language:
English
Event Date*
(no longer used):
June 30 - July 4, 2003
Organization:
Event Start Date:
15 January 2004
Event End Date:
15 January 2004
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2719
Number:
Month:
Pages:
943-955
Year*:
2003
VG Wort Pages:
31
ISBN/ISSN:
3540404937
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) 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.
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{KarkkainenSanders2003,
AUTHOR = {K{\"a}rkk{\"a}inen, Juha and Sanders, Peter},
 EDITOR = {Baeten, Jos C.M. and Lenstra, Jan Karel and Parrow, Joachim and Woeginger, Gerhard J.},
 TITLE = {Simple Linear Work Suffix Array Construction},
 BOOKTITLE = {Automata, languages and programming : 30th International Colloquium, ICALP 2003},
 PUBLISHER = {Springer},
 YEAR = {2003},
 VOLUME = {2719},
 PAGES = {943--955},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Eindhoven, The Netherlands},
 ISBN = {3540404937},
}

Entry last modified by Christine Kiesel, 03/02/2010
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)
Juha Kaerkkainen		Created
04/15/2003 16:41:44
Revisions
5.
4.
3.
2.
1.		Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel
Christine Kiesel		Edit Dates
15.06.2004 14:34:14
15.06.2004 14:32:50
11.06.2004 17:07:52
11.06.2004 17:07:42
01/15/2004 07:49:26 PM