Optimal parallel algorithms for prefix matching

Ramesh Hariharan; S. Muthukrishnan

doi:10.1007/3-540-58201-0_69

Optimal parallel algorithms for prefix matching

Ramesh Hariharan, S. Muthukrishnan

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

1 Scopus citations

Abstract

The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for this problem. The first algorithm works for the case when the characters in p and t are drawn from an alphabet set of size polynomial in m + n, where m = |p| and n = |t|; it takes O(log m) time, O(m^1+ε+n^1+ε) space, and does O(m + n) work, for any ε>0. The second algorithm works for unbounded alphabet sets and takes O(log²m(log log m)³) time, O(m + n) space, and does O(m + n) work. These are the first known work-optimal algorithms for this problem.

Original language	English (US)
Title of host publication	Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings
Editors	Serge Abiteboul, Eli Shamir
Publisher	Springer Verlag
Pages	203-214
Number of pages	12
ISBN (Print)	9783540582014
DOIs	https://doi.org/10.1007/3-540-58201-0_69
State	Published - 1994
Externally published	Yes
Event	Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 - Jerusalem, Isr Duration: Jul 1 1994 → Jul 1 1994

Publication series

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

Other

Other	Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94
City	Jerusalem, Isr
Period	7/1/94 → 7/1/94

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-58201-0_69

Cite this

Hariharan, R., & Muthukrishnan, S. (1994). Optimal parallel algorithms for prefix matching. In S. Abiteboul, & E. Shamir (Eds.), Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings (pp. 203-214). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 820 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-58201-0_69

Hariharan, Ramesh ; Muthukrishnan, S. / Optimal parallel algorithms for prefix matching. Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings. editor / Serge Abiteboul ; Eli Shamir. Springer Verlag, 1994. pp. 203-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f87fa7167d284929af8051068cf981a3,

title = "Optimal parallel algorithms for prefix matching",

abstract = "The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for this problem. The first algorithm works for the case when the characters in p and t are drawn from an alphabet set of size polynomial in m + n, where m = |p| and n = |t|; it takes O(log m) time, O(m1+ε+n1+ε) space, and does O(m + n) work, for any ε>0. The second algorithm works for unbounded alphabet sets and takes O(log2m(log log m)3) time, O(m + n) space, and does O(m + n) work. These are the first known work-optimal algorithms for this problem.",

author = "Ramesh Hariharan and S. Muthukrishnan",

note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94 ; Conference date: 01-07-1994 Through 01-07-1994",

year = "1994",

doi = "10.1007/3-540-58201-0_69",

language = "English (US)",

isbn = "9783540582014",

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

publisher = "Springer Verlag",

pages = "203--214",

editor = "Serge Abiteboul and Eli Shamir",

booktitle = "Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings",

address = "Germany",

}

Hariharan, R & Muthukrishnan, S 1994, Optimal parallel algorithms for prefix matching. in S Abiteboul & E Shamir (eds), Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 820 LNCS, Springer Verlag, pp. 203-214, Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94, Jerusalem, Isr, 7/1/94. https://doi.org/10.1007/3-540-58201-0_69

Optimal parallel algorithms for prefix matching. / Hariharan, Ramesh; Muthukrishnan, S.
Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings. ed. / Serge Abiteboul; Eli Shamir. Springer Verlag, 1994. p. 203-214 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 820 LNCS).

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

TY - GEN

T1 - Optimal parallel algorithms for prefix matching

AU - Hariharan, Ramesh

AU - Muthukrishnan, S.

PY - 1994

Y1 - 1994

N2 - The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for this problem. The first algorithm works for the case when the characters in p and t are drawn from an alphabet set of size polynomial in m + n, where m = |p| and n = |t|; it takes O(log m) time, O(m1+ε+n1+ε) space, and does O(m + n) work, for any ε>0. The second algorithm works for unbounded alphabet sets and takes O(log2m(log log m)3) time, O(m + n) space, and does O(m + n) work. These are the first known work-optimal algorithms for this problem.

AB - The Prefix Matching Problem is to determine, for each location in the text t, the longest prefix of a given pattern p which occurs beginning at that location. We present two work-optimal parallel algorithms for this problem. The first algorithm works for the case when the characters in p and t are drawn from an alphabet set of size polynomial in m + n, where m = |p| and n = |t|; it takes O(log m) time, O(m1+ε+n1+ε) space, and does O(m + n) work, for any ε>0. The second algorithm works for unbounded alphabet sets and takes O(log2m(log log m)3) time, O(m + n) space, and does O(m + n) work. These are the first known work-optimal algorithms for this problem.

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

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

U2 - 10.1007/3-540-58201-0_69

DO - 10.1007/3-540-58201-0_69

M3 - Conference contribution

AN - SCOPUS:21344498092

SN - 9783540582014

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

SP - 203

EP - 214

BT - Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings

A2 - Abiteboul, Serge

A2 - Shamir, Eli

PB - Springer Verlag

T2 - Proceedings of the 1994 21st International Colloquium on Automata, Languages and Programming, ICALP'94

Y2 - 1 July 1994 through 1 July 1994

ER -

Hariharan R, Muthukrishnan S. Optimal parallel algorithms for prefix matching. In Abiteboul S, Shamir E, editors, Automata, Languages and Programming - 21st International Colloquium, ICALP 1994, Proceedings. Springer Verlag. 1994. p. 203-214. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-58201-0_69

Optimal parallel algorithms for prefix matching

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this