LCP array construction in external memory

Juha Kärkkäinen; Dominik Kempa

doi:10.1007/978-3-319-07959-2_35

LCP array construction in external memory

Juha Kärkkäinen
, Dominik Kempa

Computer Science

University of Helsinki

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

13 Scopus citations

Abstract

One of the most important data structures for string processing, the suffix array, needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for constructing the LCP array given the suffix array as input. The only previous way to compute the LCP array for data that is bigger than the RAM is to use a suffix array construction algorithm with complex modifications to produce the LCP array as a by-product. Compared to the best prior method, our algorithm needs much less disk space (by more than a factor of three) and is significantly faster. Furthermore, our algorithm can be combined with any suffix array construction algorithm including a better one developed in the future.

Original language	English
Title of host publication	Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings
Publisher	Springer Verlag
Pages	412-423
Number of pages	12
ISBN (Print)	9783319079585
DOIs	https://doi.org/10.1007/978-3-319-07959-2_35
State	Published - 2014
Event	13th International Symposium on Experimental Algorithms, SEA 2014 - Copenhagen, Denmark Duration: Jun 29 2014 → Jul 1 2014

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	8504 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th International Symposium on Experimental Algorithms, SEA 2014
Country/Territory	Denmark
City	Copenhagen
Period	06/29/14 → 07/1/14

Access to Document

10.1007/978-3-319-07959-2_35

Cite this

Kärkkäinen, J., & Kempa, D. (2014). LCP array construction in external memory. In Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings (pp. 412-423). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8504 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-07959-2_35

@inproceedings{0e6b640bb28849d19596999427478e20,

title = "LCP array construction in external memory",

abstract = "One of the most important data structures for string processing, the suffix array, needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for constructing the LCP array given the suffix array as input. The only previous way to compute the LCP array for data that is bigger than the RAM is to use a suffix array construction algorithm with complex modifications to produce the LCP array as a by-product. Compared to the best prior method, our algorithm needs much less disk space (by more than a factor of three) and is significantly faster. Furthermore, our algorithm can be combined with any suffix array construction algorithm including a better one developed in the future.",

author = "Juha K{\"a}rkk{\"a}inen and Dominik Kempa",

year = "2014",

doi = "10.1007/978-3-319-07959-2\_35",

language = "English",

isbn = "9783319079585",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "412--423",

booktitle = "Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings",

note = "13th International Symposium on Experimental Algorithms, SEA 2014 ; Conference date: 29-06-2014 Through 01-07-2014",

}

Kärkkäinen, J & Kempa, D 2014, LCP array construction in external memory. in Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8504 LNCS, Springer Verlag, pp. 412-423, 13th International Symposium on Experimental Algorithms, SEA 2014, Copenhagen, Denmark, 06/29/14. https://doi.org/10.1007/978-3-319-07959-2_35

LCP array construction in external memory. / Kärkkäinen, Juha; Kempa, Dominik.
Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings. Springer Verlag, 2014. p. 412-423 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8504 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - LCP array construction in external memory

AU - Kärkkäinen, Juha

AU - Kempa, Dominik

PY - 2014

Y1 - 2014

N2 - One of the most important data structures for string processing, the suffix array, needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for constructing the LCP array given the suffix array as input. The only previous way to compute the LCP array for data that is bigger than the RAM is to use a suffix array construction algorithm with complex modifications to produce the LCP array as a by-product. Compared to the best prior method, our algorithm needs much less disk space (by more than a factor of three) and is significantly faster. Furthermore, our algorithm can be combined with any suffix array construction algorithm including a better one developed in the future.

AB - One of the most important data structures for string processing, the suffix array, needs to be augmented with the longest-common-prefix (LCP) array in numerous applications. We describe the first external memory algorithm for constructing the LCP array given the suffix array as input. The only previous way to compute the LCP array for data that is bigger than the RAM is to use a suffix array construction algorithm with complex modifications to produce the LCP array as a by-product. Compared to the best prior method, our algorithm needs much less disk space (by more than a factor of three) and is significantly faster. Furthermore, our algorithm can be combined with any suffix array construction algorithm including a better one developed in the future.

UR - https://www.scopus.com/pages/publications/84903746793

U2 - 10.1007/978-3-319-07959-2_35

DO - 10.1007/978-3-319-07959-2_35

M3 - Conference contribution

AN - SCOPUS:84903746793

SN - 9783319079585

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 412

EP - 423

BT - Experimental Algorithms - 13th International Symposium, SEA 2014, Proceedings

PB - Springer Verlag

T2 - 13th International Symposium on Experimental Algorithms, SEA 2014

Y2 - 29 June 2014 through 1 July 2014

ER -

LCP array construction in external memory

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this