高级检索
    王少鹏, 闻英友, 赵宏. 基于LCSS的数据流相似性查询处理算法研究[J]. 计算机研究与发展, 2015, 52(9): 1976-1991. DOI: 10.7544/issn1000-1239.2015.20140479
    引用本文: 王少鹏, 闻英友, 赵宏. 基于LCSS的数据流相似性查询处理算法研究[J]. 计算机研究与发展, 2015, 52(9): 1976-1991. DOI: 10.7544/issn1000-1239.2015.20140479
    Wang Shaopeng, Wen Yingyou, Zhao Hong. Similarity Query Processing Algorithm over Data Stream Based on LCSS[J]. Journal of Computer Research and Development, 2015, 52(9): 1976-1991. DOI: 10.7544/issn1000-1239.2015.20140479
    Citation: Wang Shaopeng, Wen Yingyou, Zhao Hong. Similarity Query Processing Algorithm over Data Stream Based on LCSS[J]. Journal of Computer Research and Development, 2015, 52(9): 1976-1991. DOI: 10.7544/issn1000-1239.2015.20140479

    基于LCSS的数据流相似性查询处理算法研究

    Similarity Query Processing Algorithm over Data Stream Based on LCSS

    • 摘要: 数据流相似性查询广泛应用于智能家居、环境监测等领域.当前以LCSS(longest common subsequence)作为相似性测度函数的研究并不多.NAIVE算法使用基本动态规划方法计算测度函数值,通过该值与相似阈值的比较得到查询结果,对基于LCSS的数据流相似性查询问题进行研究.针对NAIVE算法必须在动态规划矩阵所有成员取值的计算完成后才能得到查询结果的缺点,提出了一种基于PS(possible solution)-CC(column critical)域优化策略的数据流相似性查询处理算法.该算法划定了每个窗口上动态规划矩阵的PS域和CC域,很好地利用了这2个域中成员所具有的性质和相似性查询的特点,无须获得测度函数的最终值便可得到查询结果,省略了很多矩阵成员的计算.实验部分证明了该算法的有效性,与同类算法相比,在处理具有更高精度结果要求的查询时效果更好.

       

      Abstract: Nowadays similarity query about data stream has been essential in many applications, like smart home and environmental monitoring. However, few of the current relevant researches take LCSS (longest common subsequence) as the similarity measurement function. The NAIVE algorithm gets the query results by comparing the threshold and the value of measurement function which is obtained based on the basic dynamic programming method. The similarity query over data stream based on the LCSS is considered in this paper. The D2S-PC algorithm is proposed to overcome the drawback that the query result cannot be gotten until the calculations on all the elements in the full dynamic programming matrix are finished. It defines the PS and CC domains of the matrix over every window, and utilizes the characteristics of the similarity query and matrix members in these two domains effectively. By taking this algorithm, the similarity query results can be obtained before the final length of LCSS is calculated. Compared with the original algorithm, it reduces the computations about the members in the matrix greatly. Extensive experiments on real and synthetic datasets show that the D2S-PC algorithm is effective in handling the similarity query over data stream based on the LCSS in the condition of more precise query results, and can meet the requirements of practical applications.

       

    /

    返回文章
    返回