期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

一种序列模式的相似性查询算法

A Similarity Query Algorithm in Sequential Patterns
下载PDF
导出
摘要 数值型序列在很多应用中存在,如超市的POS销售记录和证券交易所的股票买卖数据等.在此类数据中查询与给定序列模式相似的子模式具有重要的现实意义.提出一种趋势融合的序列相似性查询算法NSS_QA,首先对所有序列进行单调区间的"融合"处理,然后根据各区间的长度比例和幅度比例产生序列模式的候选集,最后定义了一种新的相似性度量来计算并返回查询结果.该查询算法能找到与给定序列模式"放大"或"缩小"的模式结果.实验结果表明,提出的算法能找到在总体形状上与给定序列模式相似的所有模式,且在时间上具有较好的伸缩性能. 数值型序列在很多应用中存在,如超市的POS销售记录和证券交易所的股票买卖数据等.在此类数据中查询与给定序列模式相似的子模式具有重要的现实意义.提出一种趋势融合的序列相似性查询算法NSS_QA,首先对所有序列进行单调区间的"融合"处理,然后根据各区间的长度比例和幅度比例产生序列模式的候选集,最后定义了一种新的相似性度量来计算并返回查询结果.该查询算法能找到与给定序列模式"放大"或"缩小"的模式结果.实验结果表明,提出的算法能找到在总体形状上与给定序列模式相似的所有模式,且在时间上具有较好的伸缩性能.
作者 汤春蕾 董家麒 戴东波 朱扬勇
机构地区 复旦大学计算机科学技术学院 上海大学计算机工程与科学学院
出处 《计算机研究与发展》 EI CSCD 北大核心 2011年第S3期132-139,共8页 Journal of Computer Research and Development
基金 国家自然科学基金项目(60903075) 上海市重点学科建设基金项目(B114)
关键词 序列模式 相似性查询 相似性度量 sequential pattern similarity query similarity measure
分类号 TP3 [自动化与计算机技术—计算机科学与技术]
  • 相关文献

参考文献16

  • 1Gusfield D.Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. . 1997
  • 2X Golay,S Kollias,G Stoll,et al.A new correlation-based fuzzy logic clustering algorithm for fMRI. Proceedings of Magnetic Resonance in Medicinet . 1998
  • 3Han W S,Lee J,Moon Y S.Ranked subsequence matching in time-series databases. Proc of the 33rd Int Conf on Very Large Data Bases . 2007
  • 4Fu A W,Keogh E J,Lau L Y,et al.Scaling and time warping in time series quering. Proc of the VLDB . 2005
  • 5Udechukwu A,Barker K,Alhajj R.Discovering all frequent trends in time series. Proceedings of the Winter International Synposium on Information and Communication Technologies . 2004
  • 6王国仁,葛健,徐恒宇,郑若石.基于二分频率变换的序列相似性查询处理技术[J].软件学报,2006,17(2):232-241. 被引量：8
  • 7Pei J,Han J,Mortazavi-Asl B,et al.Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth. Proceedings of the International Conference on Data Engineering . 2001
  • 8CHEN L,OZSU M T,ORIA V.Robust and fast similarity searchfor moving object trajectories. Proceedings of the ACM SIG-MOD Conference . 2005
  • 9Vlachos M,Kollios G,Gunopulos D.Dicovering similar multidimensional trajectories. Proc of ICDE . 2002
  • 10ZHU Yunyue,Shasha D.Warping indexes with envelopetransforms for query by humming. Proc ACM SIGMODInt Conf on Management of Data . 2003

二级参考文献87

  • 1王国仁,葛健,徐恒宇,郑若石.基于二分频率变换的序列相似性查询处理技术[J].软件学报,2006,17(2):232-241. 被引量：8
  • 2The human genome project (HGP).2006.http://www.nhgri.nih.gov/
  • 3National Center for Biotechnology Information.Genbank database.2005.http://www.ncbi.nlm.nih.gov/
  • 4Benson DA,Karsh-Mizrachi I,Lipman DJ,Ostell J,Rapp BA,Wheeler DL.Genbank.Nucleic Acids Research,2000,28(1):15-18.
  • 5Gusfield D.Algorithms on Strings,Trees and Sequences:Computer Science and Computational Biology.Cambridge:Cambridge University Press,1997
  • 6Myers E.An O(ND) difference algorithm and itsvariations.Algorithmica,1986,1(2):251-266.
  • 7Myers E.A sublinear algorithm for approximate keyword matching.Algorithmica,1994,12(4-5):345-374.
  • 8Baeza-Yates RA,Navarro G.Faster approximate string matching.Algorithmica,1999,23(2):127-158.
  • 9Kahveci T,Singh AK.An efficient index structure for string databases.In:Apers P,Atzeni P,Ceri S,Paraboschi S,Ramamohanarao K,Snodgrass R,eds.Proc.of the 27th Int'l Conf.on Very Large Data Bases (VLDB 2001).Roma:Morgan Kaufmann Publishers,2001.351-360.
  • 10Sun H,Ozturk O,Ferhatosmanoglu H.CoMRI:A compressed muti-resolution index structure for sequence similarity queries.In:Peter M,Xu Y,ed.Proc.of the 2nd IEEE Computer Society Bioinformatics Conf.(CSB 2003).Califonia:IEEE Computer Society,2003.553-559.

共引文献19

计算机研究与发展
2011年 第S3期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部