在知识检索图

文摘

随着因特网的迅速发展和大数据,地方检索已成为日常生活不可或缺的一部分。然而,传统的检索技术并不能满足用户的语义需求。知识图引入了新一代检索系统来提高检索性能。知识图抽象事物实体和实体之间建立关系,用三元组的形式表示。然而,随着知识的扩张图和数据量的快速增长,传统的检索知识图的方法性能较低的地方。本文设计一个检索方法以提高地方检索的效率。首先,执行数据预处理和问题模型建立在离线阶段。同时,构建语义距离指数、空间四叉树索引,并根据语义空间语义的混合索引和空间信息。同时,在网上检索阶段,本文设计一个高效的查询算法和基于该指数的排名模型信息构建在离线阶段,针对提高检索系统的总体性能。最后,我们用实验来验证其有效性和可行性的检索方法基于知识图的检索准确性和检索效率下的真实数据。

1。介绍

近年来,检索相关地理信息吸引了越来越多的关注,从学术领域由于其在社会生活不可或缺的应用。目前,地方旅游查询中检索无处不在,周边生活和其他方面。根据相关的调查和统计,超过28%的结果是相关的地理信息,如邮政核心地址,互联网IP地址、城市和省份,当用户在互联网搜索引擎上输入相关查询。

传统的关键字检索方法不能达到精度和效率高,因为他们不能捕获用户的语义要求。因此,新一代的大数据检索是基于知识图(1]。与传统的检索方法、知识图的目的是描述和抽象实体和概念,存在于现实世界和表达实体和概念之间的关系。它可以更好地反映用户的语义和要求通过关联关系和提高检索的精度和一致性。与此同时,前面的图搜索算法(2,3)将更多的注意力放在图结构而不是语义内容,这是不足以明显提高搜索的精度和效率。

近年来,关键字查询基于RDF数据发展迅速。RDF是一种特殊类型的图表数据。基于RDF数据查询SPARQL等结构化查询语言(4]。总的来说,大致有两个类别的检索基于知识图:一个是研究优化基于SPARQL的结构化查询语言。目前,SPARQL查询的研究主要集中在关系代数和Top-K加入查询算法(5,6]。虽然查询结果可以通过上述研究更准确的查询优化的SPARQL Top-K,不适合直接应用在大规模RDF数据集。此外,用户需要了解查询语义和RDF存储模式;用户的位置和其他信息不考虑。另一个是基于RDF图的查询方法。这种方法允许捕捉更多的信息从RDF图结构,如子图7- - - - - -10],邻居[11),路径(5),和距离(12]。这些方法可以表达的语义需求用户快速检索结果。然而,他们为大规模数据查询固有的低效率。

目前,知识的地方检索图仍在初步阶段,有许多研究困难:(1)检索的地方需要更好的理解用户的实际检索语义和需要从知识图中提取信息。(2)大量的空间信息数据将被忽略,导致查询结果不能更好地理解用户的检索需求的地理位置。检索结果需要结合地理位置,时间和其他信息进行个性化推荐。(3)现有方法缺乏能力大规模图数据进行高效查询其庞大的存储和计算成本。同时,之前的研究没有明确计算的成本排名检索结果,影响检索结果的准确性。

考虑上述研究现状的不足,有必要设计一个检索方法来克服这些限制。提出公司KPR系统,一个有效的系统图的知识检索,提高检索的速度和准确度。具体地说,我们在不同的数据集进行实验,实证结果表明,我们的方法明显优于传统的检索。

值得强调以下本文的贡献:(1)在离线阶段,我们引入一个空间语义的混合索引保存位置特征和语义特征。此外,共同优化施工过程的空间索引和语义距离指数、混合指数不仅满足要求的位置和语义也缩短查询的执行时间。(2)在线阶段,我们提出一个基于数量排名模型分类和在线查询算法来提高公司KPR系统的准确性和效率。结果表明,我们提出的方法克服了大数据检索的效率低。

本文组织如下。部分2提出了预处理和索引构建方法。部分3介绍了查询算法和排序模型。节4、索引构建和在线查询算法进行测试以验证其有效性。部分5总结和前景的研究工作。

2。预处理和索引构建

本文建立模型通过预处理部分的问题。与此同时,本文构造的语义距离指数和空间索引空间和语义信息的基础上,本文分别优化,减少存储的成本。最后,本文将建立一个混合索引结构。

2.1。相关定义

