An Index Data Structure for Matrices, with Applications to Fast Two-Dimensional Pattern Matching

We describe a new data structure, the submatrix trees (s-trees for short). Is is a forest of compacted patricia trees representing all submatrices of a given matrix TEXT. The s-trees is the first data structure representing all submatrices of a general matrix that can be efficiently built, dynamically changed, queried and extended to deal with run length encoded matrices, which are typically used in digital picture processing. It can be thought of as a generalization to matrices of McCreight's suffix tree for a string, which represents all substrings of a string, and of Giancarlo's Lsuffix tree of a square matrix, which represents all square submatrices of a square matrix and therefore, deals with a special case of the matrices considered here. The s-trees requires new algorithmic techniques as explained in the Introduction.