A guided tour to approximate string matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A guided tour to approximate string matching

Full text

Pdf (1.19 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 33 , Issue 1 (March 2001) table of contents

Pages: 31 - 88

Year of Publication: 2001

ISSN:0360-0300

Author

Gonzalo Navarro

Univ. of Chile, Santiago, Chile

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 116, Downloads (12 Months): 1092, Citation Count: 124

Additional Information:

abstract references cited by index terms review 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/375360.375365 What is a DOI?

ABSTRACT

We survey the current techniques to cope with the problem of string matching that allows errors. This is becoming a more and more relevant issue for many fast growing areas such as information retrieval and computational biology. We focus on online searching and mostly on edit distance, explaining the problem and its relevance, its statistical behavior, its history and current developments, and the central ideas of the algorithms and their complexities. We present a number of experiments to compare the performance of the different algorithms and show which are the best choices. We conclude with some directions for future work and open problems.

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	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]
	2	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	3	ALTSCHUL, S., GISH, W., MILLER, W., MYERS,G.,AND LIPMAN, D. 1990. Basic local alignment search tool. J. Mol. Biol. 215, 403-410.
	4	Amihood Amir , Moshe Lewenstein , Noa Lewenstein, Pattern Matching In Hypertext, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.160-173, August 06-08, 1997
	5	A. Amir , Y. Aumann , G. M. Landau , M. Lewenstein , N. Lewenstein, Pattern matching with swaps, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.144, October 19-22, 1997
	6	APOSTOLICO, A. 1985. The myriad virtues of subword trees. In Combinatorial Algorithms on Words. Springer-Verlag, Barlin, 85-96.
	7	Alberto Apostolico , Zvi Galil, Combinatorial Algorithms on Words, Springer-Verlag New York, Inc., Secaucus, NJ, 1985
	8	Alberto Apostolico , Zvi Galil, Pattern matching algorithms, Oxford University Press, Oxford, 1997
	9	APOSTOLICO,A.AND GUERRA, C. 1987. The Longest Common Subsequence problem revisited. Algorithmica 2, 315-336.
	10	ARAUJO, M., NAVARRO,G.,AND ZIVIANI, N. 1997. Large text searching allowing errors. In Proceedings of the 4th South American Workshop on String Processing (WSP '97), Carleton Univ. Press. 2-20.
	11	ARLAZAROV, V., DINIC, E., KONROD, M., AND FARADZEV, I. 1975. On economic construction of the transitive closure of a directed graph. Sov. Math. Dokl. 11, 1209, 1210. Original in Russian in Dokl. Akad. Nauk SSSR 194, 1970.
	12	ATALLAH, M., JACQUET,P.,AND SZPANKOWSKI, W. 1993. A probabilistic approach to pattern matching with mismatches. Random Struct. Algor. 4, 191- 213.
	13	R. L. Baeza-Yates, Efficient text searching, University of Waterloo, Waterloo, Ont., Canada, 1989
	14	BAEZA-YATES, R. 1991. Some new results on approximate string matching. In Workshop on Data Structures, Dagstuhl, Germany. Abstract.
	15	Ricardo A. Baeza-Yates, Text-Retrieval: Theory and Practice, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.465-476, September 07-11, 1992
	16	Ricardo A. Baeza-Yates, A Unified View to String Matching Algorithms, Proceedings of the 23rd Seminar on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics, p.1-15, November 23-30, 1996
	17	Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992 [doi>10.1145/135239.135243]
	18	BAEZA-YATES,R.AND GONNET, G. 1994. Fast string matching with mismatches. Information and Computation 108, 2, 187-199. Preliminary version as Tech. Rep. CS-88-36, Data Structuring Group, Univ. of Waterloo, Sept. 1988.
	19	Ricardo A. Baeza-Yates , Gonzalo Navarro, Multiple Approximate String Matching, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.174-184, August 06-08, 1997
	20	BAEZA-YATES,R.AND NAVARRO, G. 1998. New and faster filters for multiple approximate string matching. Tech. Rep. TR/DCC-98-10, Dept. of Computer Science, University of Chile. Random Struct. Algor. to appear. ftp://ftp. dcc.ptuchile.cl/pub/users/gnavarro/multi. ps.gz.
	21	Ricardo A. Baeza-Yates , Gonzalo Navarro, A Faster Algorithm for Approximate String Matching, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.1-23, June 10-12, 1996
	22	Ricardo Baeza-Yates , Gonzalo Nevarro, Block addressing indices for approximate text retrieval, Journal of the American Society for Information Science, v.51 n.1, p.69-82, Jan. 2000 [doi>10.1002/(SICI)1097-4571(2000)51:1<69::AID-ASI10>3.0.CO;2-C]
	23	Ricardo A. Baeza-Yates , Chris H. Perleberg, Fast and practical approximate string matching, Information Processing Letters, v.59 n.1, p.21-27, July 8, 1996 [doi>10.1016/0020-0190(96)00083-X]
	24	R. Baeza-Yates , M. Régnier, Fast algorithms for two-dimensional and multiple pattern matching (preliminary version), Proceedings of the second Scandinavian workshop on Algorithm theory, p.332-347, July 1990, Bergen, Sweden
	25	Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
	26	BLUMER, A., BLUMER, J., HAUSSLER, D., EHRENFEUCHT, A., CHEN, M., AND SEIFERAS, J. 1985. The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 31-55.
	27	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]
	28	William I. Chang , Jordan Lampe, Theoretical and Empirical Comparisons of Approximate String Matching Algorithms, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.175-184, April 29-May 01, 1992
	29	CHANG,W.AND LAWLER, E. 1994. Sublinear approximate string matching and biological applications. Algorithmica 12, 4/5, 327-344. Preliminary version in FOCS '90.
	30	William I. Chang , Thomas G. Marr, Approximate String Matching and Local Similarity, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.259-273, June 05-08, 1994
	31	CHVATAL,V.AND SANKOFF, D. 1975. Longest common subsequences of two random sequences. J. Appl. Probab. 12, 306-315.
	32	COBBS, A. 1995. Fast approximate matching using suffix trees. In Proceedings of the 6th Annual Symposium on Combinatorial Pattern Matching (CPM '95), 41-54.
	33	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
	34	Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
	35	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	36	Maxime Crochemore, Transducers and repetitions, Theoretical Computer Science, v.45 n.1, p.63-86, Sept. 1986
	37	Maxime Crochemore , Wojciech Rytter, Text algorithms, Oxford University Press, Inc., New York, NY, 1994
	38	CROCHEMORE, M., CZUMAJ, A., GASIENIEC, L., JAROMINEK, S., LECROQ, T., PLANDOWSKI,W.,AND RYTTER,W. 1994. Speeding up two string-matching algorithms. Algorithmica 12, 247-267.
	39	Fred J. Damerau, A technique for computer detection and correction of spelling errors, Communications of the ACM, v.7 n.3, p.171-176, March 1964 [doi>10.1145/363958.363994]
	40	Gautam Das , Rudolf Fleischer , Leszek Gasieniec , Dimitrios Gunopulos , Juha Kärkkäinen, Episode Matching, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.12-27, June 30-July 02, 1997
	41	DEKEN, J. 1979. Some limit results for longest common subsequences. Discrete Math. 26, 17-31.
	42	N. Rex Dixon , Thomas B. Martin, Automatic Speech and Speaker Recognition, John Wiley & Sons, Inc., New York, NY, 1979
	43	A. Ehrenfeucht , D. Haussler, A new distance metric on strings computable in linear time, Discrete Applied Mathematics, v.20 n.3, p.191-203, July, 1988 [doi>10.1016/0166-218X(88)90076-5]
	44	D. G. Elliman , I. T. Lancaster, A review of segmentation and contextual analysis techniques for text recognition, Pattern Recognition, v.23 n.3-4, p.337-346, March 1990 [doi>10.1016/0031-3203(90)90021-C]
	45	James C. French , Allison L. Powell , Eric Schulman, Applications of approximate word matching in information retrieval, Proceedings of the sixth international conference on Information and knowledge management, p.9-15, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266721]
	46	Z. Galil , R. Giancarlo, Data structures and algorithms for approximate string matching, Journal of Complexity, v.4 n.1, p.33-72, March 1988 [doi>10.1016/0885-064X(88)90008-8]
	47	Zvi Galil , Kunsoo Park, An improved algorithm for approximate string matching, SIAM Journal on Computing, v.19 n.6, p.989-999, Dec. 1990 [doi>10.1137/0219067]
	48	GIEGERICH, R., KURTZ, S., HISCHKE,F.,AND OHLEBUSCH, E. 1997. A general technique to improve filter algorithms for approximate string matching. In Proceedings of the 4th South American Workshop on String Processing (WSP '97). Carleton Univ. Press. 38-52. Preliminary version as Tech. Rep. 96-01, Universit at Bielefeld, Germany, 1996.
	49	GONNET, G. 1992. A tutorial introduction to Computational Biochemistry using Darwin. Tech. rep., Informatik E. T. H., Zuerich, Switzerland.
	50	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	51	GONZALEZ,R.AND THOMASON, M. 1978. Syntactic Pattern Recognition. Addison-Wesley, Reading, MA.
	52	James Gosling, A redisplay algorithm, Proceedings of the ACM SIGPLAN SIGOA symposium on Text manipulation, p.123-129, June 08-10, 1981, Portland, Oregon, United States
	53	GROSSI,R.AND LUCCIO, F. 1989. Simple and efficient string matching with k mismatches. Inf. Process. Lett. 33, 3, 113-120.
	54	Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
	55	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980 [doi>10.1145/356827.356830]
	56	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]
	57	Paul Heckel, A technique for isolating differences between files, Communications of the ACM, v.21 n.4, p.264-268, April 1978 [doi>10.1145/359460.359467]
	58	HOLSTI,N.AND SUTINEN, E. 1994. Approximate string matching using q-gram places. In Proceedings of 7th Finnish Symposium on Computer Science. Univ. of Joensuu. 23-32.
	59	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	60	HORSPOOL, R. 1980. Practical fast searching in strings. Software Practice Exper. 10, 501-506.
	61	JOKINEN,P.AND UKKONEN, E. 1991. Two algorithms for approximate string matching in static texts. In Proceedings of the 2nd Mathematical Foundations of Computer Science (MFCS '91). Springer- Verlag, Berlin, vol. 16, 240-248.
	62	Petteri Jokinen , Jorma Tarhio , Esko Ukkonen, A comparison of approximate string matching algorithms, Software—Practice & Experience, v.26 n.12, p.1439-1458, Dec. 1996 [doi>10.1002/(SICI)1097-024X(199612)26:12<1439::AID-SPE71>3.0.CO;2-1]
	63	Howard Karloff, Fast algorithms for approximately counting mismatches, Information Processing Letters, v.48 n.2, p.53-60, Nov. 8, 1993 [doi>10.1016/0020-0190(93)90177-B]
	64	KECECIOGLU,J.AND SANKOFF, D. 1995. Exact and approximation algorithms for the inversion distance between two permutations. Algorithmica 13, 180-210.
	65	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	66	KNUTH, D., MORRIS, J., JR, AND PRATT, V. 1977. Fast pattern matching in strings. SIAM J. Com-put. 6, 1, 323-350.
	67	Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992 [doi>10.1145/146370.146380]
	68	KUMAR,S.AND SPAFFORD, E. 1994. A patternmatching model for intrusion detection. In Proceedings of the National Computer Security Conference, 11-21.
	69	KURTZ, S. 1996. Approximate string searching under weighted edit distance. In Proceedings of the 3rd South American Workshop on String Processing (WSP '96). Carleton Univ. Press. 156- 170.
	70	Stefan Kurtz , Gene Myers, Estimating the Probability of Approximate Matches, Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.52-64, June 30-July 02, 1997
	71	Gad M. Landau , Uzi Vishkin, Fast string matching with k-differences, Journal of Computer and System Sciences, v.37 n.1, p.63-78, August 1988 [doi>10.1016/0022-0000(88)90045-1]
	72	G. M. Landau , U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, v.10 n.2, p.157-169, June 1989 [doi>10.1016/0196-6774(89)90010-2]
	73	Gad M. Landau , Eugene W. Myers , Jeanette P. Schmidt, Incremental String Comparison, SIAM Journal on Computing, v.27 n.2, p.557-582, April 1998 [doi>10.1137/S0097539794264810]
	74	LAWRENCE,S.AND GILES, C. L. 1999. Accessibility of information on the web. Nature 400, 107-109.
	75	Jee-Soo Lee , Dong Kyue Kim , Kunsoo Park , Yookun Cho, Efficient Algorithms for Approximate String Matching with Swaps (Extended Abstract), Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching, p.28-39, June 30-July 02, 1997
	76	LEVENSHTEIN, V. 1965. Binary codes capable of correcting spurious insertions and deletions of ones. Probl. Inf. Transmission 1, 8-17.
	77	LEVENSHTEIN, V. 1966. Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl. 10, 8, 707-710. Original in Russian in Dokl. Akad. Nauk SSSR 163, 4, 845-848, 1965.
	78	LIPTON,R.AND LOPRESTI, D. 1985. A systolic array for rapid string comparison. In Proceedings of the Chapel Hill Conference on VLSI, 363- 376.
	79	LOPRESTI,D.AND TOMKINS, A. 1994. On the search-ability of electronic ink. In Proceedings of the 4th International Workshop on Frontiers in Handwriting Recognition, 156-165.
	80	Daniel Lopresti , Andrew Tomkins, Block edit models for approximate string matching, Theoretical Computer Science, v.181 n.1, p.159-179, July 15, 1997 [doi>10.1016/S0304-3975(96)00268-X]
	81	Robert A. Wagner , Roy Lowrance, An Extension of the String-to-String Correction Problem, Journal of the ACM (JACM), v.22 n.2, p.177-183, April 1975 [doi>10.1145/321879.321880]
	82	LUCZAK,T.AND SZPANKOWSKI, W. 1997. A suboptimal lossy data compression based on approximate pattern matching. IEEE Trans. Inf. Theor. 43, 1439-1451.
	83	MANBER,U.AND WU, S. 1994. GLIMPSE: A tool to search through entire file systems. In Proceedings of USENIX Technical Conference. USENIX Association, Berkeley, CA, USA. 23-32. Preliminary version as Tech. Rep. 93-34, Dept. of Computer Science, Univ. of Arizona, Oct. 1993.
	84	MASEK,W.AND PATERSON, M. 1980. A faster algorithm for computing string edit distances. J. Comput. Syst. Sci. 20, 18-31.
	85	MASTERS, H. 1927. A study of spelling errors. Univ. of Iowa Studies in Educ. 4,4.
	86	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	87	MELICHAR, B. 1996. String matching with k differences by finite automata. In Proceedings of the International Congress on Pattern Recognition (ICPR '96). IEEE CS Press, Silver Spring, MD. 256-260. Preliminary version in Computer Anal-ysis of Images and Patterns (LNCS, vol. 970, 1995).
	88	Donald R. Morrison, PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric, Journal of the ACM (JACM), v.15 n.4, p.514-534, Oct. 1968 [doi>10.1145/321479.321481]
	89	Robert Muth , Udi Manber, Approximate Multiple Strings Search, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.75-86, June 10-12, 1996
	90	MYERS, G. 1994a. A sublinear algorithm for approximate keyword searching. Algorithmica 12, 4/5, 345-374. Perliminary version in Tech. Rep. TR90-25, Computer Science Dept., Univ. of Arizona, Sept. 1991.
	91	MYERS, G. 1994b. Algorithmic Advances for Searching Biosequence Databases. Plenum Press, New York, 121-135.
	92	MYERS, G. 1986a. Incremental alignment algorithms and their applications. Tech. Rep. 86-22, Dept. of Computer Science, Univ. of Arizona.
	93	MYERS, G. 1986b. An O(ND) difference algorithm and its variations. Algorithmica 1, 251-266.
	94	MYERS, G. 1991. An overview of sequence comparison algorithms in molecular biology. Tech. Rep. TR-91-29, Dept. of Computer Science, Univ. of Arizona.
	95	Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM (JACM), v.46 n.3, p.395-415, May 1999 [doi>10.1145/316542.316550]
	96	NAVARRO, G. 1997a. Multiple approximate string matching by counting. In Proceedings of the 4th South American Workshop on String Processing (WSP '97). Carleton Univ. Press, 125-139.
	97	NAVARRO, G. 1997b. A partial deterministic automaton for approximate string matching. In Proceedings of the 4th South American Workshop on String Processing (WSP '97). Carleton Univ. Press, 112-124.
	98	NAVARRO, G. 1998. Approximate Text Searching. Ph.D. thesis, Dept. of Computer Science, Univ. of Chile. Tech. Rep. TR/DCC-98-14. ftp://ftp. dcc.uchile.cl/pub/users/gnavarro/thesis98. ps.gz.
	99	Gonzalo Navarro, Improved approximate pattern matching on hypertext, Theoretical Computer Science, v.237 n.1-2, p.455-463, April 28, 2000 [doi>10.1016/S0304-3975(99)00333-3]
	100	NAVARRO, G. 2000b. Nrgrep: A fast and flexible pattern matching tool, Tech. Rep. TR/DCC-2000-3. Dept. of Computer Science, Univ. of Chile, Aug. ftp://ftp.dcc.uchile.cl/pub/users/gnavarro/ nrgrep.ps.gz.
	101	NAVARRO,G.AND BAEZA-YATES, R. 1998a. Improving an algorithm for approximate pattern matching. Tech. Rep. TR/DCC-98- 5, Dept. of Computer Science, Univ. of Chile. Algorithmica, to appear. ftp:// ftp.dcc.uchile.cl/pub/users/gnavarro/dexp. ps.gz.
	102	NAVARRO,G.AND BAEZA-YATES, R. 1998b. A practical q-gram index for text retrieval allowing errors. CLEI Electron. J. 1,2.http://www.clei.cl.
	103	Gonzalo Navarro , Ricardo A. Baeza-Yates, Fast Multi-dimensional Approximate Pattern Matching, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.243-257, July 22-24, 1999
	104	Gonzalo Navarro , Ricardo A. Baeza-Yates, A New Indexing Method for Approximate String Matching, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.163-185, July 22-24, 1999
	105	Gonzalo Navarro , Ricardo Baeza-Yates, Very fast and simple approximate string matching, Information Processing Letters, v.72 n.1-2, p.65-70, Oct. 29, 1999 [doi>10.1016/S0020-0190(99)00121-0]
	106	Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000 [doi>10.1145/351827.384246]
	107	Gonzalo Navarro , Edleno Silva De Moura , Marden Neubert , Nivio Ziviani , Ricardo Baeza-Yates, Adding Compression to Block Addressing Inverted Indexes, Information Retrieval, v.3 n.1, p.49-77, July 2000 [doi>10.1023/A:1009934302807]
	108	NEEDLEMAN,S.AND WUNSCH, C. 1970. A general method applicable to the search for similarities in the amino acid sequences of two proteins. J. Mol. Biol. 48, 444-453.
	109	John C Nesbit, The accuracy of approximate string matching algorithms, Journal of Computer Based Instruction, v.13 n.3, p.80-83, Summer 1986
	110	O. Owolabi , D. R. McGregor, Fast approximate string matching, Software—Practice & Experience, v.18 n.4, p.387-393, April, 1988 [doi>10.1002/spe.4380180407]
	111	M. Régnier , W. Szpankowski, On the Approximate Pattern Occurrences in a Text, Proceedings of the Compression and Complexity of Sequences 1997, p.253, June 11-13, 1997
	112	RIVEST, R. 1976. Partial-match retrieval algorithms. SIAM J. Comput. 5,1.
	113	SAHINALP,S.AND VISHKIN, U. 1997. Approximate pattern matching using locally consistent parsing. Manuscript, Univ. of Maryland Institute for Advanced Computer Studies (UMIACS).
	114	SANKOFF, D. 1972. Matching sequences under deletion/insertion constraints. In Proceedings of the National Academy of Sciences of the USA, vol. 69, 4-6.
	115	SANKOFF,D.AND KRUSKAL, J., Eds. 1983. Time Warps, String Edits, and Macromolecules: The Theory and Practice of Sequence Comparison. Addison-Wesley, Reading, MA.
	116	SANKOFF,D.AND MAINVILLE, S. 1983. Common Subsequences and Monotone Subsequences. Addison-Wesley, Reading, MA, 363-365.
	117	Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
	118	SELLERS, P. 1974. On the theory and computation of evolutionary distances. SIAM J. Appl. Math. 26, 787-793.
	119	SELLERS, P. 1980. The theory and computation of evolutionary distances: pattern recognition. J. Algor. 1, 359-373.
	120	SHI, F. 1996. Fast approximate string matching with q-blocks sequences. In Proceedings of the 3rd South American Workshop on String Processing (WSP'96). Carleton Univ. Press. 257- 271.
	121	Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990 [doi>10.1145/79173.79184]
	122	SUTINEN, E. 1998. Approximate Pattern Matching with the q-Gram Family. Ph.D. thesis, Dept. of Computer Science, Univ. of Helsinki, Finland. Tech. Rep. A-1998-3.
	123	Erkki Sutinen , Jorma Tarhio, On Using q-Gram Locations in Approximate String Matching, Proceedings of the Third Annual European Symposium on Algorithms, p.327-340, September 25-27, 1995
	124	Erkki Sutinen , Jorma Tarhio, Filtration with q-Samples in Approximate String Matching, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.50-63, June 10-12, 1996
	125	Tadao Takaoka, Approximate Pattern Matching with Samples, Proceedings of the 5th International Symposium on Algorithms and Computation, p.234-242, August 25-27, 1994
	126	J. Tarhio , E. Ukkonen, A greedy approximation algorithm for constructing shortest common superstrings, Theoretical Computer Science, v.57 n.1, p.131-145, April 1988 [doi>10.1016/0304-3975(88)90167-3]
	127	Jorma Tarhio , Esko Ukkonen, Approximate Boyer-Moore string matching, SIAM Journal on Computing, v.22 n.2, p.243-260, April 1993 [doi>10.1137/0222018]
	128	Walter F. Tichy, The string-to-string correction problem with block moves, ACM Transactions on Computer Systems (TOCS), v.2 n.4, p.309-321, Nov. 1984 [doi>10.1145/357401.357404]
	129	Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985 [doi>10.1016/S0019-9958(85)80046-2]
	130	UKKONEN, E. 1985b. Finding approximate patterns in strings. J. Algor. 6, 132-137.
	131	Esko Ukkonen, Approximate string-matching with q-grams and maximal matches, Theoretical Computer Science, v.92 n.1, p.191-211, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90143-4]
	132	Esko Ukkonen, Approximate String-Matching over Suffix Trees, Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching, p.228-242, June 02-04, 1993
	133	UKKONEN, E. 1995. Constructing suffix trees online in linear time. Algorithmica 14, 3, 249- 260.
	134	UKKONEN,E.AND WOOD, D. 1993. Approximate string matching with suffix automata. Algorithmica 10, 353-364. Preliminary version in Rep. A-1990-4, Dept. of Computer Science, Univ. of Helsinki, Apr. 1990.
	135	ULLMAN, J. 1977. A binary n-gram technique for automatic correction of substitution, deletion, insertion and reversal errors in words. Comput. J. 10, 141-147.
	136	VINTSYUK, T. 1968. Speech discrimination by dynamic programming. Cybernetics 4, 52-58.
	137	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]
	138	WATERMAN, M. 1995. Introduction to Computational Biology. Chapman and Hall, London.
	139	WEINER, P. 1973. Linear pattern matching algorithms. In Proceedings of IEEE Symposium on Switching and Automata Theory, 1-11.
	140	Alden H. Wright, Approximate string matching using within-word parallelism, Software—Practice & Experience, v.24 n.4, p.337-362, April 1994 [doi>10.1002/spe.4380240402]
	141	WU,S.AND MANBER, U. 1992a. Agrepfia fast approximate pattern-matching tool. In Proceedings of USENIX Technical Conference. USENIX Association, Berkeley, CA, USA. 153-162.
	142	Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
	143	Sun Wu , Udi Manber , Eugene Myers, A subquadratic algorithm for approximate regular expression matching, Journal of Algorithms, v.19 n.3, p.346-360, Nov. 1995 [doi>10.1006/jagm.1995.1041]
	144	WU, S., MANBER,U.,AND MYERS, E. 1996. A subquadratic algorithm for approximate limited expression matching. Algorithmica 15,1,50- 67. Preliminary version as Tech. Rep. TR29-36, Computer Science Dept., Univ. of Arizona, 1992.
	145	YAO, A. 1979. The complexity of pattern matching for a random string. SIAM J. Comput. 8, 368- 387.
	146	Tieng K. Yap , Ophir Frieder , Robert L. Martino, High Performance Computational Methods for Biological Sequence Analysis, Kluwer Academic Publishers, Norwell, MA, 1996
	147	Justin Zobel , Philip Dart, Phonetic string matching: lessons from information retrieval, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.166-172, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243258]

CITED BY 124

	Federica Mandreoli , Riccardo Martoglia , Paolo Tiberio, A syntactic approach for searching similarities within sentences, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Ying Xu , Lusheng Wang , Hao Zhao , Jianping Li, Exact matching of RNA secondary structure patterns, Theoretical Computer Science, v.335 n.1, p.53-66, 20 May 2005
	Sunita Sarawagi , Anuradha Bhamidipaty, Interactive deduplication using active learning, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada
	Gonzalo Navarro , Ricardo Baeza-Yates , João Marcelo Azevedo Arcoverde, Matchsimile: a flexible approximate matching tool for searching proper names, Journal of the American Society for Information Science and Technology, v.54 n.1, p.3-15, January 2003
	Luis Gravano , Panagiotis G. Ipeirotis , Nick Koudas , Divesh Srivastava, Text joins in an RDBMS for web data integration, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary
	Ricardo Baeza-Yates , Gonzalo Navarro, New and faster filters for multiple approximate string matching, Random Structures & Algorithms, v.20 n.1, p.23-49, January 2002
	Jun Sun , Zhulong Wang , Hao Yu , Fumihito Nishino , Yukata Katsuyama , Satoshi Naoi, Effective text extraction and recognition for WWW images, Proceedings of the 2003 ACM symposium on Document engineering, November 20-22, 2003, Grenoble, France
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, Performance evaluation of load balancing strategies for approximate string matching application on an MPI cluster of heterogeneous workstations, Future Generation Computer Systems, v.19 n.7, p.1075-1104, October 2003
	Josué Kuri , Gonzalo Navarro , Ludovic Mé, Fast multipattern search algorithms for intrusion detection, Fundamenta Informaticae, v.56 n.1,2, p.23-49, July 2003
	Stefan Burkhardt , Juha Kärkkäinen, Better filtering with gapped q-grams, Fundamenta Informaticae, v.56 n.1,2, p.51-70, July 2003
	Gonzalo Navarro, Regular expression searching on compressed text, Journal of Discrete Algorithms, v.1 n.5-6, p.423-443, October 2003
	Changsheng Xu , Xi Shao , Namunu C. Maddage , Mohan S. Kankanhalli, Automatic music video summarization based on audio-visual-text analysis and alignment, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
	Juha Kärkkäinen , Gonzalo Navarro , Esko Ukkonen, Approximate string matching on Ziv-Lempel compressed text, Journal of Discrete Algorithms, v.1 n.3-4, p.313-338, June 2003
	Ying Xu , Lusheng Wang , Xiaotie Deng, Exact pattern matching for RNA secondary structures, Proceedings of the second conference on Asia-Pacific bioinformatics, p.257-263, January 01, 2004, Dunedin, New Zealand
	Yoshimasa Tsuruoka , Jun'ichi Tsujii, Probabilistic term variant generator for biomedical terms, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada
	Masayuki Takeda , Tomoko Fukuda , Ichiro Nanri , Mayumi Yamasaki , Koichi Tamari, Discovering instances of poetic allusion from anthologies of classical Japanese poems, Theoretical Computer Science, v.292 n.2, p.497-524, 27 January 2003
	Takao MIURA , Isamu SHIOYA, Similarity among melodies for music information retrieval, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Gonzalo Navarro, Approximate regular expression searching with arbitrary integer weights, Nordic Journal of Computing, v.11 n.4, p.356-373, December 2004
	Ching-Fung Cheung , Jeffrey Xu Yu , Hongjun Lu, Constructing Suffix Tree for Gigabyte Sequences with Megabyte Memory, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.90-105, January 2005
	Indrajit Bhattacharya , Lise Getoor, Iterative record linkage for cleaning and integration, Proceedings of the 9th ACM SIGMOD workshop on Research issues in data mining and knowledge discovery, June 13, 2004, Paris, France
	Melanie Weis , Felix Naumann, Detecting duplicate objects in XML documents, Proceedings of the 2004 international workshop on Information quality in information systems, June 18, 2004, Paris, France
	Christine M. O'Keefe , Ming Yung , Lifang Gu , Rohan Baxter, Privacy-preserving data linkage protocols, Proceedings of the 2004 ACM workshop on Privacy in the electronic society, October 28-28, 2004, Washington DC, USA
	Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000
	Arne Halaas , Børge Svingen , Magnar Nedland , Pål Sætrom , Ola Snøve, Jr. , Olaf René Birkeland, A recursive MISD architecture for pattern matching, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.727-734, July 2004
	Bijit Hore , Hakan Hacigumus , Bala Iyer , Sharad Mehrotra, Indexing text data under space constraints, Proceedings of the thirteenth ACM international conference on Information and knowledge management, November 08-13, 2004, Washington, D.C., USA
	Namunu C. Maddage , Changsheng Xu , Mohan S. Kankanhalli , Xi Shao, Content-based music structure analysis with applications to music semantics understanding, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
	William E. Winkler, Methods for evaluating and creating data quality, Information Systems, v.29 n.7, p.531-550, October 2004
	Yoshimasa Tsuruoka , Jun'ichi Tsujii, Improving the performance of dictionary-based approaches in protein name recognition, Journal of Biomedical Informatics, v.37 n.6, p.461-470, December 2004
	Kimmo Fredriksson , Gonzalo Navarro, Average-optimal single and multiple approximate string matching, Journal of Experimental Algorithmics (JEA), v.9 n.es, 2004
	Min-Soo Kim , Kyu-Young Whang , Jae-Gil Lee , Min-Jae Lee, n-gram/2L: a space and time efficient two-level n-gram inverted index structure, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Moninder Singh , Jayant R. Kalagnanam , Sudhir Verma , Amit J. Shah , Swaroop K. Chalasani, Automated cleansing for spend analytics, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany
	Nikolaus Augsten , Michael Böhlen , Johann Gamper, Approximate matching of hierarchical data using pq-grams, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Xifeng Yan , Philip S. Yu , Jiawei Han, Substructure similarity search in graph databases, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland
	E. Sutinen , J. Tarhio, Approximate string matching with ordered q-grams, Nordic Journal of Computing, v.11 n.4, p.321-343, December 2004
	Bodo Manthey , Rüdiger Reischuk, The intractability of computing the Hamming distance, Theoretical Computer Science, v.337 n.1-3, p.331-346, 9 June 2005
	Eike Schallehn , Kai-Uwe Sattler , Gunter Saake, Efficient similarity-based operations for data integration, Data & Knowledge Engineering, v.48 n.3, p.361-387, March 2004
	Indrajit Bhattacharya , Lise Getoor, Relational clustering for multi-type entity resolution, Proceedings of the 4th international workshop on Multi-relational mining, p.3-12, August 21-21, 2005, Chicago, Illinois
	K. Perdikuri , C. Makris , A. Tsakalidis, Discovering regularities in biosequences: challenges and applications, Proceedings of the international conference on Computational methods in sciences and engineering, p.500-503, September 12-16, 2003, Kastoria, Greece
	Yoshimasa Tsuruoka , Jun'ichi Tsujii, Boosting precision and recall of dictionary-based protein name recognition, Proceedings of the ACL 2003 workshop on Natural language processing in biomedicine, p.41-48, July 11-11, 2003, Sapporo, Japan
	Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Integrating XML data sources using approximate joins, ACM Transactions on Database Systems (TODS), v.31 n.1, p.161-207, March 2006
	Uwe Quasthoff , Christian Biemann , Christian Wolff, Named entity learning and verification: expectation maximization in large corpora, proceeding of the 6th conference on Natural language learning, p.1-7, August 31, 2002
	Christian Bird , Alex Gourley , Prem Devanbu , Michael Gertz , Anand Swaminathan, Mining email social networks, Proceedings of the 2006 international workshop on Mining software repositories, May 22-23, 2006, Shanghai, China
	Trinh N. D. Huynh , Wing-Kai Hon , Tak-Wah Lam , Wing-Kin Sung, Approximate string matching using compressed suffix arrays, Theoretical Computer Science, v.352 n.1, p.240-249, 7 March 2006
	Gonzalo Navarro , Edgar Chávez, A metric index for approximate string matching, Theoretical Computer Science, v.352 n.1, p.266-279, 7 March 2006
	Sudipto Guha , H. V. Jagadish , Nick Koudas , Divesh Srivastava , Ting Yu, Approximate XML joins, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Federica Mandreoli , Riccardo Martoglia , Paolo Tiberio, EXTRA: a system for example-based translation assistance, Machine Translation, v.20 n.3, p.167-197, September 2006
	A. M. Sokolov, Vector representations for efficient comparison and search for similar strings, Cybernetics and Systems Analysis, v.43 n.4, p.484-498, July 2007
	Lin Xu , Curtis Dyreson, Approximate retrieval of XML data with ApproXPath, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
	Chen Li , Bin Wang , Xiaochun Yang, VGRAM: improving performance of approximate queries on string collections using variable-length grams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, Database indexing for large DNA and protein sequence collections, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.3, p.256-271, November 2002
	Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.523-544, October 2007
	Sebastian Deorowicz, Speeding up transposition-invariant string matching, Information Processing Letters, v.100 n.1, p.14-20, 16 October 2006
	Stoyan Mihov , Klaus U. Schulz, Fast Approximate Search in Large Dictionaries, Computational Linguistics, v.30 n.4, p.451-477, December 2004
	Anni Järvelin , Antti Järvelin , Kalervo Järvelin, s-grams: Defining generalized n-grams for information retrieval, Information Processing and Management: an International Journal, v.43 n.4, p.1005-1019, July, 2007
	Indrajit Bhattacharya , Lise Getoor, Collective entity resolution in relational data, ACM Transactions on Knowledge Discovery from Data (TKDD), v.1 n.1, p.5-es, March 2007
	Heikki Hyyrö , Kimmo Fredriksson , Gonzalo Navarro, Increased bit-parallelism for approximate and multiple string matching, Journal of Experimental Algorithmics (JEA), 10, 2005
	Atsuhiro Takasu, An approximate multi-word matching algorithm for robust document retrieval, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Sreenivas Gollapudi , Rina Panigrahy, A dictionary for approximate string search and longest prefix search, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA
	Xifeng Yan , Feida Zhu , Philip S. Yu , Jiawei Han, Feature-based similarity search in graph structures, ACM Transactions on Database Systems (TODS), v.31 n.4, p.1418-1453, December 2006
	Hong-Hai Do , Erhard Rahm, Matching large schemas: Approaches and evaluation, Information Systems, v.32 n.6, p.857-885, September, 2007
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, A programmable array processor architecture for flexible approximate string matching algorithms, Journal of Parallel and Distributed Computing, v.67 n.2, p.131-141, February, 2007
	Shengfeng Tian , Shaomin Mu , Chuanhuan Yin, Sequence-similarity kernels for SVMs to detect anomalies in system calls, Neurocomputing, v.70 n.4-6, p.859-866, January, 2007
	Changsheng Xu , Namunu C. Maddage , Xi Shao , Qi Tian, Content-adaptive digital music watermarking based on music structure analysis, ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP), v.3 n.1, p.1-es, February 2007
	G. Tremblay , F. Champagne, Marking musical dictations using the edit distance algorithm, Software—Practice & Experience, v.37 n.2, p.207-230, February 2007
	Cédric du Mouza , Philippe Rigaux , Michel Scholl, Parameterized pattern queries, Data & Knowledge Engineering, v.63 n.2, p.433-456, November, 2007
	Ying-Dar Lin , Kuo-Kun Tseng , Tsern-Huei Lee , Yi-Neng Lin , Chen-Chou Hung , Yuan-Cheng Lai, A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.12, p.937-950, December, 2007
	Hongrae Lee , Raymond T. Ng , Kyuseok Shim, Extending q-grams to estimate selectivity of string matching with low edit distance, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
	Shengfeng Tian , Shaomin Mu , Chuanhuan Yin, Length-weighted string kernels for sequence data classification, Pattern Recognition Letters, v.28 n.13, p.1651-1656, October, 2007
	Jeremy Ey, Simulating regional medical record systems (student poster), Proceedings of the 45th annual southeast regional conference, March 23-24, 2007, Winston-Salem, North Carolina
	Arturas Mazeika , Michael H. Böhlen , Nick Koudas , Divesh Srivastava, Estimating the selectivity of approximate string queries, ACM Transactions on Database Systems (TODS), v.32 n.2, p.12-es, June 2007
	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
	Gonzalo Navarro, Searching in metric spaces by spatial approximation, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.1, p.28-46, August 2002
	Krister Lindén, Multilingual modeling of cross-lingual spelling variants, Information Retrieval, v.9 n.3, p.295-310, June 2006
	Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, A Database Index to Large Biological Sequences, Proceedings of the 27th International Conference on Very Large Data Bases, p.139-148, September 11-14, 2001
	Luis Gravano , Panagiotis G. Ipeirotis , H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Divesh Srivastava, Approximate String Joins in a Database (Almost) for Free, Proceedings of the 27th International Conference on Very Large Data Bases, p.491-500, September 11-14, 2001
	Moritz G. Maaí , Johannes Nowak, Text indexing with errors, Journal of Discrete Algorithms, v.5 n.4, p.662-681, December, 2007
	Rodolfo Bezerra Batista , Azzedine Boukerche , Alba Cristina Magalhaes Alves de Melo, A parallel strategy for biological sequence alignment in restricted memory space, Journal of Parallel and Distributed Computing, v.68 n.4, p.548-561, April, 2008
	Shaoxu Song , Lei Chen, Probabilistic correlation-based similarity measure of unstructured records, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	Arnaud Giacometti , Patrick Marcel , Elsa Negre, A framework for recommending OLAP queries, Proceeding of the ACM 11th international workshop on Data warehousing and OLAP, October 30-30, 2008, Napa Valley, California, USA
	Xiaochun Yang , Bin Wang , Chen Li, Cost-based variable-length-gram selection for string collections to support approximate queries efficiently, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Zhihao Yang , Hongfei Lin , Yanpeng Li, Brief Communication: Exploiting the performance of dictionary-based bio-entity name recognition in biomedical literature, Computational Biology and Chemistry, v.32 n.4, p.287-291, August, 2008
	Deise de Brum Saccol , Nina Edelweiss , Renata de Matos Galante , Carlo Zaniolo, XML version detection, Proceedings of the 2007 ACM symposium on Document engineering, August 28-31, 2007, Winnipeg, Manitoba, Canada
	Mikalai Sabel, Structuring wiki revision history, Proceedings of the 2007 international symposium on Wikis, p.125-130, October 21-25, 2007, Montreal, Quebec, Canada
	Miklós Kurucz , András A. Benczúr , Tamás Kiss , István Nagy , Adrienn Szabó , Balázs Torma, KDD Cup 2007 task 1 winner report, ACM SIGKDD Explorations Newsletter, v.9 n.2, December 2007
	Kuo-Kun Tseng , Ying-Dar Lin , Tsern-Huei Lee , Yuan-Cheng Lai, Deterministic high-speed root-hashing automaton matching coprocessor for embedded network processor, ACM SIGARCH Computer Architecture News, v.35 n.3, p.36-43, June 2007
	Claudie Faure , Nicole Vincent, Document image analysis for active reading, Proceedings of the 2007 international workshop on Semantically aware document processing and indexing, May 21-22, 2007, Montpellier, France
	Oliver Sharma , Mark Girolami , Joseph Sventek, Detecting worm variants using machine learning, Proceedings of the 2007 ACM CoNEXT conference, December 10-13, 2007, New York, New York
	Christian R. Prause , Markus Eisenhauer, Social aspects of a continuous inspection platform for software source code, Proceedings of the 2008 international workshop on Cooperative and human aspects of software engineering, p.85-88, May 13-13, 2008, Leipzig, Germany
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, Processor array architectures for flexible approximate string matching, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.35-54, January, 2008
	Hsin-Min Lu , Daniel Zeng , Lea Trujillo , Ken Komatsu , Hsinchun Chen, Ontology-enhanced automatic chief complaint classification for syndromic surveillance, Journal of Biomedical Informatics, v.41 n.2, p.340-356, April, 2008
	Szymon Grabowski , Kimmo Fredriksson, Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉) worst case time, Information Processing Letters, v.105 n.5, p.182-187, February, 2008
	Zheng Liu , James Borneman , Tao Jiang, A software system for gene sequence database construction based on fast approximate string matching, International Journal of Bioinformatics Research and Applications, v.1 n.3, p.273-291, September 2005
	Natenapa Sriharee , Twittie Senivongse, Matchmaking and ranking of semantic web services using integrated service profile, International Journal of Metadata, Semantics and Ontologies, v.1 n.2, p.100-118, October 2006
	Joong Chae Na , Kangho Roh , Alberto Apostolico , Kunsoo Park, Alignment of biological sequences with quality scores, International Journal of Bioinformatics Research and Applications, v.5 n.1, p.97-113, January 2009
	George Giannakopoulos , Vangelis Karkaletsis , George Vouros , Panagiotis Stamatopoulos, Summarization system evaluation revisited: N-gram graphs, ACM Transactions on Speech and Language Processing (TSLP), v.5 n.3, p.1-39, October 2008
	Heikki Hyyrö, Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching, Information Processing Letters, v.108 n.5, p.313-319, November, 2008
	Biao Qin , Yuni Xia, Generating efficient safe query plans for probabilistic databases, Data & Knowledge Engineering, v.67 n.3, p.485-503, December, 2008
	Liang Jin , Chen Li , Rares Vernica, SEPIA: estimating selectivities of approximate string predicates in large Databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1213-1229, August 2008
	Alberto Apostolico , Claudia Tagliacollo, Incremental discovery of the irredundant motif bases for all suffixes of a string in O(n2logn) time, Theoretical Computer Science, v.408 n.2-3, p.106-115, November, 2008
	C. H. Makris , K. Perdikuri , A. Tsakalidis, Discovering regularities in biosequences: Challenges and applications, Journal of Computational Methods in Sciences and Engineering, v.5 n.3, p.189-199, August 2005
	Leonor Becerra-Bonache , Colin de la Higuera , Jean-Christophe Janodet , Frédéric Tantini, Learning Balls of Strings from Edit Corrections, The Journal of Machine Learning Research, 9, p.1841-1870, 6/1/2008
	Chuan Xiao , Wei Wang , Xuemin Lin, Ed-Join: an efficient algorithm for similarity joins with edit distance constraints, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007
	Alexander Tiskin, Semi-local longest common subsequences in subquadratic time, Journal of Discrete Algorithms, v.6 n.4, p.570-581, December, 2008
	Mei-Chen Yeh , Kwang-Ting Cheng, A string matching approach for visual retrieval and classification, Proceeding of the 1st ACM international conference on Multimedia information retrieval, October 30-31, 2008, Vancouver, British Columbia, Canada
	Li Yujian , Liu Bo, A Normalized Levenshtein Distance Metric, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.29 n.6, p.1091-1095, June 2007
	Philip Bille , Martin Farach-Colton, Fast and compact regular expression matching, Theoretical Computer Science, v.409 n.3, p.486-496, December, 2008
	Benjamin Bustos , Gonzalo Navarro, Improving the space cost of k-NN search in metric spaces by using distance estimators, Multimedia Tools and Applications, v.41 n.2, p.215-233, January 2009
	Paolo Tormene , Toni Giorgino , Silvana Quaglini , Mario Stefanelli, Matching incomplete time series with dynamic time warping: an algorithm and an application to post-stroke rehabilitation, Arificial Intelligence in Medicine, v.45 n.1, p.11-34, January, 2009
	Manish Kumar , Shane Moriah , Srikumar Krishnamoorthy, Performance evaluation of similarity join for real time information integration, Proceedings of the 2nd Bangalore Annual Compute Conference on 2nd Bangalore Annual Compute Conference, January 09-10, 2009, Bangalore, India
	Erik Linstead , Sushil Bajracharya , Trung Ngo , Paul Rigor , Cristina Lopes , Pierre Baldi, Sourcerer: mining and searching internet-scale software repositories, Data Mining and Knowledge Discovery, v.18 n.2, p.300-336, April 2009
	Cinzia Pizzi, Note: k-difference matching in amortized linear time for all the words in a text, Theoretical Computer Science, v.410 n.8-10, p.983-987, March, 2009
	Rares Vernica , Chen Li, Efficient top-k algorithms for fuzzy search in string collections, Proceedings of the First International Workshop on Keyword Search on Structured Data, June 28-28, 2009, Providence, Rhode Island
	Wei Wang , Chuan Xiao , Xuemin Lin , Chengqi Zhang, Efficient approximate entity extraction with edit distance constraints, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Alessandro Basso , Marco Milanesio , Giancarlo Ruffo, Events discovery for personal video recorders, Proceedings of the seventh european conference on European interactive television conference, June 03-05, 2009, Leuven, Belgium
	Kuo-Kun Tseng , Yuan-Cheng Lai , Ying-Dar Lin , Tsern-Huei Lee, A fast scalable automaton-matching accelerator for embedded content processors, ACM Transactions on Embedded Computing Systems (TECS), v.8 n.3, p.1-30, April 2009
	Tossapon Boongoen , Qiang Shen, Intelligent hybrid approach to false identity detection, Proceedings of the 12th International Conference on Artificial Intelligence and Law, June 08-12, 2009, Barcelona, Spain
	Lior Aronovich , Ron Asher , Eitan Bachmat , Haim Bitner , Michael Hirsch , Shmuel T. Klein, The design of a similarity based deduplication system, Proceedings of SYSTOR 2009: The Israeli Experimental Systems Conference, May 04-April 06, 2009, Haifa, Israel
	Alexandr Andoni , Krzysztof Onak, Approximating edit distance in near-linear time, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA
	Nilesh Dalvi , Ravi Kumar , Bo Pang , Raghu Ramakrishnan , Andrew Tomkins , Philip Bohannon , Sathiya Keerthi , Srujana Merugu, A web of concepts, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Surajit Chaudhuri , Raghav Kaushik, Extending autocompletion to tolerate errors, Proceedings of the 35th SIGMOD international conference on Management of data, June 29-July 02, 2009, Providence, Rhode Island, USA
	Indrajit Bhattacharya , Lise Getoor, Query-time entity resolution, Journal of Artificial Intelligence Research, v.30 n.1, p.621-657, September 2007
	Martin Reynaert, Parallel identification of the spelling variants in corpora, Proceedings of The Third Workshop on Analytics for Noisy Unstructured Text Data, July 23-24, 2009, Barcelona, Spain

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

Additional Classification:
H. Information Systems
H.3 INFORMATION STORAGE AND RETRIEVAL
H.3.3 Information Search and Retrieval
Subjects: Search process

General Terms:
Algorithms

Keywords:
Levenshtein distance, edit distance, online string matching, text searching allowing errors

REVIEW

"Paul Cull : Reviewer"

String matching is used in a variety of areas, including word processing, information retrieval, and computational biology. This survey considers the problem of locating within a text string all substrings which are nearly the same as an inp more...

Collaborative Colleagues:

Gonzalo Navarro: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player