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 logn+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: Σ×Σ→[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.

Authors

• Amihood Amir
• Gad M. Landau

Keywords

No keywords are indexed for this paper.