不确定集值数据的高效相似查询

• 作者: 洪银杰 陈刚 陈珂
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 相似查询 期望相似度 动态规划 不确定集值
• 年，卷（期）: 2012,（6）
• 所属期刊栏目: 数据库技术
• 页码范围: 1588-1601
• 分类号: TP311
• 字数: 9413字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04110

摘要

基于可能世界的不确定集合的相似查询,从语义上或者从计算方法的角度来看,都有别于传统的确定型集合上的技术.由于集合中的项存在不确定性,即一个项出现在集合中是有一定概率的,使得传统处理集合的技术不再适用.提出了一个基于可能世界的集合期望相似度的度量公式.在期望的度量公式中,如果一对集合(X,Y)的期望相似度大于给定的阈值τ∈(0,1),则被称为相似集合对.一般的算法,在基于可能世界的情况下计算不确定集合的期望相似度,其复杂度是指数级的.提出了利用动态规划来计算集合期望相似度的算法,该算法的复杂度是多项式级别,极大地减少了计算时间.实验结果表明了基于该算法查询的可用性和高性能.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈刚	浙江大学计算机科学与技术系	204	2984	32.0	47.0
2	陈珂	浙江大学计算机科学与技术系	22	25	4.0	4.0
3	洪银杰	浙江大学计算机科学与技术系	2	2	1.0	1.0