Highly efficient dictionary matching in parallel

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Highly efficient dictionary matching in parallel

Full text

Pdf (1.18 MB)

Source

ACM Symposium on Parallel Algorithms and Architectures archive
Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures table of contents

Velen, Germany

Pages: 69 - 78

Year of Publication: 1993

ISBN:0-89791-599-2

Authors

S. Muthukrishnan
K. Palem

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
European Comp Soc : European Computer Society

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 24, Citation Count: 3

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/165231.165239 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AB92	Amihood Amir , Gary Benson, Two-dimensional periodicity and its applications, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.440-452, September 1992, Orlando, Florida, United States
	ABF93	Amihood Amir , Gary Benson , Martin Farach, Optimal parallel two dimensional pattern matching, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.79-85, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165242]
	AC75	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	AF91	Amihood Amir , Martin Farach, Adaptive dictionary matching, Proceedings of the 32nd annual symposium on Foundations of computer science, p.760-766, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185445]
	AF92	Amihood Amir , Martin Farach, Two-dimensional dictionary matching, Information Processing Letters, v.44 n.5, p.233-239, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90206-B]
	AFGGP91	A. Amir, M. Farach, R. Giancarlo, Z. Galil, and K. Park. Dynamic dictionary matching. Manuscript, 1991.
	AFILS93	Amihood Amir , Martin Farach , Ramana M. Idury , Johannes A. La Poutré , Alejandro A. Schäffer, Improved dynamic dictionary matching, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.392-401, January 25-27, 1993, Austin, Texas, United States
	AFM92	Amihood Amir , Martin Farach , Yossi Matias, Efficient Randomized Dictionary Matching Algorithms (Extended Abstract), Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.262-275, April 29-May 01, 1992
	AILSV88	A. Apostolico, C. Iliopoulos, G. Landau, B. Schieber, and U. Vishkin. Parallel Construction of a Suffix Tree with Applications. Algeri#hmica 8, 1988, 347-8(35.
	B77	R. Bird. Two Dimensional Pattern Matching. Information Processing Letters 6:168- 170, 1977.
	Ba78	T. Baker. A Technique for Extending Rapid Exact String Matching to Arrays of More Than One Dimension. SIAM J. Computing 7:533-541, 1978.
	BDHPRS91	P. C. P. Bhatt , K. Diks , T. Hagerup , V. C. Prasad , T. Radzik , S. Saxena, Improved deterministic parallel integer sorting, Information and Computation, v.94 n.1, p.29-47, Sept. 1991 [doi>10.1016/0890-5401(91)90031-V]
	Br74	Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
	CGRMR92	M. Crochemore, L. Gasieniec, W. Rytter, S. Muthukrishnan, and H. Ramesh. Fast parallel two dimensional/string pattern matching. Manuscript, 1992.
	F93	M. Farach. Personal Communication.
	FL70	Richard E. Ladner , Michael J. Fischer, Parallel Prefix Computation, Journal of the ACM (JACM), v.27 n.4, p.831-838, Oct. 1980 [doi>10.1145/322217.322232]
	Ga84	Zvi Galil, Optimal parallel algorithms for string matching, Information and Control, v.67 n.1-3, p.144-157, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80031-0]
	Ga92	Zvi Galil, A constant-time optimal parallel string-matching algorithm, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.69-76, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129720]
	Gi93	Rafaele Giancarlo, The Suffix of a square matrix, with applications, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.402-411, January 25-27, 1993, Austin, Texas, United States
	GG93	Raffaele Giancarlo , Roberto Grossi, Parallel construction and query of suffix trees for two-dimensional matrices, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.86-97, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165243]
	GMV91	Joseph Gil , Yossi Matias , Uzi Vishkin, Towards a theory of nearly constant time parallel algorithms, Proceedings of the 32nd annual symposium on Foundations of computer science, p.698-710, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185438]
	H88	T. Hagerup, On saving space in parallel computation (Note), Information Processing Letters, v.29 n.6, p.327-329, Dec. 8, 1988 [doi>10.1016/0020-0190(88)90233-5]
	H92	Torben Hagerup, The Log-Star Revolution, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.259-278, February 13-15, 1992
	H93	Torben Hagerup, Fast deterministic processor allocation, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.1-10, January 25-27, 1993, Austin, Texas, United States
	IS91	Ramana M. Idury , Alejandro A. Schäffer, Dynamic Dictionary Matching with Failure Functions (Extended Abstract), Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.276-287, April 29-May 01, 1992
	Ja92	Joseph JáJá, An introduction to parallel algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1992
	KLP89	Z. M. Kedem , G. M. Landau , K. V. Palem, Optimal parallel suffix-prefix matching algorithm and applications, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.388-398, June 18-21, 1989, Santa Fe, New Mexico, United States [doi>10.1145/72935.72977]
	KMP77	D.E. Knuth, J. Morris, V. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(1973), 323-350.
	KMR72	Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
	KP88	Zvi M. Kedem , Krishna V. Palem, Optimal parallel algorithms for forest and term matching, Theoretical Computer Science, v.93 n.2, p.245-264, 17 Feb. 1992 [doi>10.1016/0304-3975(92)90332-A]
	MP93	Mutukrishnan , K. Palem, Highly Efficient Dictionary Matching in Parallel, New York University, New York, NY, 1993
	O83	Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
	Rab93	M. Rabin. Optimal parallel pattern matching through randomization. Sequences '91: Methods in Communication, Security and Computer Science, R. Capocelli, A. De Santis and U. Vaccaro Ed., Springer-Verlag 1993.
	Vi85	Uzi Vishkin, Optimal parallel pattern matching in strings, Information and Control, v.67 n.1-3, p.91-113, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80028-0]
	Vi90	U. Vishkin, Deterministic sampling—a new technique for fast pattern matching, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.170-180, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100235]

CITED BY 3

	Raffaele Giancarlo , Roberto Grossi, Parallel construction and query of suffix trees for two-dimensional matrices, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.86-97, June 30-July 02, 1993, Velen, Germany
	Martin Farach , S. Muthukrishnan, Optimal parallel dictionary matching and compression (extended abstract), Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.244-253, June 24-26, 1995, Santa Barbara, California, United States
	Ramesh Hariharan, Optimal parallel suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.290-299, May 23-25, 1994, Montreal, Quebec, Canada