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 + k2)) and the parallel algorithm runs in time O(d((d)log n + k) + k2) 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(2(d)n(d) log2 m) 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:SIGMA x SIGMA --> [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(2(d)n(d) log2 m). Our parallel algorithm is again of time complexity O(d log n) using n(d) processors.