Fast Parallel and Serial Multidimensional Approximate Array Matching

Consider the multidimensional array matching problem, where differences between characters of the pattern and characters of the text are permitted. A difference may be due to a mismatch between a text and pattern character, superfluous text character or superfluous pattern character. Given a d-dimensional array of size n d (text) and a d dimensional array of size m d (pattern) we present the following algorithms: For a given k, find all occurrences of the pattern in the text with at most k differences. Our serial algorithm runs in time O(n d (dk+k 2 )) and the parallel algorithm runs in time O(d(d log n +k)+ k 2 ) using n d processors. If superfluous characters are not allowed and the only permitted errors are mismatches, we solve the problem serially in time O(n d dk) and in parallel in time O(d(d log n +k)) using n d processors. We present an alternate algorithm for the mismatches problem which runs serially in time O(d 2 n d log n log m log log n) and in parallel in time O(d log n) using n d processors. This algorithm is more efficient for large k. We also give an efficient solution to the close match problem. Here a mismatch weight function f: Σ + Σ → [0,1] is assigned. The weight function gives weight to the mismatches, some mismatches being worse than others. We present a serial algorithm for finding all appearances of the pattern in the text with a bounded total error in time O(d 2 n d log n log m log log n). Our parallel algorithm is again of time complexity O(d log n) using n d processors.