Fast Parallel and Serial Multidimensional Approximate Array Matching

Amihood Amir and Gad M. Landau
Additional contact information
Amihood Amir: University of Maryland, Department of Computer Science and Institute for Advanced Computer Studies
Gad M. Landau: New York University, Department of Computer Science Courant Institute of Mathematical Sciences

A chapter in Sequences, 1990, pp 3-24 from Springer

Abstract: Abstract 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.

Keywords: Parallel Algorithm; Match Problem; String Match; Suffix Tree; Dimensional Array (search for similar items in EconPapers)
Date: 1990
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4612-3352-7_1

Ordering information: This item can be ordered from
http://www.springer.com/9781461233527

DOI: 10.1007/978-1-4612-3352-7_1

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().