序列数据相似性查询技术研究综述

被引：13

作者：

朱扬勇

戴东波

熊赟

机构：

[1] 复旦大学计算机科学技术学院

来源：

计算机研究与发展 | 2010年 / 02期

关键词：

序列数据; 相似性度量; 距离分布; 过滤方法; 相似性查询;

D O I：

暂无

中图分类号：

TP311.13 [];

学科分类号：

1201 ;

摘要：

序列数据在文本、Web访问日志文件、生物数据库等应用中普遍存在,对其进行相似性查询是一种提取有用信息的重要手段.近年来,随着各种科学计算的发展和序列数据的大量产生,序列相似性查询已经成为数据分析领域一个研究热点.其涉及到的几个重要问题有面向各种应用领域的相似性度量及其相互之间的关系;随机序列数据中距离分布的统计信息及其对分析查询算法性能的作用;在大规模数据中,各种高效回答相似性查询的关键技术及各自的优缺点比较.总结了序列数据的分类和特点,给出了几种序列数据相似性度量和随机序列之间距离分布的统计信息,并进一步分析了这些度量之间的关系.接着给出了几种序列相似性查询的类型,以及序列相似性查询要解决的核心问题.在此基础上,针对各种序列相似性查询关键技术进行分类和评价.最后,讨论了关于序列数据相似性查询研究所面临的挑战,并归结了未来的研究方向.

引用

页码：264 / 276

页数：13

共 20 条

[1] DNA序列数据挖掘技术
朱扬勇
熊赟
[J]. 软件学报, 2007, (11) : 2766 - 2781
[2] 基于二分频率变换的序列相似性查询处理技术
王国仁
葛健
徐恒宇
郑若石
[J]. 软件学报, 2006, (02) : 232 - 241
[3] 改进的多模式匹配算法
王永成
沈州
许一震
不详
[J]. 计算机研究与发展 , 2002, (01) : 55 - 60
[4] Low distortion embeddings for edit distance
Ostrovsky, Rafail
Rabani, Yuval
[J]. JOURNAL OF THE ACM, 2007, 54 (05)
[5] Reference-based indexing for metric spaces with costly distance measures[J] . Jayendra Venkateswaran,Tamer Kahveci,Christopher Jermaine,Deepak Lachwani.The VLDB Journal . 2008 (5)
[6] Efficient large-scale sequence comparison by locality-sensitive hashing
Buhler, J
[J]. BIOINFORMATICS, 2001, 17 (05) : 419 - 428
[7] A guided tour to approximate string matching
Navarro, G
[J]. ACM COMPUTING SURVEYS, 2001, 33 (01) : 31 - 88
[8] An Index Structure for Data Mining and Clustering
Xiong Wang
Jason T. L. Wang
King-Ip Lin
Dennis Shasha
Bruce A. Shapiro
Kaizhong Zhang
[J]. Knowledge and Information Systems, 2000, 2 (2) : 161 - 184
[9] Faster approximate string matching
BaezaYates, R
Navarro, G
[J]. ALGORITHMICA, 1999, 23 (02) : 127 - 158
[10] Fast text searching[J] . Sun Wu,Udi Manber.Communications of the ACM . 1992 (10)

← 1 2 →