Multi-Dimensional Pattern Matching with Dimensional Wildcards: Data Structures and Optimal On-Line Search Algorithms
✍ Scribed by Raffaele Giancarlo; Roberto Grossi
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 434 KB
- Volume
- 24
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
We introduce a new multidimensional pattern matching problem that is a Ž natural generalization of string matching, a well studied problem A. V. Aho, Ž . ''Handbook of Theoretical Computer Science'' J. van Leeuwen, Ed. , pp. 257᎐295, . Elsevier, Amsterdam, 1990 . The motivation for its algorithmic study is mainly w x theoretical. Let A 1:n , . . . , 1:n be a text matrix with N s n . . . n entries and 1 d 1 d w x B 1:m , . . . , 1:m be a pattern matrix with M s m . . . m entries, where d G r G 1 1 r 1 r
Ž . the matrix entries are taken from an ordered alphabet ⌺ . We study the problem Ž of checking whether some r-dimensional submatrix of A is equal to B i.e., a . decision query . A can be preprocessed and B is given on-line. We define a new data structure for preprocessing A and propose CRCW-PRAM algorithms that Ž . 2 Ž . build it in O log N time with N rn processors, where n s max n , . . . , n , ma x max 1 d Ž . Ž . such that the decision query for B takes O M work and O log M time. By using d ŽŽ . . known techniques, we would get the same preprocessing bounds but an O M r work bound for the decision query. The latter bound is undesirable since it can depend exponentially on d; our bound, in contrast, is independent of d and Ž . optimal.
We can also answer, in optimal work, two further types of queries: a an