论文部分内容阅读
基于可能世界的不确定集合的相似查询，从语义上或者从计算方法的角度来看，都有别于传统的确定型集合上的技术．由于集合中的项存在不确定性，即一个项出现在集合中是有一定概率的，使得传统处理集合的技术不再适用．提出了一个基于可能世界的集合期望相似度的度量公式．在期望的度量公式中，如果一对集合（X,Y）的期望相似度大于给定的阈值τ∈（0,1），则被称为相似集合对．一般的算法，在基于可能世界的情况下计算不确定集合的期望相似度，其复杂度是指数级的．提出了利用动态规划来计算集合期望相似度的算法，该算法的复杂度是多项式级别，