定义1。(过度增殖查询)。用户查询语义Top-K基于空间RDF数据集。地理位置的用户输入问当前的查询,位置查询的类型,需要返回的结果数k集,以及一系列关键字描述t。这将返回Top-K位置最佳匹配用户的查询需求。这些位置考虑语义距离和空间距离的成本函数完成评价排名。满足以下两个条件:(1)这个位置是一个实体在RDF图的地方。(2)节点的顶点为根的子树的实体包含所有用户输入的关键字。图1显示了一个示例查询的过度增殖。

定义2。(语义距离 )。定量计算语义距离是用来表达的语义相关性的大小。语义距离越小,语义相关性就越大。这意味着更大的相关性目前查询用户位置查询语义需求。假设用户输入的查询关键字 ,给定一个地方实体满足查询 , 从实体是最短的距离吗p的关键字在RDF图G。然后,语义距离是最短的距离的总和所有的关键词:

定义3。(空间距离 )。空间距离代表之间的欧几里得距离空间地理位置的用户查询的位置问和这个地方实体p。这个方程是 。 用户查询位置的空间地理坐标吗问。 这个地方实体的空间地理坐标吗 。

2.2。问题模型

假设用户在波士顿,用户将查询“大学培养诺贝尔和图灵奖。“在图1,两个子树包含关键字“诺贝尔奖”和“图灵奖”,和根节点“哈佛大学”和“麻省理工学院”。过度增殖查询的目的是找一套地方实体满足用户查询关键词。

考虑到语义和空间信息因素,过度增殖查询的目标模型构建:

在方程(2),地方实体 地方类型C,问用户查询位置,用户查询关键词设置,f是合成的排序功能语义和空间信息。

因为实体描述包含大量的关键字信息,有很多重复,本文构造一个反向索引关键字关键在预处理阶段和实体之间的语义距离的计算转换为计算节点。根据语义距离的定义,以满足所有的查询关键词,有必要计算最短的距离之和的最小值查询当前的实体p所有的物理节点在每组V:

图2问题是模型,假设用户输入查询关键字为{主题、奉献、罗马}。找到相对应的组节点根据反向索引关键字和找到节点到{{v1, v4}, {v2}, {v1、v2, v5}},节点集的排列和组合后,需要搜索的节点集获得{v1、v2}, {v1、v2, v5}, {v4 v2}, {v4 v2, v5}, {v4, v2, v1}。获得的语义距离是根据节点之间最短的距离。

2.3。语义距离指数

根据问题的模型建立在前一节中,为了快速获得语义距离计算物理节点之间最短的距离,这部分构造一个高效的索引结构语义距离。

定义4。(象征 )。D是最短的距离从一个实体到另一个组中的实体RDF图。存储一对顶点 ,u任何实体节点和吗代表从实体节点最短的距离u实体节点 。
对于每个实体节点 ,从查询节点年代到节点t是最短的距离 ; 是 首先,所有当前地方实体身份号码。其次,对于每一个节点 ,初始化标志是空的。最后,对d层执行广度优先搜索的地方实体的ID。添加节点的距离广度优先搜索时离开从节点1执行k时间。它可以显示为 。假设之间的距离u和遍历 。如果 ,然后切u不再把( )在马克 。此外,不再试图把所有的边缘u。索引信息的形式存储在<地方实体ID、节点ID,最短的距离>。图3描述了语义距离指数建设的过程。

2.4。空间索引

空间位置是另一个重要的因素影响检索结果的地方。因此,本节将重点介绍如何构建一个有效的索引基于空间位置信息和快速查询实体。

定义5。(区域矩形坐标(RRC))。区域的矩形坐标(RRC)空间区域信息的表示和存储信息。假设一个空间米地区,代表的空间区域协调RRC我_th地区。左上角的坐标和右下角的坐标表示为 根据RRC的地区和空间坐标( )的位置问,它可以确定位置是否在该地区 :

