面向时序知识图谱的多样化Top-k查询算法研究.pdf

面向时序知识图谱的多样化Top-k查询算法研究

摘要

时序知识图谱从理论上来讲是一个会遵循特定时间序列变化的知识图谱。时

序知识图谱对现实世界中的实体、属性和关系等客观事实进行建模，以图的形式

来展现实体、属性和实体之间在特定时间序列的关系，高效处理和查询时序知识

图谱是其广泛应用的关键。然而，在处理和查询时序知识图谱时，我们面临着一

些挑战：首先，由于时序知识图谱的规模庞大且随着时间的推移不断变化，如何

有效地管理和检索这些数据成为一个重要问题；其次，现有的研究方法尚未对时

序知识图谱上的多样化Top-k查询问题进行充分研究：在查询结果中，我们需要兼

顾内容的重要性和多样性，以得到更有意义的结果。

为了解决时序知识图谱的存储问题，本文提出结合快照和日志模式的存储模

型SL-tgStore。模型由若干时间桶组成，每个时间桶由一系列时间窗口组成，首个

时间窗口引入初始快照作为时序知识图谱存储和处理的基本单元，在接下来的时

间窗口存储为增量日志，提出相应的阙值θ来确定初始快照的生成，即生成一个新

的时间桶，以达到初始快照数量与增量日志数量的平衡，并提出临时快照生成算

法；为了对SL-tgStore模型进行高效查询，在此基础上提出4种索引结构Ttg-hash、

Vtg-tree、Ptg-hash和Ltg-tree。有效的解决了快照存储模式消耗内存大，日志存储

模式查询效率低的问题。

针对时序知识图谱上的多样化Top-k查询问题，本文提出一种多样化Top-k查

询算法，能够在时序知识图谱上快速的查询出权重高且冗余低的结果。在

SL-tgStore上提出基于快照模式的单元匹配算法和整体匹配算法，得出时序知识图

谱上的快照匹配结果集；提出基于日志模式的匹配算法，得出时序知识图谱上的

日志匹配结果集；然后提出一种多样化Top-k查询算法，得到了高权重、低冗余的

结果；此外，提出一种高效的剪枝算法，以降低多样化Top-k处理的时间开销。

最后，本文在GDELT、ICEWS、Wikidata、YAGO这四个真实数据集上进行

时序知识图谱存储和查询的实验。理论研究与实验结果表明本文所提出的

SL-tgStore存储模型具有高效性；本文提出的时序知识图谱多样化Top-k查询算法

的有效性和高效性。

关键词时序知识图谱；数据管理；快照模式；日志模式；Top-k查询

-I-

DiversifiedTop-kQueryresearchon

Temporalknowledgegraph

Abstract

Temporalknowledgegraphistheoreticallyaknowledgegraphthatfollows

changesinaspecifictimeseries.Thetemporalknowledgegraphmodelsobjectivefacts

suchasentities,attributes,andrelationshipsintherealworld,andshowsthe

relationshipsbetweenentities,attributes,andentitiesinaspecifictimeseriesinthe

formofgraphs.Efficientprocessingoftemporalknowledgegraphqueriesisthekeyto

itswideapplication.However,wefaceseveralchallengeswhenprocessingand

queryingtemporalknowledgegraph:first,howtoeffectivelymanageandretrievethis

databecomesanimportantissueduetot