A Fast Order-Preserving Matching with q-neighborhood Filtration Using SIMD Instructions

Abstract

The order-preserving matching problem is a variant of the pattern matching problem focusing on shapes of sequences instead of values of sequences. Given a text and a pattern, the problem is to output all positions where the pattern and a subsequence in the text are of the same relative order. Chhabra and Tarhio proposed a fast algorithm based on filtration for the order-preserving matching problem, and Faro and Ku¨lekci improved Chhabra and Tarhio's solution by extending the filter. Furthermore, Cantone et al. and Chhabra et al. proposed solutions based on filtration using SIMD (Single Instruction Multiple Data) instructions, and showed that SIMD instructions are efficient in speeding up their algorithms. In this paper, we propose a fast matching algorithm for the orderpreserving matching problem using SIMD instructions based on filtration proposed by Faro and Ku¨lekci. We show that our algorithm is practically faster than previous solutions.

Keywords

• pattern matching problem
• order-preserving matching problem
• SIMD instructions

1 Introduction

The order-preserving matching problem [ 9, 11 ] is a variant of the pattern matching problem focusing on shapes of sequences instead of values of sequences. This matching can be applied to various fields, such as musical matching, sensor data analysis and stock price analysis. Kubica et al. [ 11 ] defined an order-isomorphism as one of the similarities of sequences. For two numerical sequences X and Y of the same length, the order-isomorphism expresses that the relative order of X coincides with that of Y. For example, two sequences X = (8; 32; 40; 24; 16) and Y = (18; 42; 50; 34; 26) are order-isomorphic because both the relative orders of X and Y are (1; 4; 5; 3; 2). The order-preserving matching problem is, given a text and a pattern, to output all positions of subsequences in the text that are order-isomorphic to the pattern.

Various sequential matching algorithms for the order-preserving matching problem have been developed, based on the Knuth-Morris-Pratt Algorithm [ 9, 11 ], Horspoo Algorithm [ 5 ], and forward automaton Algorithm [ 1 ]. Moreover, Chhabra and Tarhio [ 4 ] proposed a practically fast pattern matching algorithm using a filtration method. In this method, text T and pattern P are encoded into binary sequences T ′ and P′ respectively, based on the relationship to the adjacent values. Because the standard string matching P′ in T ′ is much faster than the order-preserving matching P in T , it can be used to narrow the candidate positions, although some incorrect answers may be included. Hence this methods requires verification steps for the candidates. Faro and Ku¨lekci [ 7 ] improved the filter by considering q-neighborhood values, instead of adjacent (1-neighborhood) values. More recently, solutions based on filtration using SIMD (Single Instruction Multiple Data) instructions were proposed by Cantone et al. [ 2 ] and Chhabra et al. [ 3 ]. They showed that SIMD instructions are efficient in speeding up their algorithms.

In this paper, we propose a new fast algorithm using SIMD instructions based on filtration proposed by Faro and Ku¨lekci [ 7 ]. Our experiments show that our algorithm is practically faster than previous solutions. 2 2.1

Preliminaries

Notations

Let be an ordered alphabet, and be the set of all sequences over . jXj denotes the length of a sequence X 2 , and X[i] denotes the i-th value of X for 1 i jXj. A subsequence of X beginning at i and ending at j for 1 i j jXj is denoted by X[i : j] = (X[i]; X[i + 1]; : : : ; X[ j 1]; X[ j]). 2.2

Order Preserving Matching

Definition 1 (Order-isomorphism [11]). Two sequences X; Y 2

are order-isomorphic if X[i] X[ j] () Y[i] Y[ j] for any 1 X Y if X is order-isomorphic to Y, and X 0 Y otherwise. of the same length i; j jXj. We write Example 1. For sequences X = (8; 32; 40; 24; 16), Y = (18; 42; 50; 34; 26) and Z = (20; 24; 45; 38; 31), we have X Y and X 0 Z.

Definition 2 (Order-Preserving Matching Problem [9, 11]). Given a text T 2 of

