String Matching is one of the fundamental and most studied problems in computer science. In contrast, multidimensional matching proved more difficult to tackle. However, multidimensional pattern matching is central to many important applications, from multimedia to computational molecular biology. This research develops a theory of multidimensional matching, involving new insights into the nature of multidimensional matching, and results such as the following: better serial and parallel algorithms for exact multidimensional matching; efficient algorithms for rotations and approximate matching; and efficient algorithms for approximate dictionary matching. Several of the algorithms have been implemented in some practical application systems.
