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):

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

URL of the conference:

http://www.win.tue.nl/icalp2003/

URL for downloading the paper:

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
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)
Juha Kaerkkainen
Created
04/15/2003 04:41:44 PM
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
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section