The use of a lattice for fast pattern matching

Abstract

Pattern recognition involves the matching of a given pattern against a collection of patterns in store in order to identify the given pattern as belonging to a particular class already known to the system or not. Similarly, data retrieval from content addressable storage involves the matching of a partial pattern against a collection of patterns in store in order to retrieve the required pattern.

This matching procedure can be made very efficient by integrating stored patterns into a graphical structure called a lattice. The lattice forms an optimal indexing mechanism and supports fast parallel matching. The indexing mechanism is optimal because it is both complete and minimal: all possible indices to a particular pattern are generated, and indices are integrated maximally, i.e. paths to similar patterns overlap as much as possible and thereby prevent duplication. Moreover, the indexing mechanism is robust: if faulty or partial information is supplied, the lattice is guaranteed to provide the best approximate answer.