MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.fismat.umich.mx/cpm03/
Downloading URL:
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
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
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

File Attachment Icon
cpm03.pdf