• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
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

Similarity Query Processing Algorithm over Data Stream Based on LCSS

More Information
  • Published Date: August 31, 2015
  • 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.
  • Related Articles

    [1]Shi Haihe, Lan Sunwen, Liu Riming, Shi Haipeng, Wang Lan, Zhong Linhui. Unified Formal Construction and Isabelle Verification of the Dynamic Programming Algorithms for Biological Sequence Alignment[J]. Journal of Computer Research and Development, 2025, 62(1): 119-131. DOI: 10.7544/issn1000-1239.202330698
    [2]Shi Haihe, Zhou Weixing. Design and Implementation of Pairwise Sequence Alignment Algorithm Components Based on Dynamic Programming[J]. Journal of Computer Research and Development, 2019, 56(9): 1907-1917. DOI: 10.7544/issn1000-1239.2019.20180835
    [3]Wang Shaopeng, Wen Yingyou, Li Zhi, and Zhao Hong. A Fast Processing Algorithm on Section Disjoint Query of Data Stream[J]. Journal of Computer Research and Development, 2014, 51(5): 1136-1148.
    [4]Wang Kaiyun, Kong Siqi, Fu Yunsheng, Pan Zeyou, Ma Weidong, Zhao Qiang. Two Longest Common Substring Algorithms Based on Bi-Directional Comparison[J]. Journal of Computer Research and Development, 2013, 50(11): 2444-2454.
    [5]Wu Hao and Wu Guoqing. Dynamical Integrity of Codes: Model and Method[J]. Journal of Computer Research and Development, 2012, 49(9): 1874-1882.
    [6]Qi Yafei, Wang Yijie, and Li Xiaoyong. A Skyline Query Method over Gaussian Model Uncertain Data Streams[J]. Journal of Computer Research and Development, 2012, 49(7): 1467-1473.
    [7]Zhang Li, Zou Peng, Jia Yan, and Tian Li. Continuous Dynamic Skyline Queries over Data Stream[J]. Journal of Computer Research and Development, 2011, 48(1): 77-85.
    [8]Zhu Yangyong, Dai Dongbo, and Xiong Yun. A Survey of the Research on Similarity Query Technique of Sequence Data[J]. Journal of Computer Research and Development, 2010, 47(2): 264-276.
    [9]Wang Shuaiqiang, Ma Jun, Wang Haiyang, and Wan Jiancheng. A Novel Method for Behavioral Model Refinement Based on Genetic Programming[J]. Journal of Computer Research and Development, 2008, 45(11): 1911-1919.
    [10]Yang Wenguo, Guo Tiande, Zhao Tong. Routing Algorithms of the Wireless Sensor Network Based on Dynamic Programming[J]. Journal of Computer Research and Development, 2007, 44(5): 890-897.

Catalog

    Article views (1491) PDF downloads (750) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return