An Efficient Incremental Mining Algorithm for Discovering Sequential Pattern in Wireless Sensor Network Environments

Abstract

Wireless sensor networks (WSNs) are an important type of network for sensing the environment and collecting information. It can be deployed in almost every type of environment in the real world, providing a reliable and low-cost solution for management. Huge amounts of data are produced from WSNs all the time, and it is significant to process and analyze data effectively to support intelligent decision and management. However, the new characteristics of sensor data, such as rapid growth and frequent updates, bring new challenges to the mining algorithms, especially given the time constraints for intelligent decision-making. In this work, an efficient incremental mining algorithm for discovering sequential pattern (novel incremental algorithm, NIA) is proposed, in order to enhance the efficiency of the whole mining process. First, a reasoned proof is given to demonstrate how to update the frequent sequences incrementally, and the mining space is greatly narrowed based on the proof. Second, an improvement is made on PrefixSpan, which is a classic sequential pattern mining algorithm with a high-complexity recursive process. The improved algorithm, named PrefixSpan+, utilizes a mapping structure to extend the prefixes to sequential patterns, making the mining step more efficient. Third, a fast support number-counting algorithm is presented to choose frequent sequences from the potential frequent sequences. A reticular tree is constructed to store all the potential frequent sequences according to subordinate relations between them, and then the support degree can be efficiently calculated without scanning the original database repeatedly. NIA is compared with various kinds of mining algorithms via intensive experiments on the real monitoring datasets, benchmarking datasets and synthetic datasets from aspects including time cost, sensitivity of factors, and space cost. The results show that NIA performs better than the existed methods.

Keywords: WSNs; big data; incremental mining; prefix projection database; reticular sequence tree.

Figure 1

The updated database UD which is the combination of SDB and sdb.

Figure 2

Reticular Sequence Tree.

Figure 3

The Construction Process.

Figure 4

The Counted Results.

Figure 5

Diamond Structure.

Figure 6

The Monitoring Data Flow.

Figure 7

The Runtimes on the Dataset of $\left|UD\right|=100K$ with $N=100K$.

Figure 8

The Runtimes on the Dataset of $\left|UD\right|=100K$ with $N=10K$.

Figure 9

The Runtimes on the Dataset of $\left|UD\right|=200K$ with $N=10K$.

Figure 10

The Runtime Comparison with Three Novel SPM Algorithms.

Figure 11

The Runtime Comparison with the Practical SPM Algorithms.

Figure 12

The Runtimes on BMSWebView-1 with TIR = 0.1% and PIR = 0.01%.

Figure 13

The Runtimes on Kosarak with TIR = 0.1% and PIR = 0.01%.

Figure 14

The Runtimes on the Synthetic Dataset 1 with $R_{sdb}=5\%,R_{new}=50\%$.

Figure 15

The Runtimes on the Synthetic Dataset 2 with $R_{sdb}=5\%,R_{new}=50\%$.

Figure 16

The Runtimes with the Different Settings of $R_{sdb}$.

Figure 17

The Runtimes with the Different Settings of $R_{new}$.

Figure 18

The Amounts of Potential Frequent Sequences on the Different minsups.

Figure 19

The Memory Usage on the Dataset of $\left|UD\right|=100K$ with $N=100K$.

Figure 20

The Memory Usage Comparison with Three Novel SPM Algorithms.