定义6。(线性四叉树)。一个线性四叉树符合下列条件:(1)Nonleaf节点有四子树。(2)中间节点也是一个线性四叉树。(3)保存非空的四叉树的叶节点一维辅助对象空间基于磁盘和每一个节点可以通过空间填充编码技术。(4)在确保所有节点在一个地区分为四个矩形亚区,试图确保每个分区中节点的数目是偶数。
四叉树的生成算法是一个自上而下的迭代过程。(1)首先,计算RRC的RDF图包含所有的地方实体节点我线性四叉树的根节点,同时整个数据空间。(2)数据空间我分为4部分垂直或平行的x设在方向或y设在方向根据节点的分布。每个部分包含一个几乎相同数量的地方实体节点。(3)计算RRC分开的四个分区,建立链接到父节点。此外,执行迭代执行,直到每个区域的物理节点数量达到阈值米。(4)为四叉树做split-sequence-based编码区域划分。分割空间的顺序如下:SW(西南),SE(东南)、西北(西北)、NE(东北)。这些空间代表二进制00,01年10和11分别编码,可以为每个subpartition分割序列获得的链接。节点路径和特定区域在一个线性四叉树编码是全局唯一,便于线性存储的数据。(5)映射区域编码的RRC相应区域<地区编码,RRC >,这可以让它容易迅速找到一个位置。它可以快速确定在一定的线性四叉树的节点区域的地理位置。

2.5。空间语义的混合索引

定义7。(区域语义距离(RSD)指数)。仍然有大量的实体在该地区的地方年代在空间分割。关于语义距离指数每个地方的实体,实体可以按顺序存储根据实体的ID。
根据过度增殖的定义查询,每个地方的实体的语义距离需要计算,和越接近用户的位置,满足用户的需求。因此,有必要结合空间索引信息与语义距离索引信息,形成基于空间的混合索引结构和语义。这个结构是区域语义索引。语义距离索引信息存储在空间四叉树索引的叶节点,每个叶节点代表相应的空间区域和存储马克D (v)的实体在该地区的地方。此外,D (v)是最短的距离信息的实体与其他实体节点在该地区。图4显示区域的结构语义距离(RSD)指数,和表1显示了RSD的存储信息。

3所示。查询算法和排序模型

3.1。排名模型

位置的一组用户查询的结果,一个排名函数模型需要建立。此外,结合语义距离和空间距离信息来对结果进行排序,并选择Top-K结果返回给用户。

传统的线性排序模型有大量缺陷。首先,它是影响因素不敏感。其次,它可以影响重量参数。第三,很容易导致极端值,从而导致不准确的查询结果。本文生成天际线的指数排名模型。图5显示了轮廓坐标。

Exponent-based天际线层次排序算法(数量),检索结果集的地方是映射到地平线二维坐标系统,水平和垂直轴代表空间距离指数和语义距离指数,分别。数据在二维坐标系中计算得到不同的轮廓水平,数据相同的轮廓水平排名优先。轮廓水平越低,排名优先级越高。例如,数据在CL (k - 1)是更先进的比CL (k)中的数据。关于在同一等高线数据级别,合规距离F (p)将由方程(计算7)。较小的F(p),排名是更高级的,这表明当前地方实体更符合用户的实际需要:

3.2。查询算法

本节提供了一个有效的联机检索查询算法;具体步骤如下:(1)找到一组节点对应关键字设置根据用户设置输入关键字描述。(2)根据用户的查询位置信息,每层节点的RRC是在线性四叉树索引的搜索与空间坐标的地方,和最小区域位置所属的位置。(3)阅读RSD在这方面的信息。标记信息的查询需求节点的设置根据用户输入的关键字,并计算语义距离。然后,用户查询的空间坐标位置和地方实体查询得到的距离计算公式获得的空间距离。集成空间和语义信息的Top-K结果集计算根据成本函数模型。结果集是由最小堆的方法维护和更新的比较kth直到最后查询的结果。在线查询算法算法所示1。

关于网上查询的结果集,假设Top-K结果保持在当前的最小堆。为kth坏的结果,如果下一个查询的结果是更昂贵的,没有需要更新的最小堆。因此,基于语义距离和空间距离的边界可以根据成本函数模型和计算kth当前最小堆的结果。用它来修剪后续查询。动态调整相应的边界最小堆时每次更新。假设θ当前的成本吗k结果,最大的语义距离的实体 。这意味着,无论多小的空间距离,最终成本将不低于θ当随后将实体语义距离大于极限。因此,地方实体被移除和随后的计算并不持续。同样,空间距离的最大限度 。图6显示了一个示例的修剪优化查询。

4所示。实验设计

为了验证本文索引结构,在线查询算法本文排名和改善检索性能的模型,本文将从三个方面:测试系统性能指标性能,查询算法和查询的准确性。

系统模块图如图7。

4.1。实验环境和数据集

硬件环境如下:本文实验机是一个双通道英特尔酷睿i7 - 4790 CPU, 64 GB的DDR3 1600、300 GB机械硬盘。

