Parallel construction and query of index data structures for pattern matching on square matrices

We describe fast parallel algorithms for building index data structures tha t can be used to gather various statistics on square matrices. The main dat a structure is the Lsuffuc tree, which is a generalization of the classical suffix tree for strings. Given an n x n text matrix A, we build our data s tructures in O(log n) time with n(2) processors on a CRCW PRAM, so that we can quickly process A in parallel as follows: (i) report some statistical i nformation about A, e.g., find the largest repeated square submatrices that appear at least twice in A or determine, for each position in A, the small est submatrix that occurs only there; (ii) given, on-line, an m x m pattern matrix PAT, check whether it occurs in A. We refer to the above two kinds of operations as queries and point out that they have applications to visua l databases and two-dimensional data compression. Query (i) takes O(log n) time with n(2)/log n processors and query (ii) takes O(log m) time with m(2 )/log m processors. The query algorithms are work optimal while the constru ction algorithm is work optimal only for arbitrary and large alphabets. (C) 1999 Academic Press.