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

Burkhardt, Stefan
Kärkkäinen, Juha

dblp
dblp



Editor(s):

Baeza-Yates, R.
Chávez, E.
Crochemore, M.

dblp
dblp
dblp

Not MPII Editor(s):

R. Baeza-Yates, E. Chávez, M. Crochemore

BibTeX cite key*:

Burkhardt2003

Title, Booktitle

Title*:

Fast Lightweight Suffix Array Construction and Checking


cpm03.pdf (222.88 KB)

Booktitle*:

Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003

Event, URLs

URL of the conference:

http://www.fismat.umich.mx/cpm03/

URL for downloading the paper:

http://www.mpi-sb.mpg.de/~stburk/PUBLICATIONS/cpm_03.ps

Event Address*:

Morelia, Michoacán, Mexico

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

25 June 2003

Event End Date:

27 June 2003

Publisher

Name*:

Springer

URL:

http://www.springeronline.com/

Address*:

Heidelberg, Germany

Type:


Vol, No, Year, pp.

Series:

Lecture Notes in Computer Science

Volume:

2676

Number:


Month:

June

Pages:

55-69

Year*:

2003

VG Wort Pages:


ISBN/ISSN:

0302-9743

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.

Keywords:

Suffix Array Construction, Text Indexing

HyperLinks / References / URLs:

http://www.mpi-sb.mpg.de/~stburk/CODE/cpm_03.tar.gz



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Research Context:

Suffix Array Construction, Text Indexing

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Burkhardt2003,
AUTHOR = {Burkhardt, Stefan and K{\"a}rkk{\"a}inen, Juha},
EDITOR = {Baeza-Yates, R. and Ch{\'a}vez, E. and Crochemore, M.},
TITLE = {Fast Lightweight Suffix Array Construction and Checking},
BOOKTITLE = {Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003},
PUBLISHER = {Springer},
YEAR = {2003},
VOLUME = {2676},
PAGES = {55--69},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Morelia, Michoacán, Mexico},
MONTH = {June},
ISBN = {0302-9743},
}


Entry last modified by Sabine Krott, 08/02/2004
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)
Stefan Burkhardt
Created
05/04/2004 09:50:19 AM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Sabine Krott
Christine Kiesel
Christine Kiesel
Stefan Burkhardt
Stefan Burkhardt
Edit Dates
17.06.2004 11:17:27
15.06.2004 14:43:41
15.06.2004 14:42:50
05/04/2004 02:45:28 PM
05/04/2004 09:51:38 AM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:


File Attachment Icon
cpm03.pdf