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

Crauser, Andreas
Ferragina, Paolo

dblp
dblp



Editor(s):

Nesetril, Jaroslav

dblp



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

URL of the conference:


URL for downloading the paper:


Event Address*:

Prague, Czech Republic

Language:

English

Event Date*
(no longer used):

July, 16 - July, 18

Organization:


Event Start Date:

15 October 2019

Event End Date:

15 October 2019

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