Optimal parallel dictionary matching and compression (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Optimal parallel dictionary matching and compression (extended abstract)

Full text

Pdf (1.01 MB)

Source

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

Santa Barbara, California, United States

Pages: 244 - 253

Year of Publication: 1995

ISBN:0-89791-717-0

Authors

Martin Farach	Rutgers University
S. Muthukrishnan	DIMACS

Sponsors

European Theoretical :
IEEE : Institute of Electrical and Electronics Engineers
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 19, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/215399.215451 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.

	1	Sergio De Agostino, P-complete problems in data compression, Theoretical Computer Science, v.127 n.1, p.181-186, May 9, 1994 [doi>10.1016/0304-3975(94)90106-6]
	2	S~ De Agostino and J. Storer. Parallel algorithms for optimal compression using dictionaries with the prefix property. Proc. of the 2nd IEEE Data Compression Conference, pages 52-61, 1992.
	3	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]
	4	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]
	5	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
	6	O. Berkman , Z. Galil , B. Schieber , U. Vishkin, Highly parallelizable problems, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.309-319, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73036]
	7	O. Berkman and U. Vishkin. Recursive *-tree parallel data-structure. In Proco of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 196-202, 1989.
	8	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]
	9	R. Cole, M. Crochemore, Z. Galil, L. Gasieniec, K. Park, S. Muthukrishnan, H. Ramesh, and W. Rytter. Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions. Proc. of the 3$th IEEE Annual Symp. on Foundation of Computer Science# pages 248- 258, 1993~
	10	Maxime Crochemore , Wojciech Rytter, Efficient parallel algorithms to test square-freeness and factorize strings, Information Processing Letters, v.38 n.2, p.57-60, April 26, 1991 [doi>10.1016/0020-0190(91)90223-5]
	11	M. Farach and S. Muthukrishnan. An optimal, logarithmic time, randomized parallel suffix tree contruction algorithm. Technical report, DIMACS, 1995.
	12	Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
	13	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]
	14	Ho Gazit. An optimal randomized parallel algorithm for finding connected components in a graph~ In Proc. of the 27th IEEE Annual Syrup. on Foundation of Computer Science, pages 492-501# 1986.
	15	M. E. Gonzalez Smith , J. A. Storer, Parallel algorithms for data compression, Journal of the ACM (JACM), v.32 n.2, p.344-373, April 1985 [doi>10.1145/3149.3152]
	16	Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	17	Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
	18	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]
	19	D.E. Knuth, J.H. Morris, and V.R. Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6:323-350, 1977.
	20	A. Lempel and J. Ziv. On the complexity of finite sequences. IEEE Transactions on Information Theory, 22:75-81, 1976.
	21	S. Muthukrishnan. A time and space efficient algorithm for dynamic method look-up in object oriented programming languages, manuscript, 1995.
	22	S. Muthukrishnan , K. Palem, Highly efficient dictionary matching in parallel, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.69-78, June 30-July 02, 1993, Velen, Germany [doi>10.1145/165231.165239]
	23	Moni Naor, String matching with preprocessing of text and pattern, Proceedings of the 18th international colloquium on Automata, languages and programming, p.739-750, June 1991, Madrid, Spain
	24	M. Papadipoyli. A distributed dictionary matching implementation. 1994.
	25	James A. Storer, Data compression: methods and theory, Computer Science Press, Inc., New York, NY, 1987
	26	P. van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Math. Systems Theory, 10:99-127, 1977.
	27	Uzi Vishkin, Optimal Parallel Pattern Matching in Strings (Extended Summary), Proceedings of the 12th Colloquium on Automata, Languages and Programming, p.497-508, July 15-19, 1985
	28	Uzi Vishkin, Deterministic sampling: a new technique for fast pattern matching, SIAM Journal on Computing, v.20 n.1, p.22-40, Feb. 1991 [doi>10.1137/0220002]
	29	Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
	30	J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23(3):337-343, 1977.