Introducing efficient parallelism into approximate string matching and a new serial algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Introducing efficient parallelism into approximate string matching and a new serial algorithm

Full text

Pdf (951 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the eighteenth annual ACM symposium on Theory of computing table of contents

Berkeley, California, United States

Pages: 220 - 230

Year of Publication: 1986

ISBN:0-89791-193-8

Authors

G M Landau	Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel
U Vishkin	Department of Computer Science, Courant Institute of Mathematical Sciences, New York University and Department of Computer Science, School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 12, Downloads (12 Months): 52, Citation Count: 13

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

	AHU-74	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	Br-74	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]
	BM-77	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	FL-80	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]
	G-84	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]
	G-85	Z. Galil, "Open problems in stringology", in A. Apostolico and Z. Galil (editors), Combinatorial Algorithms on Words, NATO ASI Series, Series F: Computer and System Sciences, Vol. 12, Springer-Verlag, 1985, 1-8.
	GS-83	Z. Galil and J.I. Seiferas, "Timespace-optimal string matching", J. Computer and System Sciences 26 (1983), 280-294.
	HT-84	Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
	I-85	A.G. Ivanov "Recognition of an approximate occurrence of words on a turing machine in real time", Math. USSR Izvestiya, Vol. 24(1985), No. 3, 479-522.
	KMP-77	D.E. Knuth, J.H. Morris and V.R. Pratt, "Fast pattern matching in strings", SIAM J. Comp. 6 (1977), 322-350.
	KR-80	R.M. Karp, and M.O. Rabin, "Efficient randomized pattemmatching algorithms", manuscript, 1980.
	LV-85a	G.M. Landau and U. Vishkin "Efficient string matching in the presence of errors", Proc. 26 IEEE FOCS, 1985, 126-136. This is a preliminary version of {LV-85b} and {LV-85c}.
	LV-85b	G M Landau , U Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, v.43 n.2-3, p.239-249, July 1986
	LV-85c	G.M. Landau and U. Vishkin "Efficient string matching with k differences", TR-36/85, Department of Computer Science, Tel Aviv University, 1985.
	LVN-85	G.M. Landau, U. Vishkin and R. Nussinov "An efficient string matching algorithm with k differences for nucleotide and amino acid sequences ", Nucleic Acids Research 1986, to appear.
	ML-84	Michael G. Main , Richard J. Lorentz, An O(n log n) algorithm for finding all repetitions in a string, Journal of Algorithms, v.5 n.3, p.422-432, Sept. 1984 [doi>10.1016/0196-6774(84)90021-X]
	S-80	P. H. Sellers, "The theory and computation of evolutionary distances: Pattern recognition", J. c,f Algorithms 1 (1980), 359-373.
	SK-83	D. Sankoff and J.B. Kruskal (editors), Time Warps, String Edits, and Macromolecules: the Theory and Practice of Sequence Comparison, Addison- Wesley, Reading, MA, 1983.
	TV-85	R.E. Tarjan and U. Vishkin, "An efficient parallel biconnectivity algorithm", SIAM J. Comput. 14,4(1985),862-874.
	U-83	Esko Ukkonen, On Approximate String Matching, Proceedings of the 1983 International FCT-Conference on Fundamentals of Computation Theory, p.487-495, August 21-27, 1983
	U-85	E. Ukkonen, "Finding approximate pattern in strings", J. of Algorithms 6 (1985), 132-137.
	V-83	U. Vishkin, "Synchronous parallel computation - a survey", TR-71, Dept. of Computer Science, Courant Institute, NYU, 1983.
	V-84	U. Vishkin, "An optimal parallel connectivity algorithm", Discrete Applied Math. 9 (1984), 197-207.
	V-85a	U. Vishkin, "On efficient parallel strong orientation", hfformation Processing Letters 20 (1985), 235-240.
	V-85b	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
	W-73	P. Weiner "Linear Pattern Matching Algorithm", Proc. 14 IEEE Symposium on Switching and Automata Theory, 1973, 1-11.
	WF-74	Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]

CITED BY 13

	Danny Dolev , Yuval Harari , Nathan Linial , Noam Nisan , Michal Parnas, Neighborhood preserving hashing and approximate queries, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.251-259, January 23-25, 1994, Arlington, Virginia, United States
	Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
	Richard Cole , Ramesh Hariharan, Dynamic LCA queries on trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.235-244, January 17-19, 1999, Baltimore, Maryland, United States
	Amihood Amir , Martin Farach, Efficient 2-dimensional approximate matching of non-rectangular figures, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.212-223, January 28-30, 1991, San Francisco, California, United States
	Richard Cole , Ramesh Hariharan, Approximate string matching: a simpler faster algorithm, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.463-472, January 25-27, 1998, San Francisco, 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
	Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
	Tugkan Batu , Funda Ergün , Joe Kilian , Avner Magen , Sofya Raskhodnikova , Ronitt Rubinfeld , Rahul Sami, A sublinear algorithm for weakly approximating edit distance, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	J. T. -L. Wang , K. Zhang , K. Jeong , D. Shasha, A System for Approximate Tree Matching, IEEE Transactions on Knowledge and Data Engineering, v.6 n.4, p.559-571, August 1994
	Mikhail J. Atallah , Florian Kerschbaum , Wenliang Du, Secure and private sequence comparisons, Proceedings of the 2003 ACM workshop on Privacy in the electronic society, October 30, 2003, Washington, DC
	Azzedine Boukerche , Alba Cristina Melo , Edans Flavius Sandes , Mauricio Ayala-Rincon, An exact parallel algorithm to compare very long biological sequences in clusters of workstations, Cluster Computing, v.10 n.2, p.187-202, June 2007
	D. Shasha , K. Zhang, Fast parallel algorithms for the unit cost editing distance between trees, Proceedings of the first annual ACM symposium on Parallel algorithms and architectures, p.117-126, June 18-21, 1989, Santa Fe, New Mexico, United States
	Benny Porat , Ely Porat , Asaf Zur, Note: Pattern matching with pair correlation distance, Theoretical Computer Science, v.407 n.1-3, p.587-590, November, 2008