On the Construction of Index Data Structures for Matrices: A lower bound.

We introduce the notion and investigate the complexity of an abstract index data structure for an n xw matrix TEXT, which has entries defined over an alphabet E. Such index is a tree data structure that represents all submatrices of the given matrix and that can be sued to answer quickly queries of the type "does the pattern matrix PAT occur in TEXT?". The data structures proposed in [9] and [11] are a special case of our abstract index. We prove that the number of edges and nodes that any such tree must have is bounded by ohm (max(n,w) min(n,w) sup 2). Therefore, it cannot be built in less than that amount of time. The lower bound can be easily generalized to a set of matrices.