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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
9223699
Program Officer
Yechezkel Zalcstein
Project Start
Project End
Budget Start
1993-07-01
Budget End
1997-12-31
Support Year
Fiscal Year
1992
Total Cost
$123,110
Indirect Cost
Name
Georgia Tech Research Corporation
Department
Type
DUNS #
City
Atlanta
State
GA
Country
United States
Zip Code
30332