In this research, we propose the nearest neighbor searching problem and we give an algorithm to solve the problem. Roughly speaking, the nearest neighbor searching problem is defined as follows: Give a text string T=t1t2…tn and a pattern string P=p1p2…pm, find all substrings in T whose edit distances with respect to P are the smallest among all substrings of T. Our algorithm is based upon two concepts: (1) There is a special property of dynamic programming matrix which is used to solve the approximate string matching problem. We call this property the small change property. (2) Values on the D matrix can be computed along the diagonals. Our experimental results showed that our algorithm is quite efficient.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com