Parallel duel-and-sweep algorithm for the order-preserving pattern matching
The 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020),
LNCS Vol.12011, pp.211-222
(2020), [peer-reviewed]
Event Date:
January 20-23, 2020
@ Limassol, Cyprus
- Limassol, Cyprus
Abstract / 概要
Given a text and a pattern over an alphabet, the classic exact matching problem searches for all occurrences of pattern P in text T. Unlike the exact matching problem, order-preserving pattern matching considers the relative order of elements, rather than their exact values. In this paper, we propose the first parallel algorithm for the OPPM problem. Our algorithm is based on the “duel-and-sweep” algorithm. For a pattern of length $m$ and a text of length $n$, our algorithm runs in $O(\log^3{m})$ time and $O(n \log^3{m})$ work on the Priority CRCW PRAM.