Keyword Query over Error-Tolerant Knowledge Bases

来源 :计算机科学技术学报(英文版) | 被引量 : 0次 | 上传用户:jxzsy
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
With more and more knowledge provided by WWW, querying and mining the knowledge bases have attracted much research attention. Among all the queries over knowledge bases, which are usually modelled as graphs, a keyword query is the most widely used one. Although the problem of keyword query over graphs has been deeply studied for years, knowledge bases, as special error-tolerant graphs, lead to the results of the traditional defined keyword queries out of users’ satisfaction. Thus, in this paper, we define a new keyword query, called confident r-clique, specific for knowledge bases based on the r-clique definition for keyword query on general graphs, which has been proved to be the best one. However, as we prove in the paper, finding the confident r-cliques is #P-hard. We propose a filtering-and-verification framework to improve the search e?ciency. In the filtering phase, we develop the tightest upper bound of the confident r-clique, and design an index together with its search algorithm, which suits the large scale of knowledge bases well. In the verification phase, we develop an e?cient sampling method to verify the final answers from the candidates remaining in the filtering phase. Extensive experiments demonstrate that the results derived from our new definition satisfy the users’ requirement better compared with the traditional r-clique definition, and our algorithms are e?cient.
其他文献
所谓近海浮绳式网箱养鱼,就是在港湾外的近海较深水域设置浮绳式的网箱,选择优质的鱼类,进行高密度、集约化的养殖。它是在内湾传统式网箱养鱼的基础上发展起来的一种优质、高产
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊
短暂性脑缺血发作(TIA)呈局部性、短暂性、反复性。近期我们在对颈动脉狭窄与TIA的研究过程中,发现两者之间有一定相关性。现报告如下。1资料与方法1.1临床资料:2006—2008年
大菱鲆为栖息于大西洋东北部沿岸的特有的海水鱼类。其最佳养殖水温10-20℃,耐受极端温度0-30℃,1龄鱼的生活水温为3-26℃,2龄以上对高温的适应性略有下降。大菱鲆是欧洲著名的海水养殖良种,受到
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊
目的:本文旨在探讨PTC对梗阻性黄疸的诊断价值。方法:本组共114例梗阻性黄疸,均经手术病理证实,术前均行PTC检查及B超检查,其中56例做了CT检查。结果:114例梗阻性黄疸的PTC检查,诊断
2018年7月6日bauma CONEXPOINDIA 2018展会主办方在北京召开了新闻发布会,发布会由AEM亚太区销售总监李凯恩先生主持,慕尼黑展览印度公司商务总监Tushar Alekar先生介绍了bau
期刊
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
期刊
患者 ,女 ,5 1岁。原有胆囊炎、胆石症 ,近一周上腹部闷胀不适而入院。腹部体检胆区有轻压痛 ,无其他体征。B超检查 :右肾上极内后方探及一境界清楚 ,有包膜 ,约 4cm× 2 .7cm低回