length n, and a pattern P 2 of length m, the order-preserving matching problem asks for all positions i satisfying T [i : i + m 1] P for 1 i n m + 1. Example 2. For a text T = (13; 18; 42; 50; 34; 26; 12; 20; 24; 45; 38; 31) and a pattern P = (8; 32; 40; 24; 16), the output is 2 because T [2 : 6] P, see Fig. 1.

Solutions for the order-preserving matching problem based on filtration require a verification step. That is, each candidate T [i : i + m 1] is verified whether it is order-isomorphic to the pattern P of length m. It takes O(m2) time by using a naive algorithm based on Definition 1. The previous work [ 2, 4 ] showed the following lemma for verifying the order-isomorphism of two sequences of length m in O(m) time with O(sort(m)) preprocessing time, where sort(m) is the time required to sort one of the sequences.

Definition 3 (relative order array [2, 4]). For a sequence Y 2 , the relative or

der array RY of Y is defined as RY = (rankY1(1); rankY1(2); : : : ; rankY1(jYj)), where rankY (i) = jfk : Y[k] < Y[i] or (Y[k] = Y[i] and k < i)gj.

Lemma 1 ([ 4 ]). Given two sequences X; Y 2 of length m, and the relative order array RY of Y, we have X 0 Y if and only if there exists 1 j m 1 such that one of the following conditions holds: (1) X[RY [ j]] > X[RY [ j + 1]], (2) X[RY [ j]] = X[RY [ j + 1]] and X[RY [ j]] , X[RY [ j + 1]], or (3) X[RY [ j]] < X[RY [ j + 1]] and X[RY [ j]] = X[RY [ j + 1]].

The relative order array can be computed in O(sort(m)) time [ 4 ]. Therefore, the verification algorithm based on Lemma 1 runs in O(m) time with O(sort(m)) preprocessing time. 3 3.1

Previous Work

Neighborhood Ranking Filter

Chhabra and Tarhio [ 4 ] proposed an order-preserving filtration technique. In this paper, we call it Neighborhood Ranking filter (shortly NR filter). It consists of two phases, the filtration phase and the verification phase.

In the filtration phase, candidates are filtered out by using Neighborhood Ranking code (shortly NR code) defined by the following.

Definition 4 (Neighborhood Ranking code). For a sequence X 2 , the Neighbor

hood Ranking code of X is defined as B(X)[i] = 1 if X[i] < X[i + 1], and 0 otherwise, for 1 i jXj 1.

At the beginning of the filtering phase, we compute the NR code B(P) of the pattern P. Next, we find all positions i satisfying B(T [i : i + m 1]) = B(P) for 1 i n m + 1, that are candidates of the order-preserving matching. In order to find these positions, we can use any standard string matching algorithms, such as Knuth-MorrisPratt algorithm [ 10 ]. Such candidates include no false negative results, in other words, the filter never removes correct answers by the following proposition. Proposition 1 ([ 4 ]). For any two sequences X; Y 2 , X

Y ) B(X) = B(Y): The converse of Proposition 1 is not always true. Hence, candidates include false positive results, in other words, the filter may pass incorrect answers.

In the verification phase, every candidate is checked whether it is order-isomorphic to the pattern or not. The verification method is based on Lemma 1, which requires pre-computing the relative order array RP of pattern P.

Example 3. We consider again the instance in Example 1 and Fig. 1. At first, the relative order array RP = (1; 5; 4; 2; 3) of P is computed. Next, in the filtering phase, T and P are encoded into NR codes as B(T ) = (1; 1; 1; 0; 0; 0; 1; 1; 1; 0; 0) and B(P) = (1; 1; 0; 0), respectively. The positions i that satisfy B(T )[i : i + m 1] = B(P) are i = 2 and i = 8 only. Therefore, the candidates are T [2 : 6] = (18; 42; 50; 34; 26) and T [8 : 12] = (20; 24; 45; 38; 31). Lastly, in the verification phase, T [2 : 6] and T [8 : 12] are verified whether they are order-isomorphic to P or not, using the verification algorithm based on Lemma 1. As a result, the position 2 is reported. 3.2

