A Fast Processing Algorithm on Section Disjoint Query of Data Stream

Disjoint query has played a very important role in the research about similarity match over subsequence of data stream, such as sensor network, data mining and so on. But the existing research did not focus on the disjoint query which is executed for elements of data stream in the fixed-length section. Running Spring algorithm for all the elements in every section directly is the NAIVE algorithm. But this algorithm does not have the characteristic of incremental computation, so it has redundant operation. The boundary path technology is proposed in this paper to deal with this redundant operation. The NAIVE algorithm can get the disjoint query results of current section based on the ones of previous section and need not performing for every element in current section by using this technology, so it has the characteristic of incremental computation. The FSDQ algorithm, which has the characteristic of incremental computation, is proposed by improving NAIVE algorithm with the boundary path technology. Extensive experiments on real and synthetic data sets show that the FSDQ algorithm is an effective way to solve the problem of section disjoint query over data stream, and it can reduce redundant operations the NAIVE algorithm has and meet the requirements of practical application.