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

摘要：

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

关键词：相似查询、期望相似度、动态规划、不确定集值

所属期刊栏目：23

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金60803003,60970124

在线出版日期：2012-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：1588-1601