Technical report:
Samuel R. Buss.
"Neighborhood Metrics on n-Dimensions Blocks of
Characters"
Technical Report. Mathematical Sciences Research
Institute, Berkeley, 1986.
Download: Searchable PDF or plain PDF .
Abstract: A mathematical framework for constructing metrics on arrays of characters is defined. This is inspired by the Yianilos string matching algorithm. New metrics \nu_d are defined which provide a fuzzy comparison function on d-dimensional blocks of characters. A sequential algorithm for \nu_2 is given, with runtime O((#A) N^2), which operates on NxN blocks of characters, where #A is the alphabet size. A parallel algorithm for \nu_2 is presented, which uses N^2 processors and runtime O((#A)+N). Possible applications of \nu_2 include image recognition.