q-Neighborhood Ranking Filter Faro and Ku¨lekci [ 7 ] proposed q-Neighborhood Ranking code (q-NR code) for the filtration technique, which is a more effective filtration technique than that of using the original neighborhood ranking code. It uses q-neighborhood relationships, while the original neighborhood ranking code uses only one-adjacent relationships.

Definition 5 (q-Neighborhood Ranking code [7]). Let X 2 be a sequence of length

n, and q be an integer satisfying 1 q < n. The q-Neighborhood Ranking code of X is defined as Bq(X)[i] = ∑qj=1( X(i; j) 2q j) where X(i; j) = 1 if X[i] < X[i + j], and 0 otherwise, for 1 i n q.

Example 4. For a sequence X = (8; 32; 40; 24; 16), we have B1(X) = (1; 1; 0; 0), B2(X) = ((11)2; (10)2; (00)2) = (3; 2; 0) and B3(X) = ((111)2; (100)2) = (7; 4).

The next lemma guarantees that candidates filtered by q-NR code also contain no false negatives as well as the NR filter.

Lemma 2 ([ 7 ]). For any two sequences X; Y 2 , X

Y ) Bq(X) = Bq(Y).

The converse of Lemma 2 is not always true, similarly to Proposition 1. Hence, candidates obtained by using the q-NR filter also possibly contain false positive results. 4 4.1

Proposed Methods

Fast Implementation Using SIMD Instructions

In this section, we propose a fast implementation using SIMD (Single Instruction Multiple Data) instructions. We use SSE4.2 [ 8 ] for a SIMD instruction set. SSE4.2 supports 128-bit registers, that can contain two 64-bit, four 32-bit, eight 16-bit, or sixteen 8-bit numbers. The packing factor = 128=w stands for the number of w-bit numbers contained in the 128-bit register. SSE4.2 allows to perform the same operation in parallel on several numbers stored in the 128-bit register. behavior Return a sequence C˜, where C˜[i] = 2w if X˜1 < X˜2, and 0 otherwise for 1 i Return a sequence A˜, where A˜[i] = X˜1[i] & X˜2[i] for 1 i .

Return a sequence O˜, where O˜[i] = X˜1[i] j X˜2[i] for 1 i .

Return a bit mask from most significant bits of X˜ [i] for 1 i .

Find X˜P of length m from X˜T of length n. SIMD Instructions Table 1 shows the functions and SIMD instructions used in this paper. We explain some non-trivial functions in it. The function MoveMask(X˜ ) returns a bit mask that consists of the most significant bit of each value in a sequence X˜ , i.e., it returns ∑i=1 (⌊X˜ [i] 21 w⌋ 2i 1). For two sequences X˜ P and X˜T , and two integers 1 m; n , the function SearchStr(X˜ P; m; X˜T ; n) returns a sequence S˜ such that S˜ [i] = <>>>8 2w > >>: 0 1 ( X˜ P[1 : m] = X˜T [i : i + m 1]

X˜ P[1 : n i + 1] = X˜T [i : n] (otherwise) (1 (n i n m + 1); or ) m + 1 < i n) for 1 n

i . Note that this function compares the prefix of X˜ P and the suffix of X˜T for m + 1 < i n.

Order-preserving Matching Algorithm Using SIMD Instructions We propose a fast

algorithm, called order-preserving matching filtration technique using SIMD instructions with q-NR code (shortly OPFSIq), using the functions in Table 1. The OPFSIq

Algorithm 2: Encodeq(X; i)

Input: A sequence X 2

