New Algorithms for δγ-Order Preserving Matching

2.1. Definition of δϒ -order preserving matching problem (δϒ -OPMP)

The motivation to define δϒ -order-preserving matching stems from the observation that the application areas of order-preserving matching, mainly stock market analysis and music information retrieval, require to search for occurrences of the pattern that may not be exact but rather have slight modifications in the magnitude of the rankings. For example, let us assume that the text T presented in Figure 1 is a sequence of stock prices and that we want to determine whether it contains similar occurrences of the pattern P (also shown in this figure). Under the exact order-preserving matching paradigm, there are no matches, but there are similar occurrences at positions and 1 and 11. In particular, T1...8 and T11...18 are similar, regarding order structure, to the pattern. This similarity can be seen even more clearly if we consider natural representations of these strings (also shown in Figure 1). Next we formally define these notions

Figure 1: Order preserving matching under _ approximation example.

Definition 1 (δϒ -order-preserving match ) ^{_{Let X = X0...m−1 and Y = Y0...m−1 be two equallength strings defined over Σσ . Also, let δ, γ be two given numbers (δ, γ ∈}} N). Strings X and Yare said to δγ-order-preserving match, denoted as .

Given δ = 2, γ = 6, X = (10, 15, 19, 12, 11, 18, 23, 22) and Y = (14, 17, 20, 18, 12, 15, 23, 22i 22) = (1, 4, 6, 3, 2, 5, 8, 7i, nr(Y ) = (2, 4, 6, 5, 1, 3, 8, 7i and nr(X ) γ nr(Y ).

Problem 1 (δγ-order-preserving matching) ^{_{Let P = P0...m−1 be a pattern string and T = T0...n−1 be a text string, both defined over Σσ . Also, let δ, γ be two given numbers (δ, γ ∈}} N). The δγ-order-preserving matching problem is to calculate the set of all indices i, 0 ≤ i ≤ n − m,satisfying the condition P satisfying the condition . From now on δγ-OPMP.

2.2.Algorithms for the δϒ -OPM

In this section, we present two algorithms that solve the δϒ -OPMP: one that uses segment trees (Section 2.2.1) and the other utilizes Fenwick trees (Section 2.2.2).

2.2.1. Segment tree based algorithm (segtree BA)^{2 10}

• buildSegTree( ^{_{T , 0, n − 1}} ): Builds a segment tree with ^{_{T0 , T1}} , . . . , ^_Tn−1 and returns the root node. The complexity is O(n) .

• updateSegTree(minIndex, i, x): Sets Ti to x. The complexity is O(lg n).

• querySegTree(minI ndex, i, j): Returns the index of the minimum value among Ti , T_i+1, . . . , T_j . If there are several minimum values, the leftmost (smallest index) is chosen. The complexity is ^{_{O(lg n)}}

Figure 2: Segment tree based algorithm: segtreeBA. The totalcomplexityof the algorithm is then O(nm lg n) with a lower bound of Ω(n lg n).

2.2.2.Fenwick tree based algorithm ( bitBA )

The Binary Indexed Tree (BIT ) or Fenwick tree, is a data structure that can be used to maintain and query cumulative frequencies ^[12]. In particular, it is mainly used to efficiently calculate prefix sums in an array of numbers. Based on this data structure, we propose the algorithm called bitBA (see Figure 3). The BIT data structure could be considered then as an abstraction of an integer array of size n indexed from 1, i.e., a bit encapsulate ^{_{A = A1 A2 · · · An}} . The version we are going to use has two operations:

• sumUpT o(tree, i): Returns ^{_{A1 + A2 + . . . + Ai}} . The complexity is O(lg n).

• addAt(tree, i, x): Sums x to ^_Ai . The complexity is O(lg n)

The algorithm has a preprocessing phase in which the data structures needed to solve the δϒ - OPMP are created. This is done with a complexity of Θ(n + n lg n + m lg m). The term n is due to the creation of the BIT. The term n lg n is due to the creation of ^_Tnr and the term m lg m is due to the creation of ^_Pnr . In the searching phase, it iterates over all possible positions in the text T to find the existing matches. For each position i to be considered, the algorithm uses the BIT to get the rank of every symbol in the searching window ^{_Ti...i+m−1} , and then each rank in the window is compared with each rank in ^_Pnr to check if ^_Ti is a δϒ -order preserving match. This operation is evaluated using the function isAMatch( ^_P,Ti,δ,ϒ ); in particular, this function returns true iff I and this takes O(m lg m + m). Each rank calculation using the BIT costs O(lg n). Then the total complexity of the algorithm is O(nm lg n), but with a lower bound of Ω(nlg n).

In the preprocessing phase, the algorithm first creates the natural representations of the pattern P and the text T ( ^{_{Pnr and Tnr}} , respectively). Then, it creates a BIT which is an encapsulation of an array with n positions numbered from 1 to n. Then assigns 1 the positions

(Lines 1 to 5 in Figure 3). In the searching phase, for each candidate position i, the algorithm computes the rank of each symbol T_i+j , 0 ≤ j ≤ m − 1 using sumUpT o(i + j). After checking if there is a match at position i, the BIT must be updated in each iteration to consider symbol T_i+m (line 7 in Figure 3). And the BIT must be updated so it does not consider the position i in the next search window (line 9 in Figure 3).

Figure 3: BIT based algorithm: bitBA.

3.1.Experiments on Artificial Data

In this section, we describe the experimental setup we designed to evaluate the performance of the proposed algorithms. We compare our algorithms with two baseline algorithms: The naive algorithm, which we call naiveA, and updateBA, presented in ^[26]. The former, whose time complexity is Θ(nm lg m), considers all possible positions in the text and, for each one of them, verifies if there is a match in Θ(m lg m + m) time. The latter algorithm, whose time complexity is Θ(nm), is based on linear update and verification.

We present the experimental framework (Section 3.1.1) and describe the data generation (Section 3.1.2). Then, we discuss the results obtained (Section 3.1.3). Finally we show the results of the experiments intended to study how the algorithms segtreeBA and bitBA behave in the worstcase scenario for all experiment instances (Section 3.1.4).

3.1.1. Experimental setup

Hardware and software: All the algorithms were implemented using C++. The computer used for the experiments was a Lenovo ThinkPad with a processor Intel(R) Core(TM) i7 4600u CPU @ 2.10GHz 2.69 GHz and installed RAM memory of 8GB. The computer was running 64-bit Linux Ubuntu 14.04.5 LTS. The C++ compiler version was g++ (Ubuntu 4.8.4-2ubuntu1 14.04.3) 4.8.4.

Parameters: To show how our solution behaves with different configuration of the different parameters, we perform five types of experiments. In each experiment, we vary one of the given parameters n, m, δ, ϒ and σ, and let the other four parameters fixed at a given value. We chose the fixed values after several attempts via try and error to find values that produced results varying from no matches to matches near the value of n. For each experiment type, we performed five different experiments and took the median as the value to plot, making the median of five experiments the representative value for a experiment configuration of values n m, δ,ϒ and σ. The variation of the parameter values for each experiment type is presented in Table I.

Table I: Experimental values of n m, δ,γ and σ

3.1.2. Random data generation

An experiment consists of two stages. The first stage is the pseudo-random generation of a text T of length n and the pattern P of length m. The second stage is the execution of the algorithms on the generated strings P and T . The random generation of each character of both the pattern P and the text T is done by calling a function that pseudo-randomly and selects a number between 1 and σ with an uniform probability distribution, i.e., all symbols have the same probability to appear in a position and for that reason, on average, every symbol in the alphabet will appear with the same frequency on an arbitrary generated string.

3.1.3. Experimental results and analysis

The first result to highlight is the fact that, in every experiment, the naive algorithm always has the worst performance, as expected. We found that the size of the alphabet and the parameters δ and ϒ have practically no impact on the execution time of any of the algorithms, they all show nearly constant time behavior. Figures 4a and 4b verify the theoretical complexity analysis that states that n and m are the parameters that really determine the growth in the execution time of all the algorithms. In Figure 4a, m is a constant and n is a variable while in Figure 4b, n is a constant and m is a variable. It is important to notice that, under these conditions, the graphs are expected to be linear and the experiments verify that.

Figure 4: Experimental results of comparing the four algorithms by varying different parameters

In the figures where we show the result of varying the parameter n and the parameter m, (Figures 4a-4b), we can see that the best two algorithms are the based on data structures (segtreBA and bitBA). This despite the fact that these two algorithms have a higher upper bound on their complexities in relation with the first two algorithms (naive A and updateBA). This result can be explained by the fact that the lower bound on the data structure based algorithms is considerably lower in comparison with the other two. The lower bound of the data structures based algorithms is Ω(n lg n) and the lower bound of the naiveA and update BA is the same as their upper bound meaning they are Θ(nm lg m) and Θ(nm) respectively. This can be understood by taking into account that the first two algorithms check for a match after a natural representation of every window is completely obtained; on the contrary, data structure based algorithms break the calculation of a given natural representation of a window if at some point the δ or ϒ restriction do not hold.

Given the result of the experiments, it is safe to say that the algorithms based on data structures are faster in most cases, especially if they are going to be used in applications where very few matches are expected to appear. This is due to their lower bound of complexity. We test two different implementations of the segment tree data structure: one based on classes and pointers, and the other based on an array. Ultimately, we recommend to chose the array based as representative for the segment tree based solution and the experiments plots show their results. The array-based segment tree is almost twice time faster than the classes-based implementation.

3.1.4.Worst case experiments on segtreeBA and bitBA

Taking into account that the first two algorithms, naiveA and updateBA both have complexities in Big Theta notation, i.e. their worst case is the same as their best case, the experiments described so far are enough for their experimental analysis. For the data structures based algorithms a more particular kind of experiment is needed, i.e. the worst case experimental analysis. For this algorithms the worst case is when there is a match in every candidate position. An easy way to generate data for the worst case is when all the symbols in both the pattern P and the text T are the same. Other way to generate worst cases scenarios for this two algorithms is when either both P and T are strictly increasing or both are strictly decreasing. Results from this experiments show a fast degradation in experimental performance of the segtreeBA algorithm, but a very slow degradation of the bitBA algorithm. Results of this last experiments are shown in Figures 4c and 4d.

3.2. Applications

In this section we show a couple of applications of the defined problem, in music and finance.

3.2.1.Application in music

For the music application example, we choose the main theme from The Imperial March, soundtrack of the film series Star Wars ^[17] composed by John Williams ^[16] also known as the Darth Vader’s theme because it represents him. This melody sounds every time this villain has a significant scene. Here we use an integer alphabet abstraction of a music piece, where each note of the melody is an integer. This abstraction of music takes into account only the pitch leaving out other aspects as silences, note duration, harmony, or instrumentation, but it gives a very good idea of the possible applications in music retrieval. The alphabet for music applications could be for example the given by the MIDI (Musical Instrument Digital Interface) technical standard ^[1], ^[28]. In the MIDI standard, the first note, 0 is a C note of the octave 0 (the lowest octave), note 1 is a C # of the same octave and so on. There could be up to note 127 which will be a G in the 10th octave.

We draw an example of δϒ -OPM with the same musical piece. We consider a 66-pitch excerpt of the main melody as the text T = T _0...65 , and from the same except we extract T_42...65 as the pattern P (see Figure 5a). For δ = 8 and ϒ = 32, we found a match in position 18 which for professional musicians, and even non professional musicians, sounds very similar to the pattern. Namely,Gabriela Rojas, a professional musician from the National University of Colombia Conservatory found the match similar to the pattern. The parameters δ and γ were chosen by attempting different values of both starting from 0 and increasing them until more matches were found. Furthermore, we can see in Figure 5a how similar the pitches of the pattern and the match are. In Figure 5b we show the similarity of their natural representation . This gives us an idea of possible applications in musical retrieval of approximate string matching. This can be useful for the advanced music students in order to help them with the theoretical analysis of the scores so they can look for melodic similarities or differences either in the same piece or comparing different pieces.

Figure 5: Darth Vader’s theme from Star Wars by John Williams (Excerpt).

3.2.2. Application in finance

For the finance application we choose to analyse the stock price of the Facebook company. We take the history of the stock price of Facebook from May 18 2012 to March 31 2017 as the text T (the size of this text is 1225). As the pattern, we take the 21-day period starting in February 28 2017 up to March 28 2017. Take into account that not all days the stock actions change, for that reason we choose 21 days which is approximately the amount of days the stock actions change in a month. In Figure 6a we show the pattern and the portion of the text that we found to be the most similar to the pattern. In this figure we omit the y and x axes labels because we want to show the similarity in shape of the pattern and the search window, not the similarity in absolute values which indeed is quite different. In fact the values in the pattern to search are values lower than 34 and the text window found has values greater than 100. Finally, in Figure 6b we show the natural representation (or ranks) of both the pattern P and the match found. We can see that they have a similar structure. We selected the pattern randomly and then attempted to find its matches with different values for δ and ϒ. Given that a 21 day period is not a short period, it was expected that we just found one match in the given text window.

Figure 6: Stock price of the Facebook company from May 18 2012 to March 31 2017.