主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
陈珂,洪银杰,陈刚.不确定集值数据的高效相似查询.软件学报,2012,23(6):1588-1601
不确定集值数据的高效相似查询
Efficient Processing of Similarity Search on Uncertain Set-Valued Data
投稿时间:2011-02-24  修订日期:2011-05-18
DOI:10.3724/SP.J.1001.2012.04110
中文关键词:  相似查询  期望相似度  动态规划  不确定集值
英文关键词:similarity search  expected similarity  dynamic programming  uncertain set
基金项目:国家自然科学基金(60803003, 60970124)
作者单位E-mail
陈珂 浙江大学 计算机科学与技术系,浙江 杭州 310027  
洪银杰 浙江大学 计算机科学与技术系,浙江 杭州 310027  
陈刚 浙江大学 计算机科学与技术系,浙江 杭州 310027 cg@zju.edu.cn 
摘要点击次数: 2494
全文下载次数: 2580
中文摘要:
      基于可能世界的不确定集合的相似查询,从语义上或者从计算方法的角度来看,都有别于传统的确定型集合上的技术.由于集合中的项存在不确定性,即一个项出现在集合中是有一定概率的,使得传统处理集合的技术不再适用.提出了一个基于可能世界的集合期望相似度的度量公式.在期望的度量公式中,如果一对集合(X,Y)的期望相似度大于给定的阈值τ∈(0,1),则被称为相似集合对.一般的算法,在基于可能世界的情况下计算不确定集合的期望相似度,其复杂度是指数级的.提出了利用动态规划来计算集合期望相似度的算法,该算法的复杂度是多项式级别,极大地减少了计算时间.实验结果表明了基于该算法查询的可用性和高性能.
英文摘要:
      Setting similarity search on possible worlds is semantically and computationally different from the traditional technique for sets of certain data. Considering the uncertainty of items of set, i.e. there is a certain probability for an item appearing in a set, the traditional technique used for processing sets is not applicable. This paper brings forward the formulas to measure the expected similarity of the sets based on possible worlds' semantics. In the expected contexts, if the expected similarity of a pair of sets (X,Y) is larger than a given threshold value τ ∈(0,1), this pair could be called as similar set pair. In the normal algorithm, the complexity of the expected similarity of uncertain sets based on possible worlds is of exponential order. This paper has provided new algorithms to calculate expected similarity by dynamic programming. The complexity of these algorithms is of polynomial order and they reduce execution time greatly. The final experiments have indicated the usability and the high performance of the new algorithms.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利