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.

 Back to Sam Buss's publications page.