Output: Bq(X[i : i + 1 X˜ X[i : i + 1]; 2 for j 1 to q do 3 X˜j X[i + j : i + j + 4 M˜ j (2q j; 2q j; : : : ; 2q j) 5 K˜ j And(C˜ j; M˜ j); K˜

6 return K˜ ;

, and a position i. 1]).

K˜ (0; 0; : : : ; 0) ˜ C j

˜ /* jM jj = Or(K˜ ; K˜ j); /* jK˜ j =

*/ CompLt(X˜ ; X˜j); */ algorithm is presented in Algorithm 1 and 2. The function ctz(b) returns the number of trailing zeros in b from the least significant bit. For example, ctz((11000100)2) = 2. This function can be computed fast by using the bsf instruction in x86.

In this algorithm, a chunk of length of the text is processed by SIMD instructions. The chunk of the text is encoded to the q-NR code of length using function Encodeq shown in Algorithm 2. The matching between the encoded chunk and the encoded pattern is performed in line 6 of Algorithm 1, by a SIMD instruction. The bit mask represents candidate positions. For example, if mask = (01000001)2 then candidates are i and i + 7.

Our algorithm has some weaknesses in the following two cases. (1) The case that the pattern is long so that m > q. In this case, this algorithm uses the prefix of Bq(P), and only checks whether the prefix of Bq(P) matches with Bq(T [i : i + 1]) or not. (2) The case that a subsequence order-isomorphic to the pattern is split in two or more chunks of text. In this case, this algorithm only checks whether the prefix of Bq(P) matches to the suffix of Bq(T [i : i + 1]) (see the detail of SearchStr function). In these two cases, this algorithm can find all correct positions by Lemma 2, since Bq(X) = Bq(Y) ) Bq(X)[1 : i] = Bq(Y)[1 : i] for 1 i jXj q, although the number of candidates increases.

The main difference between our algorithm and the algorithm proposed by Faro and Ku¨lekci [ 7 ] is utilizing SIMD instructions. Their algorithm encodes the text naively and finds candidates based on the SBNDM2 [ 6 ] string matching algorithm, while our algorithm encodes elements at once and finds candidates by the SIMD instruction. Optimized Implementation Assume that w = 16 and q 8. In this case, an 8-bit integer is enough to handle each value of q-NR code, although a 16-bit integer is used by the naive implementation of Algorithm 1. Therefore, we can pack two encoded chunks T˜1 = Bq(T [i : i + 1]) and T˜2 = Bq(T [i + : i + 2 1]) into one 128-bit register, by extracting the lower 8-bits of each value of T˜1 and T˜2. Then, we can perform a matching between Bq(T [i : i + 2 1]) and the encoded pattern by SearchStr function.

In order to implement it, we encode two chunks in each iteration, and change the loop step size from into 2 . Extracting the lower 8-bits of each value and packing into one 128-bit register can be implemented by the mm shuffle epi8 and the mm or si128 instructions. This optimization technique is very effective because the mm cmpestrm instruction (SearchStr function) is much slower than other instructions [ 8 ]. This technique can be used in a similar way in the case of w = 32. 5

Experimental Results

We performed experiments comparing running time of our algorithm with that of previous work [ 2–4, 7 ]. We used a machine with Intel Xeon E5-2640 processor and 128GB memory on Ubuntu 14.04LTS. We implemented the OPFSIq algorithm 1 in C++, and compiled with gcc 4.8.4 . The OPFSIq algorithm was implemented by SSE4.2 intrinsic functions. Compiler options were -O3 -msse4.2.

We used two kinds of text data. One was random text data, consisting of 1000000 random integers of range 1 to 100. The other was temperature text data in Sendai city, consisting of 32452 integers. From a text data, 100 patterns were randomly chosen, and we computed the average running time of 100 runs for each pattern.

The algorithms proposed by Chhabra and Tarhio [ 4 ], Faro and Ku¨lekci [ 7 ], Cantone et al. [ 2 ] and Chhabra et al. [ 3 ] are respectively denoted as CT14, FK15, CFK15, and CKT15. These algorithms are implemented by themselves 2. Similarly to previous work [ 2, 7 ], CT14 is based on the SBNDM2 algorithm. CKT15 utilizes SSE4.2 and AVX instruction set. 0 25 0.2 )ce0.15 s m ( item0.1

Results are shown in Fig. 2 and Fig. 3. In FK15 and CFK15, the best results are selected among various parameters. The parameter w in OPFSIq means that the text data are treated as either w-bit integers (w = 8; 16) or w-bit floating points (w = 32), and optimized denotes that the optimization technique described in Section 4.1 is applied. In Fig. 2 and Fig. 3, we show the best results of the OPFSIq algorithm with w = 8; 16; 32. Furthermore, in Fig. 2 we also show results of OPFSI1 (w = 8) and OPFSI4 (w = 16) in order to discuss the effectiveness of the OPFSIq algorithm. 1 Our implementations can be downloaded from http://www.shino.ecei.tohoku.ac.jp/ member/youhei_ueki/sofsem2016 2 We acknowledge the authors for sharing their program.

The OPFSIq algorithm runs extremely faster for short patterns. Especially, for OPFSI4 (w = 8) and m = 7, the algorithm runs approximately 4.7 times faster than all the previous work on the random text data. Comparisons between the results of OPFSI1 (w = 8) with OPFSI4 (w = 8), and OPFSI4 (w = 16) with OPFSI4 (w = 16, optimized) respectively show the effectiveness of q-NR filtration and the optimization technique described above. All previous work runs faster as the pattern length increases, whereas the OPFSIq algorithm does not. This is because the OPFSIq algorithm runs in linear time on average. 6

Conclusion

We proposed an effective filtration for the order-preserving matching problem using SIMD instructions, and confirmed that it practically runs faster than existing methods.

We used the SIMD instruction set SSE4.2 that supports 128 bit registers. We expect that it will become faster if we use other SIMD instruction sets that support wider registers, such as AVX2 supporting 256 bit registers and AVX-512 supporting 512 bit registers.

Acknowledgments. This work was supported by ImPACT Program of Council for Science, Technology and Innovation (Cabinet Office, Government of Japan), and KAKENHI Grant Numbers 25240003 and 15H05706.

References

1. Belazzougui , D. , Pierrot , A. , Raffinot , M. , Vialette , S. : Single and multiple consecutive permutation motif search . In: ISAAC . 66 - 77 ( 2013 )

2. Cantone , D. , Faro , S. , Ku¨ lekci, M.O.: An efficient skip-search approach to the orderpreserving pattern matching problem . 22 - 35 ( 2015 )

3. Chhabra , T. , Ku¨ lekci, M.O. , Tarhio , J.: Alternative algorithms for order-preserving matching . In: PSC . 36 - 46 ( 2015 )

4. Chhabra , T. , Tarhio , J.: Order-preserving matching with filtration . In: SEA . 307 - 314 ( 2014 )

5. Cho , S. , Na , J.C. , Park , K. , Sim , J.S.: A fast algorithm for order-preserving pattern matching . Information Processing Letters 115 ( 2 ) 397 - 402 ( 2015 )

6. Durian , B. , Holub , J. , Peltola , H. , Tarhio , J.: Improving practical exact string matching . Information Processing Letters 110 ( 4 ) 148 - 152 ( 2010 )

7. Faro , S. , Ku¨ lekci, M.O.: Efficient algorithms for the order preserving pattern matching problem . arXiv:1501.04001 ( 2015 )

8. Intel Corporation : Intel (R) 64 and IA-32 Architectures Optimization Reference Manual . ( 2014 )

9. Kim , J. , Eades , P. , Fleischer , R. , Hong , S.H. , Iliopoulos , C.S. , Park , K. , Puglisi , S.J. , Tokuyama , T. : Order-preserving matching . Theoretical Computer Science 525 ( 13 ) 68 - 79 ( 2014 )

10. Knuth , D.E. , Jr. , J.H.M. , Pratt , V.R. : Fast pattern matching in strings . SIAM Journal on Computing 6 ( 2 ) 323 - 350 ( 1977 )

11. Kubica , M. , Kulczynski , T. , Radoszewski , J. , Rytter , W. , Walen , T. : A linear time algorithm for consecutive permutation pattern matching . Information Processing Letters 113 ( 12 ) 430 - 433 ( 2013 )