The Library
Pattern matching under polynomial transformation
Tools
Butman, Ayelet, Clifford, Peter, Clifford, Raphaël, Jalsenius, Markus, Lewenstein, Noa, Porat, Benny, Porat, Ely and Sach, Ben (2013) Pattern matching under polynomial transformation. SIAM Journal on Computing, 42 (2). pp. 611-633. doi:10.1137/110853327 ISSN 0097-5397.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1137/110853327
Abstract
We consider a class of pattern matching problems where a normalizing polynomial transformation can be applied at every alignment of the pattern and text. Normalized pattern matching plays a key role in fields as diverse as image processing and musical information processing, where application specific transformations are often applied to the input. By considering a wide range of such transformations, we provide fast algorithms and the first lower bounds for both new and old problems. Given a pattern of length $m$ and a longer text of length $n$, where both are assumed to contain integer values only, we first show $O(n\log m)$ time algorithms for pattern matching under linear transformations even when wildcard symbols can occur in the input. We then show how to extend the technique to polynomial transformations of arbitrary degree. Next we consider the problem of finding the minimum Hamming distance under polynomial transformation. We show that, for any $\varepsilon>0$, there cannot exist an $O(nm^{1-\varepsilon})$ time algorithm for additive and linear transformations conditional on the hardness of the classic 3Sum problem. Finally, we consider a version of the Hamming distance problem under additive transformations with a bound $k$ on the maximum distance that needs to be reported. We give a deterministic $O(nk\log k)$ time solution, which we then improve by careful use of randomization to $O(n\sqrt{k\log k}\log n)$ time for sufficiently small $k$. Our randomized solution outputs the correct answer at every position with high probability.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | SIAM Journal on Computing | ||||
Publisher: | Society for Industrial and Applied Mathematics | ||||
ISSN: | 0097-5397 | ||||
Official Date: | 2013 | ||||
Dates: |
|
||||
Volume: | 42 | ||||
Number: | 2 | ||||
Page Range: | pp. 611-633 | ||||
DOI: | 10.1137/110853327 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |