{'fraction_non_alphanumeric': 0.036071549677856904, 'fraction_numerical': 0.023016276703967446, 'mean_word_length': 4.426172953081877, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
When to Update the sequential patterns of stream data?

In this paper, we first define a difference measure between the old and new sequential patterns of stream data, which is proved to be a distance. Then we propose an experimental method, called TPD (Tradeoff between Performance and Difference), to decide when to update the sequential patterns of stream data by making a tradeoff between the performance of increasingly updating algorithms and the difference of sequential patterns. The experiments for the incremental updating algorithm IUS on two data sets show that generally, as the size of incremental windows grows, the values of the speedup and the values of the difference will decrease and increase respectively. It is also shown experimentally that the incremental ratio determined by the TPD method does not monotonically increase or decrease but changes in a range between 20 and 30 percentage for the IUS algorithm.


Introduction
To enhance the performance of algorithms of data mining, many researchers [1,2,3,4,5,6,7] have focused on increasingly updating association rules and sequential patterns. But if we update association rules or sequential patterns too frequently, the cost of computation will increase significantly. For the problem above, Lee and Cheung [8] studied the problem "Maintenance of Discovered Association Rules: When to update?" and proposed an algorithm called DELL to deal with it. The important problem of "When to update" is to find a suitable distance measure between the old and new association rules. In [8], the symmetric difference was used to measure the difference of association rules. But Lee and Cheung only considered the difference of association rules, and did not consider that the performance of increasingly updating algorithms will change with the size of added transactions. Ganti et al. [15,16] focused on the incremental stream data mining model maintenance and change detection under block evolution. However, they also didn't consider the performance of incremental data mining algorithms for the evolving data.
Obviously, with the increment of the size of incremental windows, the performance of incremental updating algorithms will decrease. If the difference between the new and old sequential patterns is too high, the size of incremental window will become too large, therefore the performance of incremental updating algorithm will be reduced greatly. On the other hand, if the difference is too small, the incremental updating algorithm will update the old sequential patterns very frequently, which will also consume too many computing resource. In all, we must make a tradeoff between the performance of the updating algorithms and the difference of the sequential patterns. In this paper, we use the speedup as a measure of incremental updating algorithms and define a metric distance as the difference measure to detect the change of the sequential patterns of stream data. Based on those measures, we propose an experimental method, called TPD (Tradeoff between Performance and Difference), to estimate the suitable range of the incremental ratio of stream data by making a tradeoff between the performance of the increasingly updating algorithm and the difference of sequential patterns.
By the TPD method, we estimate the suitable range of incremental ratio of stream data for the incremental updating algorithm IUS [21]. The experiments on two data sets in Section 5 show that generally, as the size of incremental windows grows, the values of the speedup and the values of the difference will decrease and increase respectively. By the experiments, we can discover that as the size of original windows increases, the incremental ratio determined by TPD method does not monotonically increase or decrease but changes in a range between 18 and 30 percentage for the IUS algorithm.
The rest of this paper is organized as follows. In Section 2 we compare our work with the related work of the incremental mining for stream data. Section 3 formally gives the notion and definitions in this paper and defines the difference measure between the old and new sequential patterns. In Section 4, by making a tradeoff between the performance of increasingly updating algorithm and the difference of sequential patterns, we propose a method, called TPD (Tradeoff between Performance and Difference), to decide when to update sequential patterns of stream data. We experimentally verify the proposed method on two sets of GSM alarm data in Section 5. Finally, we give the conclusion in Section 6.

Related work
Lee and Cheung studied the problem of "When to update association rules" to avoid the overhead updating the rules too frequently in [8]. But they only studied updating association rules in the transaction data, while we focus on studying when to update the sequential patterns of stream data. They used the ratio |L∆L`|/|L as the difference measure of association rules, but in this paper we not only define a difference measure of sequential patterns but also prove that this measure is a distance.
In [9], Agrawal et al. proposed an indexing method for time sequences for processing similarity queries, which uses the Discrete Fourier Transform (DFT) to map time sequences to the frequency domain. In [10], Agrawal proposed a new model of similarity of time sequences that captures the intuitive notion that two sequences should be considered similar if they have enough non-overlapping time-ordered pairs of subsequences those are similar.
In [11], Datar et al. studied the problem of maintaining aggregates and statistics over data streams, proposed the sliding window model and formulated the basic counting problem whose solution can be used as a building block for solving most of the problems.
Mannila et al. [13] used an edit distance notion for measuring the similarity of events sequences, which is defined as the cost of the cheapest possible sequence of operations that transforms a sequence to another. The edit distance can be computed using dynamic programming algorithm. Later Mannila and Seppanen [14] described a simple method for similarity search in sequences of events, which is based on the use of random projections. Das et al. [12] also introduced the notion of an external measure between attribute A and attribute B, defined by looking at the values of probe functions on sub-relations defined by A and B.
Ganti et al. [15] studied the incremental stream data mining model maintenance and change detection under block evolution. They adopted the FOCUS framework [16] for change detection, which measures the deviation between two datasets first by the class of decision tree models and then by the class of frequent itemsets. Domingos and Hulten [17] introduced Hoeffding trees and proposed a method for learning online from the high-volume data streams that are increasingly common, called VFDT (very Fast Decision Tree learner). Later Hulten et al. [18] proposed an efficient algorithm for mining decision trees from continuously-changing data streams, based on the ultra-fast VFDT decision tree learner, which was called CVFDT. Corters and Preginbon [19] have discussed the statistical and computational aspects of deploying signature-based methods in the applications of telecommunications industry.

Stream data model
An stream tuple and its length, An stream queue and its length, An stream viewing window and its size 1.) An stream event is defined as E i =<e i , t n >, i, n=1,2,3,…, where e i is an stream event type, including alarm event type, call details record type, financial market data type etc. and t n is the time of stream event type occurring. 2.) An stream tuple is defined as Q i =( ( e k1 , e k2 , …… , e km ), t i ), i,m=1,2,3,…; k1,k2,…,km=1,2,3,… , where 'e k1 , e k2 ,……, e km ' are the stream event types which concurrently occur at the time t i . An stream tuple can be represented by an stream event i.e. Q i =(< e k1 , t i >,< e k2 , t i > ,……, <e km , t i >)=( E k1 , E k2 , ….. , E km ). If an stream tuple Q i only contains one stream type, then Q i =(( e k1 ), t i )=( < e k1 , t i >)= E k1 .
3.) The length of stream tuple is |Q i |=|( e k1 , e k2 , ……, e km )|=m, which is the number of the stream event types contained in the stream tuple.

5.)
The length of stream queue is defined as | S ij |=|<Q i , Q i+1 , …, Q j >|=j-i+1, which is equal 4 to the number of stream tuple contained in stream queue.
7.) The size of stream viewing window is defined as |W k |=|<Q m ,…, Q n |d=n-m+1>|=d , where k,m,n=1,2,3, … . 8.) Given an sequence seq m =< e i1 , e i2 ,…,e im > and an stream viewing window W k , the times of the sequence seq m occurring in the W k are defined as occur (seq m, W k )=| the times of seq m occurring in W k | 9.) Given an sequence seq m =< e i1 , e i2 ,…,e im >, the support of the sequence seq m in an stream viewing window W k is defined as Figure 1 presents graphically an stream queue S 18 =< Q 1, Q 2, Q 3 , Q 4 , Q 5 , Q 6 , Q 7 , Q 8 >. The time of stream tuple Q 1 , Q 2 , … , Q 8 is that t 1 < t 2 , … ,< t 8 .In Figure 1, the stream queue S 18 can also be denoted by the stream event, S 18 =<E 2 , E 5 , E 1 , (E 3 , E 6 ), E 7 , E 9 , E 7 , E 10 >.

Estimation of the difference between the old and new sequential patterns
Before updating the frequent sequences K W L in W k , we must estimate the difference between K W L and 1 + K W L . If the difference is very large, then we should update the sequential patterns as soon as possible. But if the difference is very small, then we do not need to update the sequential patterns. In order to measure the difference between the old and new frequent sequence sets, we can define a measure as follows is the symmetric difference between We know that a measure is not necessarily a metric. A metric distance must satisfy the triangle inequality which means that for three objects A, B and C in the metric space, the distance between A and C is greater than the distance between A and B plus the distance between B and C. This property is also useful in measuring the differences between frequent sequences because that for three frequent sequences L w1 , L w2 and L w3 , if both the difference between L w1 and L w2 and the difference between L w2 and L w3 is very small, then, intuitively, the difference between L w1 and L w3 should also be small. If a difference measure between frequent sequences is a metric, then it follows from the triangle inequality that the above property holds. For the measure defined above, we can prove that it is also a metric (please see Appendix A).

The TPD (Tradeoff between Performance and Difference) method of deciding when to update sequential patterns
Lee and Cheung [8] only considered the difference between the old and new association rules, but that they didn't consider the change of the performance of incremental updating algorithms. As mentioned before, too large difference between the new and old sequential patters will result in poor performance of incremental updating algorithms, while too small difference will increase the computations lose significantly. Therefore, we must make a tradeoff between the difference of frequent sequences and the performance of increasingly updating algorithms and find the suitable range of the incremental ratio of stream data.
We propose an experimental method, called TPD (Tradeoff between Performance and Difference), to find the suitable range of incremental ratio of the initial window for deciding when to update sequential patterns of stream data. The TPD method uses the speedups as the measurement of incremental updating algorithms and adopts the measure defined in Section 3.3 as the difference between the new and old sequential patterns of stream data. With the increment of the size of incremental window, the speedup of the algorithm will decrease, while the difference of the old and new sequential patterns will increase. According to two main factors of the incremental updating algorithms, the TPD method maps the curve of the speedup and the difference changing with the size of incremental windows into the same graph under the same scale, and the points of intersection of the two curves are the suitable range of the incremental ratio of the initial windows for the increasingly updating algorithm.
In this paper, by the experiments in Section 5, we study the suitable range of incremental ratio of the initial windows for the incremental updating algorithm: IUS [21] by TPD (Tradeoff between Performance and Difference) method. In the experiments, the speedup ratio of the IUS algorithm is defined as speedup=the execution time of Robust_search / the execution time of IUS, where Robust_search is an algorithm to discover sequential patterns from stream data [20] and IUS is an increasingly updating sequential patterns algorithm based on Robust_search algorithm [21]. We use the distance i.e. d(L W k ,L W k+1 ) defined above as the difference measure between the old frequent sequences L W k and the new frequent sequences The experiments of Section 5 show that generally, as the size of incremental windows grows, the values of the speedup and the values of the difference will decrease and increase respectively. By making data transform, called Min-max normalization [22], for the values of the speedup and the difference, we can map the speedup and the difference with the increment of the size of incremental windows into the same graph under the same scale, and then from the graph we can find the intersection point of two lines, obviously, by which we can compute the suitable range of incremental ratio of the initial window to update sequential patterns according to the differences and speedups mentioned above.
The Robust_search Algorithm does compute the support of sequences in the stream queue [20], especially, which can search the support of sequences from stream queue containing noise data. But because we mainly study the problem of when to update sequential patterns, we only consider the condition that the stream queue doesn't contain noise data in this paper.
The following is IUS (Incrementally Updating Sequences) algorithm proposed in [21]. In this paper, we rewrite the IUS algorithm using the stream data model. The input of the algorithm is the window W k , , the incremental window ∆W k+1 , and two parameters: Min_supp and Min_nbd_supp, where W k+1 = W k +∆W k+1 . The output of the algorithm is the frequent and the negative border sequences NBD(W k+1 ).
else { Prune the seq m and the sequence containing seq m from L wk and NBD(W k ); 14.

Experiments
We conducted a set of experiments to find when to update sequential patterns for stream data. In the experiments, we compare the execution time of the IUS algorithm with that of the Robust_search algorithm [21] in the view window W i . The speedup ratio is defined in Section 4. We also use the distance in Section 3.3 as the difference measure between the sequential patterns of W k and W k+1 .  The size of incremental windows    The Speedup graph in Figure 4, 5, … , 11 is the speedup of IUS Algorithm [20] to the Robust_search Algorithm [21] with the size of incremental windows. The Difference graph in Figure 4, 5 , … , 11 is the difference measure of frequent sequences between the initial window and the incremental windows with the size of incremental windows. Mapping the Speed and difference graphs into the same scale graph forms Mapping graph in Figure 4, 5, … , 11.
In order to make the speed graph and difference graph have the same scale, we adopt the data normalization methods called Min-max normalization [22], which performs linear transformation of the origin data. Suppose that min A and max A are the minimum and maximum values of an attribute A. Min-max normalization maps a value ν of A to ν` in the range [new_min A , new_max A ] by computing ( ) In the experiments of this paper, we map the value of difference and speedup into the same range [0,1] by let new_min A =0 and new_max A =1. By data transformation above, we could map the broken lines of the difference and speedup into the same graph i.e. Mapping Graph under the same scale. The intersection of the two broke lines is the tradeoff size of the incremental window between the difference and speedup, by which we can compute the proper incremental ratio of incremental windows.
In the experiment 1 on data_1, we choose the initial window |W 0 |=20K, and update the initial sequential patterns by the incremental size of 2K, 4K, 6K, 8K, 10K, 12K, 14K, 16K, and 18K, i.e. the size of incremental window ∆W i . The results of experiment 1 are illustrated in Figure 4. In the speedup graphs with support=0.0020 and with support=0.0025, the values of the speedup of IUS algorithm will decrease with the increment of size of incremental windows ∆W i . In the difference graphs with support=0.0020 and with support=0.0025, the values of the difference will increase with the increment of the size of incremental alarm windows. In order to find the suitable size of incremental windows, we first map the graphs of speedup and difference into the same graph by the data transform above, then find the intersection point of the two lines. The intersection point is a tradeoff between the speedup and the difference, and is a suitable point to update sequential patterns. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 4, the intersection point is about 6K, so the suitable range of incremental ratio of initial window is about 30 percent of initial windows W 0 .
In the experiment 2 on data_2, we choose the initial window |W 0 |=20K, and update the initial sequential patterns by the incremental size of 2K, 4K, 6K, 8K, 10K, 12K, 14K, 16K, and 18K, i.e. the size of incremental window ∆W i . The results of experiment 2 are illustrated in Figure 5. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 5, the intersection point is about between 8.5K and 9K, so the suitable range of incremental ratio of initial window is about 42.5 to 45 percent of initial windows W 0 In the experiment 3 on data_1, we choose the initial window |W 0 |=40K, and update the initial sequential patterns by the incremental size of 4K, 8K, 16K, 20K, 24K, 28K, and 32K, i.e. the size of incremental window ∆W i . The results of experiment 3 are illustrated in Figure  6. The intersection point is a tradeoff between the speedup and the difference, and is a suitable point to update sequential patterns. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 6, the intersection point is between 9K and 10K, so the suitable range of incremental ratio of initial window is about 22.5 to 25 percent of initial windows W 0 .
In the experiment 4 on data_2, we choose the initial window |W 0 |=40K, and update the initial sequential patterns by the incremental size of 4K, 8K, 16K, 20K, 24K, 28K, and 32K, i.e. the size of incremental window ∆W i . The results of experiment 4 are illustrated in Figure  7. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 7, the intersection point is about 6K, so the suitable range of incremental window of initial window is about 15 percent of initial windows W 0 In the experiment 5 on data_1, we choose the initial window |W 0 |=50K, and update the initial patterns by incremental size of 5K, 10K, 15K, 20K, 25K, 30K, 35K 40k, and 45k, i.e. the size of incremental window ∆W i . The results of experiment 5 are illustrated in Figure 8.
In the mapping graphs with support=0.0020 and support=0.0025 of Figure 8, the intersection point is between 15K and 18K, so the suitable range of incremental window of initial window is about 30 to 36 percent of initial windows W 0 . In the experiment 6 on data_2, we choose the initial window |W 0 |=50K, and update the initial sequential patterns by the incremental size of 5K, 10K, 15K, 20K, 25K, 30K, and 35K, i.e. the size of incremental window ∆W i . The results of experiment 6 are illustrated in Figure  9. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 9, the intersection point is between 15K and 18K, so the range of incremental window of initial window is about 30 to 36 percent of initial windows W 0 .
In the experiment 7 on data_1, we choose the initial window |W 0 |=60K, and update the initial sequential patterns by the incremental size of 4K, 8K, 16K, 20K, 24K, 28K, 32K, and 36K, i.e. the size of incremental window ∆W i . The results of experiment 7 are illustrated in Figure 10. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 10, the intersection point is between 10K and 12K, so the suitable range of incremental window of initial window is about 16.7 to 20 percent of initial windows W 0 In the experiment 8 on data_2, we choose the initial window |W 0 |=60K, and update the initial sequential patterns by the incremental size of 4K, 8K, 16K, 20K, 24K, 28K, 32K, and 36K, i.e. the size of incremental window ∆W i . The results of experiment 8 are illustrated in Figure 11. In the mapping graphs with support=0.0020 and support=0.0025 of Figure 11, the intersection point is between 10K and 12K, so the suitable range of incremental ratio of initial window is about 16.7 to 20 percent of initial windows W 0 .
In all, by the experiments above, in general, as the size of incremental windows grows, the values of the speedup and the values of the difference will decrease and increase respectively. Based on the TPD method we proposed, it is shown experimentally that the suitable range of incremental ratio of initial windows to update is about 20 to 30 percent of the size of initial windows for the IUS algorithm.

Conclusion
In this paper, we first proposed a metric distance as the difference measure between the sequential patterns. Then we present an experimental method, called TPD (Tradeoff between Performance and Difference), to decide when to update sequential patterns of stream data.
The TPD method can determine a reasonable ratio of the size of incremental window to that of original window for incremental updating algorithms, which may depend on the concrete data. We also do eight experiments of IUS algorithm [20] to verify the TPD method. From the experiments, we can see that as the size of original windows increases, the incremental ratio determined by the TPD method does not monotonically increase or decrease but changes in a range between 20 and 30 percentage.
So in practice, when we do incremental data mining for some kind of stream data, by use of the TPD method, we can do some initial experiments to determine a suitable incremental ratio for this kind of data and then use this ratio to decide when to update sequential patterns in the incremental data mining. Finally, we hope that our method could be extended to some other increasingly updating algorithms in future.
Appendix A Theorem 1. Given two sets A and B, the measure defined as follows is a distance.
Proof. First, we can easily prove that the following two properties hold for the measure defined above.
Now we only need to prove that the triangle inequality also holds for this measure.
Namely, given three sets A, B and C, we will prove that ) , Assume that the sets A, B and C are as follows.
By the figure above and the definition of the measure d, we know that proving inequality (A.1) is equivalent to proving the following inequality. The proof of inequality (A.2) can be divided into the following four cases. . The proof in this case is similar to that in Case 3 and so we are done.