Parallel lookups in string indexes

Anders Roy Christiansen; Martín Farach-Colton

doi:10.1007/978-3-319-46049-9_6

Parallel lookups in string indexes

Anders Roy Christiansen, Martín Farach-Colton

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

Abstract

Recently, the first PRAM algorithms were presented for looking up a pattern in a suffix tree. We improve the bounds, achieving optimal results.

Original language	English (US)
Title of host publication	String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings
Editors	Shunsuke Inenaga, Kunihiko Sadakane, Tetsuya Sakai
Publisher	Springer Verlag
Pages	61-67
Number of pages	7
ISBN (Print)	9783319460482
DOIs	https://doi.org/10.1007/978-3-319-46049-9_6
State	Published - 2016
Event	23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 - Beppu, Japan Duration: Oct 18 2016 → Oct 20 2016

Publication series

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

Conference

Conference	23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016
Country/Territory	Japan
City	Beppu
Period	10/18/16 → 10/20/16

Keywords

PRAM
Parallel
Pattern matching
Suffix trees

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-46049-9_6

Cite this

Christiansen, A. R., & Farach-Colton, M. (2016). Parallel lookups in string indexes. In S. Inenaga, K. Sadakane, & T. Sakai (Eds.), String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings (pp. 61-67). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9954 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-46049-9_6

Parallel lookups in string indexes. / Christiansen, Anders Roy; Farach-Colton, Martín.
String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. ed. / Shunsuke Inenaga; Kunihiko Sadakane; Tetsuya Sakai. Springer Verlag, 2016. p. 61-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9954 LNCS).

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

Christiansen, AR & Farach-Colton, M 2016, Parallel lookups in string indexes. in S Inenaga, K Sadakane & T Sakai (eds), String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9954 LNCS, Springer Verlag, pp. 61-67, 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016, Beppu, Japan, 10/18/16. https://doi.org/10.1007/978-3-319-46049-9_6

Christiansen AR, Farach-Colton M. Parallel lookups in string indexes. In Inenaga S, Sadakane K, Sakai T, editors, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. Springer Verlag. 2016. p. 61-67. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-46049-9_6

Christiansen, Anders Roy ; Farach-Colton, Martín. / Parallel lookups in string indexes. String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings. editor / Shunsuke Inenaga ; Kunihiko Sadakane ; Tetsuya Sakai. Springer Verlag, 2016. pp. 61-67 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{54651a67732748ce89e19877367cd2e6,

title = "Parallel lookups in string indexes",

abstract = "Recently, the first PRAM algorithms were presented for looking up a pattern in a suffix tree. We improve the bounds, achieving optimal results.",

keywords = "PRAM, Parallel, Pattern matching, Suffix trees",

author = "Christiansen, {Anders Roy} and Mart{\'i}n Farach-Colton",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG 2016.; 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016 ; Conference date: 18-10-2016 Through 20-10-2016",

year = "2016",

doi = "10.1007/978-3-319-46049-9_6",

language = "English (US)",

isbn = "9783319460482",

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

publisher = "Springer Verlag",

pages = "61--67",

editor = "Shunsuke Inenaga and Kunihiko Sadakane and Tetsuya Sakai",

booktitle = "String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings",

}

TY - GEN

T1 - Parallel lookups in string indexes

AU - Christiansen, Anders Roy

AU - Farach-Colton, Martín

N1 - Publisher Copyright: © Springer International Publishing AG 2016.

PY - 2016

Y1 - 2016

N2 - Recently, the first PRAM algorithms were presented for looking up a pattern in a suffix tree. We improve the bounds, achieving optimal results.

AB - Recently, the first PRAM algorithms were presented for looking up a pattern in a suffix tree. We improve the bounds, achieving optimal results.

KW - PRAM

KW - Parallel

KW - Pattern matching

KW - Suffix trees

UR - http://www.scopus.com/inward/record.url?scp=84989826820&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84989826820&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-46049-9_6

DO - 10.1007/978-3-319-46049-9_6

M3 - Conference contribution

AN - SCOPUS:84989826820

SN - 9783319460482

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

SP - 61

EP - 67

BT - String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Proceedings

A2 - Inenaga, Shunsuke

A2 - Sadakane, Kunihiko

A2 - Sakai, Tetsuya

PB - Springer Verlag

T2 - 23rd International Symposium on String Processing and Information Retrieval, SPIRE 2016

Y2 - 18 October 2016 through 20 October 2016

ER -

Parallel lookups in string indexes

Abstract

Publication series

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this