基于r-clique的不确定RDF关键字查询研究

发布时间：2018-07-31 06:59

【摘要】：资源描述框架(Resource Description Framework,简称RDF)是语义Web网所使用的基本标记语言,在诸多领域中有广泛应用。由于现有的本体抽取、标注方法和测量技术存在误差和噪声,使得不确定RDF数据普遍存在。近年来,对于不确定RDF数据的查询研究逐渐成为热点。由于不确定RDF数据可以建模为不确定RDF图,那么对于不确定RDF数据的关键字查询的研究实际上就是对于不确定图上关键字查询的研究。本文在已有研究的基础上,提出了两种基于r-clique的不确定RDF关键字查询的算法-——SABR和HABR。单词”clique"的中文释义是“极大团、子群体”,这里指不确定图中的子图,字母r是一个表示距离阈值的变量。所以,r-clique是指包含所有查询关键字的任意两个节点的距离不大于给定值r的子图。为了提高查询速度,本文提出了一种多项式时延的近似算法来构建r-clique。算法KSABR (Keyword Search Algorithm Based on r-clique)将不确定RDF数据上的关键字查询问题映射为寻找不确定图上的r-cliques的问题。为了提高查询结果的质量,在KSABR的基础上又进一步提出了精度更高的算法：HABR (Efficient Algorithm Based on r-clique)。 HABR中采用了打分函数对结果进行排序。对于得到的k个结果,HABR算法调用打分函数对结果进行排序,然后将top-k个结果返回给用户。为了进一步提高查询的速度,本文设计了两种索引结构——KI (Keyword Inverted Index)和PI (Probabilistic Inverted Index)。KI中存放的是关键字和节点之间的映射关系,它可以用来实现结构剪枝和概率剪枝。PI中存放的是关键字节点和r-clique之间的映射关系,它可以用来实现打分函数。实验证明,本论文提出的算法KSABR在时间性能上具有较好的性能,而算法HABR在时间性能和结果质量上都具有较好的性能。
[Abstract]:Resource description Framework (Resource Description Framework,) is a basic markup language used in semantic Web nets, which is widely used in many fields. Due to the existing ontology extraction, labeling methods and measurement techniques, there are errors and noises, which make uncertain RDF data widely exist. In recent years, query for uncertain RDF data has become a hot topic. Because uncertain RDF data can be modeled as an uncertain RDF graph, the research on keyword query of uncertain RDF data is actually a study of keyword query on an uncertain RDF graph. Based on the previous research, this paper proposes two algorithms of uncertain RDF keyword query based on r-clique-SABR and Habr. The Chinese meaning of the word "clique" is "maximum mass, subgroup", which refers to a subgraph in an uncertain graph. The letter r is a variable representing the threshold of distance. Therefore, r-clique is a subgraph of any two nodes containing all query keys whose distance is not greater than a given value r. In order to improve the query speed, an approximate algorithm of polynomial delay is proposed to construct r-clique. The algorithm KSABR (Keyword Search Algorithm Based on r-clique maps the keyword query problem on uncertain RDF data to the problem of finding r-cliques on uncertain graphs. In order to improve the quality of query results, a more accurate algorithm called: Habr (Efficient Algorithm Based on r-clique is proposed on the basis of KSABR. In HABR, a scoring function is used to sort the results. For the obtained k results top-k algorithm calls the scoring function to sort the results and then returns the top-k results to the user. In order to further improve the query speed, this paper designs two index structures, Ki (Keyword Inverted Index) and PI (Probabilistic Inverted Index). Ki, which store the mapping relationship between keywords and nodes. It can be used to implement structural pruning and probabilistic pruning. Pi can store the mapping relationship between key nodes and r-clique, and it can be used to implement scoring functions. Experiments show that the proposed algorithm KSABR has better performance in time performance and HABR has better performance in both time performance and result quality.
【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP393.09

【相似文献】