软件环境如下:Ubuntu14操作系统;JDK版本1.8.0_101;IntelliJ Idea开发环境。

数据集如下:YAGO DBpedia。

数据集表中列出的信息2。

4.2。参数确认

在实验之前,需要确认以下参数:(1)的价值d:当构建语义距离指数之间最短的距离的地方实体与其他实体节点需要。这促进了在线计算语义距离。存储实体之间最短的距离广度优先搜索的标签。然而,考虑到存储空间和索引效率,层数d广度优先搜索需要实验确定。图8是一个实验参数的影响d语义距离指数下的存储大小YAGO数据集。可以看出,语义距离存储大小从100米到800米不等。此外,增加的价值大小d变得更大。当d= 5,该指数大小急剧增加。因此,在本文中,参数d= 4设置,只有interentity信息与存储的4是最短的距离。(2)的价值米:构建空间线性四叉树索引时,阈值的区域数据米会影响线性四叉树的深度,从而影响查询效率。因此,米需要通过实验获得的。图9是一个实验参数的影响米空间索引的查询时间下YAGO数据集。米是位置的总数的百分比。从这个实验可以看出,空间索引作为参数存储大小会显著上升米减少。这是因为较小的阈值米,就越需要划分区域。线性四叉树的深度越大,时间越长,查询时间。当米= 1/1000,查询已急剧增加。因此,本文设置参数米= 1/500。(3)的值排名的模型:代表是多么敏感排名模型变量。在这个实验中,β等于1.5。

4.3。构建索引性能实验

参数确认后,语义距离指数和空间线性四叉树索引需要建立,和随机生成1000查询样本。采用相同的过度增殖查询算法和比较的平均查询时间索引和nonindexing在同样的查询,然后验证的有效性检索系统的索引来提高查询效率。数据10和11显示YAGO下的实验结果数据集和DBpedia数据集,分别。

从实验结果可以看出,查询时间大大增加的数据量的增加。然而,索引信息建立后,在相同的查询输入和查询算法,包括索引信息的平均查询时间比平均查询时间短没有指数,和只有3/5∼4/5的查询时间不包括索引信息。随着数据量的增加,索引信息提高了查询效率更明显。

关于语义距离凿指数施工方法,该方法显著减少了索引存储成本的传统方法相比,直接存储语义距离最短的距离。建立传统最短的距离指数和剪切指数对不同大小的数据YAGO数据集,分别。索引的存储大小进行比较。实验结果如图所示12。

从实验结果可以看到,该指数的总量数据存储大小的增加而增加。此外,存储语义距离信息的剪裁的方法是比传统的方式更节省空间的直接存储最短的距离。随着整体的数据量的增加,裁剪效果更加明显,存储大小大约是5/7∼6/7的常规方法。验证,本文的剪裁方法有效地减少了冗余的信息。

4.4。查询算法实验

在构建索引在离线阶段,关于在线查询算法,动态查询修剪方法提出了能有效去除不必要的地方问,从而缩短查询时间。以下实验验证的效率动态查询修剪算法本文通过比较不同的查询算法。首先,随机生成1000查询输入基于相同的索引信息。其次,使用传统的过度增殖修剪算法和动态查询算法比较平均查询时间。数据13和14显示YAGO下的对比实验的结果数据集和DBpedia数据集,分别。

从实验结果可以看出,动态查询修剪算法比传统的过度增殖更高效的算法。此外,随着数据量的增加,动态修剪查询算法的优化效果越来越好。

4.5。检索性能实验

根据指数和在线查询算法提出了一个完整的检索系统公司KPR就形成了。与传统KSP-based检索系统实验比较,生成1000个随机查询下YAGO数据集,然后比较不同的检索系统的平均查询时间,这个实验将验证的有效性本文检索系统在传统的检索系统的速度。图15显示了检索系统的比较结果。

根据这个实验,公司KPR检索系统提出了与传统相比大大提高了检索效率KSP-based检索系统。然而,这也牺牲一个指数的一部分。相应的参数由实验成本指数和检索系统之间实现平衡效率改进和存储成本保证提高检索系统的性能,降低存储成本。

关于不同的排序模型,首先,随机生成1000相同的查询和结果查询结果集的Top-K。其次,计算结果获得的平均精度。第三,进行比较分析,在不同的排序模型的精确性。图16图表显示了精度比较传统的线性排序模型和指数排名模型下YAGO数据集。

