基于噪声数据流的高效相似匹配算法  

An Efficient Similarity Matching Algorithm on Noised Data Streams

作　　者：郑凯[1] 宫学庆[1] 闫莺[1] 周红福[1] 周傲英[1] 

机构地区：[1]复旦大学计算机科学与工程系,上海,200433 复旦大学计算机科学与工程系,上海,200433 复旦大学计算机科学与工程系,上海,200433 复旦大学计算机科学与工程系,上海,200433 复旦大学计算机科学与工程系,上海,200433

出　　处：《计算机研究与发展》2007年第z3期511-515,共5页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60673134)

摘　　要：由于在金融分析、环境监测、网络服务等重要领域的良好应用前景,基于数据流的相似匹配算法成为数据库研究的热点之一.在实际应用中,数据流噪声大量存在且难以被完全过滤,因此,处理噪声数据流上的相似匹配问题显得尤其重要.为解决该问题,首先提出了一种新的距离定义,K-Match距离,由于其可以避免噪声数据参与运算,因而具有较强的抗噪性能.在此定义基础上,提出了一种高效的流式匹配算法SKM. SKM通过保留历史信息,能够随着数据流的更新及时返回匹配结果.最后,通过实验进一步证明,该算法能够有效地在噪声数据流中找到相似子序列.

关 键 词：数据流 相似度 距离 噪声 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]