一种优化多重过滤的序列查询算法

作     者：戴东波 汤春蕾 邱伯仁 熊赟 朱扬勇 Dai Dongbo;Tang Chunlei;Qiu Boren;Xiong Yun;Zhu Yangyong

作者机构：复旦大学计算机科学技术学院上海200433 

基　　金：上海市重点学科建设基金项目(B114) 上海市科委基金项目(08511500203)~~ 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2010年第47卷第10期

页      码：1785-1796页

摘      要：序列数据一类重要的数据类型,在文本、Web访问日志文件、生物数据库等应用中普遍存在,对其进行相似性查询是一种获取有用信息的重要手段.在大型序列数据库中进行高效相似性查询的关键因素之一就是查询算法的过滤能力,即设计能快速过滤与查询序列不相关序列集的过滤器十分重要.提出了结合序列距离的度量性质和序列自身特征的多重过滤算法SSQ_MF,SSQ_MF使用了长度过滤器、前缀过滤器和基于参考集的过滤器,使得算法过滤能力较基于单一过滤器算法进一步增强.此外,设计了有关数据结构对查询数据库的一些统计信息进行了预计算和保存,有效估计了各过滤器的过滤集大小,并构建了一个由过滤集大小确定的最优过滤顺序模型,使得算法的过滤代价最低.实验结果表明,算法SSQ_MF的查询性能优于单一过滤器算法和随机过滤顺序的多过滤器算法.

主 题 词：序列数据 相似性查询 过滤器 过滤顺序 度量空间 

学科分类：0810[工学-土木类] 12[管理学] 1201[管理学-管理科学与工程类] 0808[工学-自动化类] 0839[0839] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 

核心收录：

馆 藏 号：203487624...