MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Crauser, Andreas
Ferragina, Paolo		dblp
dblp
Editor(s):
Nesetril, Jaroslavdblp
BibTeX cite key*:
Crauser1999
Title, Booktitle
Title*:
On Constructing Suffix Arrays in External Memory
Booktitle*:
Proceedings of the 7th Annual European Symposium on Algorithms (ESA-99)
Event, URLs
Conference URL::
Downloading URL:
Event Address*:
Prague, Czech Republic
Language:
English
Event Date*
(no longer used):
July, 16 - July, 18
Organization:
Event Start Date:
24 November 2020
Event End Date:
24 November 2020
Publisher
Name*:
Springer
URL:
Address*:
Berlin
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
1643
Number:
Month:
Pages:
224-235
Year*:
1999
VG Wort Pages:
ISBN/ISSN:
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
 The construction of full-text indexes on very large text collections
is nowadays a hot problem. The suffix array~\cite{Manber-Myers} is
one of the most attractive full-text indexing data structures due to
its simplicity, space efficiency and powerful/fast search operations
supported. In this paper we analyze theoretically and
experimentally, the I/O-complexity and the working space of six
algorithms for constructing large suffix arrays. Additionally, we
design a new external-memory algorithm that follows the basic
philosophy underlying the algorithm in~\cite{book-info} but in a
significantly different manner, thus combining its good practical
qualities with efficient worst-case performances. At the best of our
knowledge, this is the first study which provides a wide spectrum of
possible approaches to the construction of suffix arrays in external
memory, and thus it should be helpful to anyone who is interested in
building full-text indexes on very large text collections.
Keywords:
text indexing, external memoryJuly
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
experts only
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat



BibTeX Entry:

@INPROCEEDINGS{Crauser1999,
AUTHOR = {Crauser, Andreas and Ferragina, Paolo},
 EDITOR = {Nesetril, Jaroslav},
 TITLE = {On Constructing Suffix Arrays in External Memory},
 BOOKTITLE = {Proceedings of the 7th Annual European Symposium on Algorithms (ESA-99)},
 PUBLISHER = {Springer},
 YEAR = {1999},
 VOLUME = {1643},
 PAGES = {224--235},
 SERIES = {Lecture Notes in Computer Science},
 ADDRESS = {Prague, Czech Republic},
}

Entry last modified by Anja Becker, 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)
Andreas Crauser		Created
02/17/2000 03:31:34 PM
Revisions
2.
1.
0.

Editor(s)
Anja Becker
Anja Becker
Andreas Crauser

Edit Dates
06.04.2000 15:56:02
29.03.2000 13:10:47
17/02/2000 15:31:34