从实验结果可以看出,传统的线性排序函数不如指数排名模型检索的准确性。此外,随着kTop-K价值较大,指数排名模型的准确性越来越高。然而,线性排序模型的准确性是少改进。两个排名模型的精度之间的差距变得越来越大。这是因为线性顺序模型更依赖于体重值参数。此外,很容易生成一组极端由于敏感性差下的坏的结果变量。因此,检索精度不高。

4.6。实验总结

本节实验验证本文所提出的索引结构不仅提高检索性能,同时,与传统的直接指标施工方法相比,该指数施工方法提出了低成本的存储空间,可用于实际的生产环境。通过对比查询算法和传统的过度增殖算法,验证了本文算法的效率。通过查询精度的实验,验证了选择的Top-K结果排名模型本文更准确比传统Top-K结果基于线性模式。上述所有实验验证该方法的有效性和可行性提出了改善检索性能的知识图的地方。

5。结论

本文从现有知识图的问题检索技术的缺点在准确性和效率低在大量数据,综合考虑语义和空间信息因素,在离线阶段,建立索引信息和高效的查询算法和居在线模型设计阶段提高精度和效率的检索系统。

未来的研究方向主要是分布式和并行的知识图检索。目前,知识图的检索技术仍然是基于单机的内存和磁盘,存储空间的限制和并行效率。由于存在大量的实体联系图的知识,对知识的分布和并行化图,图的分区存储和分布式检索算法都是在未来的研究热点和难点。如果可以实现,知识图像检索系统的性能将进一步改善。

数据可用性

YAGO数据用于支持本研究的发现已被存入https://www.mpi-inf.mpg.de/departments/databases-and-information-systems/research/yago-naga/yago/downloads/。DBpedia数据用于支持本研究的发现已被存入https://wiki.dbpedia.org/。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是支持的智能实时调度技术的研究和应用基于人工智能的电网(52460817 a029)。

引用

1. j . Pujara h .苗族l . Getoor et al .,“知识图识别,”国际语义Web会议斯普林格出版社,柏林,德国,2013年。视图:谷歌学术搜索
2. 黄x丽安,l·陈,z”关键词搜索概率RDF图。”IEEE工程知识和数据,27卷,不。5,1246 - 1260年,2015页。视图:出版商的网站|谷歌学术搜索
3. j . z . Wang, j .冯et al。图和文字共同嵌入知识计算语言学协会斯特劳斯堡,宾夕法尼亚州,美国,2014年。
4. m·a·Bornea j .杜比a Kementsietsidis et al .,“建立一个有效的RDF存储在关系数据库中,”《2013国际会议管理data-SIGMOD的13,页121 - 132,纽约,纽约,美国,2013年。视图:出版商的网站|谷歌学术搜索
5. m .竞技场,b .昆卡格劳,e . KharlamovŠ。Marciuška, d . Zheleznyakov“面向方面的搜索图基于rdf的知识,”网络杂志的语义卷,37-38 55 - 74、2016页。视图:出版商的网站|谷歌学术搜索
6. c . Nikolaou和m . Koubarakis”在RDF和SPARQL查询信息不完整人工智能卷,237年,第171 - 138页,2016年。视图:出版商的网站|谷歌学术搜索
7. e .马克思,k . Hoffner s Shekarpour et al .,探索网络对RDF语义搜索知识图表施普林格国际出版,柏林,德国,2016年。
8. f . Li w·勒美国段et al .,“可伸缩的关键词搜索大型RDF数据。”IEEE知识&数据工程,26卷,不。11日,第2788 - 2774页,2014年。视图:出版商的网站|谷歌学术搜索
9. j . h, h . Wang杨et al .,“眨眼:关键词搜索排名图表,”学报2007年ACM SIGMOD data-SIGMOD 07年的国际会议管理,页305 - 316,纽约,纽约,美国,2007年。视图:出版商的网站|谷歌学术搜索
10. c . Choksuchat c . Chantrapornchai m . Haidl et al。加速关键字搜索大RDF Web数据很多核心系统施普林格,柏林,德国,2015年。
11. h . Arnaout和s . Elbassuoni有效的RDF图知识搜索、社会科学电子出版,纽约,纽约,美国,2017年。
12. j·史、d .吴和n . Mamoulis”最高k相关的语义检索空间RDF数据,”《2016国际会议管理Data-SIGMOD的16,页1977 - 1990,纽约,纽约,美国,2016年。视图:出版商的网站|谷歌学术搜索

版权

版权©2020鑫山et al。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。