__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.