An Efficient Skip-Search Approach to the Order-Preserving Pattern Matching Problem

Given a pattern and text, both over a common ordered alphabet, the order- preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. This problem, an approximate variant of the well-known exact pattern matching problem, finds applications in such fields as time series analysis (e.g., share prices on stock markets), weather data analysis, musical melody matching, etc., and has gained increasing attention in recent years. In this paper we present a new efficient approach to this problem inspired to the well-known Skip Search algorithm for the exact string matching problem. It makes use of efficient SIMD SSE instructions in order to speed up the searching phase. Experimental results show that our proposed algorithm is up to twice as faster than previous solutions.