基于关键词的RDF数据系统的交互与搜索研究

Presentation on theme: "基于关键词的RDF数据系统的交互与搜索研究"— Presentation transcript:

1 基于关键词的RDF数据系统的交互与搜索研究
刘敏 2018/11/28

2 Outline 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

3 流程 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

4 研究背景 Surface Web Deep Web(BrightPlanet white book) 超链接文本数据 关键词搜索
增长速度更快 月访问量是Surface Web的1.5倍 结构化数据 2018/11/28

5 研究背景 结构化数据的访问 关键词搜索 网络上的结构化数据 结构化查询语言(SQL， SPARQL等) 固定模板的表单
异构性，格式多样，Schema不明确 传统数据库不太适合 流行方案：语义网的RDF数据模型 固定模板表单往往应用于垂直搜索 2018/11/28

6 流程 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

7 基础知识与问题定义 基础知识 SPARQL RDF(Resource Description Framework)
URI、主语-谓语-宾语的三元组(SPO)形式 <The Godfather> <writer> <Mario Puzo> RDF图 RDFS 类似于关系数据库中的schema信息 <#Film> <writer> <#Writer> SPARQL 类似于SQL 描述和表示RDF数据的概念和其之间的关系 2018/11/28

8 基础知识与问题定义 问题定义 数据图G(V, E, L) 关键词映射：一个从q中的关键词到数据图G中的点或者边的映射。 连接查询
V : C-Vertices ∪E-Vertices ∪D-Vertices E: IE-Edges ∪ED-Edges ∪S-Edges(type、subclass) L：E的label的集合 关键词映射：一个从q中的关键词到数据图G中的点或者边的映射。 自然假设：关键词含义单一；关键词有意义 连接查询 (x1,...xk).A1∧…∧Ar的形式 x1,…xk被称为变量(variables) A1…Ar被称为查询原子：P(v1,v2)，其中P是谓词(Predicate)，v1,v2是变量或者常量 描述和表示RDF数据的概念和其之间的关系 2018/11/28

9 流程 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

10 星型查询的探索 定义3.1-1（星型查询）如果产生的连接查询(定义2.2-2) 是一颗树T，树T的高度为2，且树T仅有一个根节点r（即其他节点均为根节点r的孩子节点，同时也是树T的叶子节点，这些节点或是文本节点或是由文本映射得到的实体节点或类节点）时，我们将此连接查询称之为星型查询，根节点我们称之为主题节点，根节点的类型(即type属性值)我们称之为主题类型。 正如1.1背景所述，对于Deep Web中的数据的检索，通用搜索引擎无能为力。对此的一种解决办法就是垂直搜索，所谓垂直搜索引擎即搜索特定的内容类型信息，例如旅游，电影，图片，商户等等的搜索引擎。一般来说，通用搜索引擎不能够发现或者很难发现这些内容，因此垂直搜索与Deep Web紧密联系在了一起。 对于当前的垂直搜索中，有很大一部分的搜索(例如yelp，大众点评等为代表的本地商户搜索)都可以归结为星型查询。所谓星型查询，我们可以将其建模为一棵树(RDF数据我们将其看作一个图G，详见2.2)，树的根节点我们称之为为主题节点，树的高度为2，除了主题节点之外的其他节点均为叶子节点，即均为主题节点的孩子节点。所谓主题节点即阐明用户输入的查询意图的关键节点，例如在本地搜索网站例如大众点评中，用户输入关键词进行查询时，其查询的默认且唯一的主题是商户，而用户输入的关键词是对商户的直接描述。 2018/11/28

11 星型查询的探索 当前的垂直搜索系统实现方式： 设计原则 传统的全文本的检索 直接返回答案，而非查询的检索 表单方式 交互方式不能过于繁琐
交互有效性 当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

12 星型查询的探索 利用探索式搜索的基本思想，提出新的交互： 字面搜索 减少交互负担 “所见即所得”的交互设计原理
字面搜索VS结构化搜索(语义搜索) 当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

13 星型查询的探索 功能模块： 预处理：字面搜索 预处理 关键词映射 打分函数 查询构造 确定主题类型，将主题节点的描述看作文档建立索引
当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

14 星型查询的探索 关键词映射： 类型预测索引和元素定位索引 句法映射 语义映射
字符串匹配技术找形态相似的词：去停用词，词干抽取，子字符串，编辑距离等 语义映射 词典如wordnet找语义上相关的词：同义词，上位词，下位词等 类型预测索引和元素定位索引 类型预测索引：关键词->[term of keywords, type, C-Vertex1,….C-Vertexn] 元素定位索引：[term of keywords, C-Vertexi]-> C-Vertexi的前k个具体值 当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

15 星型查询的探索 打分函数 定义3.1-2（整体映射）对所有关键词分别可能映射到的类别进行组合，形成查询的整体映射。
关键词输入序列{k1, k2,…..,kn}， 每个词项 ki都与一个类别集合{ C-Vertex1,….C-Vertexmi}相关联 基本思想：已知数据图G，构造出产生形式化查询的整体映射TM来自于用户输入的关键词查询KQ的概率的大小-----P(TM|G, KQ) 当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

16 星型查询的探索 当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

17 星型查询的探索 查询构造 排序原则：我们认为一种整体映射得到的形式化查询更有可能反映了用户的意图，如果它的检索结果数量更多。
对于P(TM|G)，即从数据图G中产生TM的概率，我们将其定义为由数据图G中的满足这条整体映射TM的实例的个数与数据图G中属于主题类型的总的实例的个数的比值。 查询构造 通过Schema信息 当前的垂直搜索系统大部分是基于传统信息检索的方式，即将用户输入的关键词与将文档中的词与文档建立的倒排索引通过打分函数(例如TF-IDF)进行匹配，然后按照打分的结果返回关联文档的相应排序，显然这种将结构化数据当文本数据进行处理的方法存在很大缺陷。不仅浪费了结构化数据的元信息；而且文本进行传统信息检索返回的结果的精确度还有很大的提高空间。 传统的全文本搜索，搜索引擎将用户输入的关键词看作词袋(bag of words)，不考虑这些关键词的具体含义及相互关系，仅仅返回那些包含所有用户输入关键词的文档(按照一定的打分函数进行排序)； 通过直接将用户的关键词构造成结构化查询并将结构化查询提交给相应的结构化语言引擎进行处理，返回执行结构化查询的结果，但由于当前自然语言处理的水平、关键词查询天生的歧异性等原因，致使这种方法返回的检索结果也并不令人满意。 2018/11/28

18 星型查询探索 2018/11/28

19 流程 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

20 前k条查询的图探索 原因： 当前的前K条查询的图探索： 图数据越来越多 星型查询过于简单 用户输入关键词查询系统产生的前k条结果或者查询
关键词映射时不存在交互 例如：”river mississippi state” 系统产生的前k条查询中存在含有这种错误映射元素的查询，不仅降低了系统的准确度，还降低了前k条查询的多样性，以及影响用户的体验效果。 2018/11/28

21 前k条查询的图探索 原因： 当前的前K条查询的图探索： 图数据越来越多 星型查询过于简单 用户输入关键词查询系统产生的前k条结果或者查询
关键词映射时不存在交互 例如：”river mississippi state” 系统产生的前k条查询中存在含有这种错误映射元素的查询，不仅降低了系统的准确度，还降低了前k条查询的多样性，以及影响用户的体验效果。 2018/11/28

22 前k条查询的图探索 交互方式 优势： 交互模式简单明了并与当前的传统搜索引擎给出的交互模式相一致 交互次数少，用户负担低
系统产生的前k条查询中存在含有这种错误映射元素的查询，不仅降低了系统的准确度，还降低了前k条查询的多样性，以及影响用户的体验效果。 2018/11/28

23 前k条查询的图探索 功能模块 预处理 关键词映射 打分函数 图探索 前K条子图结构计算 查询映射 2018/11/28

24 前k条查询的图探索 预处理：获得增强Schema图
定义3.1-2（Schema图）一个数据图G(V, E, L)的Schema图GS(VS, ES, LS)是一个图。 定义3.1-2（增强Schema图）已知用户输入的K个关键词对应的M个数据图元素KEm = {kEm1, kEm2,…kEmm} (M的值不大于K)，增强Schema图AGS是一个包含Schema图GS以及以下信息的数据图： e(kEm, c)，对任意的关键词匹配得到的数据图元素kEm，数据图G中包含e(kEm, v)以及type(v, c)，其中v∈E-Vertices。 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 但由于仅仅获有Schema图并不能进行子图结构探索，因为用户输入的关键词进行映射后得到的可能是类元素，或者属性元素或者实体元素，而Schema图中只含有类与属性元素。 2018/11/28

25 前k条查询的图探索 关键词映射 索引：数据图G中的每一个E-Vertices顶点，将其邻接的D-Vertices节点值、E边的标签以及E-Vertices的label值或者title值或name值看作一个文档，进行索引。 提供自动补全功能 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

26 前k条查询的图探索 打分函数 得到的分数表示的是生成的子图的权重而非与用户查询的相关性 当前的研究的打分函数一般考虑”图的结构”以及”图元素与关键词的相似度”，但并未考虑用户输入的关键词之间的相互关系 权重： 结构权重 上下文权重----基本思想：越相关的关键词则其位置彼此更临近 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

27 前k条查询的图探索 打分函数 思想：图中的顶点的关系越密切(即顶点间的权重距离越小)则其越可能符合用户的信息需求 衡量标准：子图的权重越小，则其越可能符合用户的信息需求 得到的分数表示的是生成的子图的权重而非与用户查询的相关性 当前的研究的打分函数一般考虑”图的结构”以及”图元素与关键词的相似度”，但并未考虑用户输入的关键词之间的相互关系 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

28 前k条查询的图探索 打分函数 图的权重 思想：图中的顶点的关系越密切(即顶点间的权重距离越小)则其越可能符合用户的信息需求
衡量标准：子图的权重越小，则其越可能符合用户的信息需求 得到的分数表示的是生成的子图的权重而非与用户查询的相关性 图的权重 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

29 前k条查询的图探索 路径权重 当前的研究的打分函数一般考虑”图的结构”以及”图元素与关键词的相似度”，但并未考虑用户输入的关键词或者映射得到的数据图元素之间的相互关系 权重： 结构权重 上下文权重----基本思想：越相关的关键词则其位置彼此更临近 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

30 前k条查询的图探索 结构权重 默认权重 流行权重：
顶点权重：Schema图中每个顶点(Schema中的每个顶点都是类型顶点)的实例数据的数目与数据图中总的实体数据的数目的比值来衡量 边权重：每条边在数据图中出现的次数与数据图中总的IE-edges的数目的比值来衡量 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

31 前k条查询的图探索 上下文权重 直观思想：使存在于增强Schema图中那些与用户输入直接以及间接相关的数据图元素的权重减小
举例：查找”The Godfather”的Director与”Superman”的Writer合作的电影 关键词输入：” godfather director superman writer film” 关键词元素序列：[”The Godfather I(Film)”，”Director”， ”Superman(Film)”，”Writer”，”Film”] 关键词元素在增强Schema图中的权重减小 关键词元素序列中元素之间的位置关系也表明了用户对构造出的查询的偏好 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

32 前k条查询的图探索 形式化公式：已知关键词元素KEm = {kEm1, kEm2,…kEmm}以及增强Schema图
基于用户输入的观察，如果用户查找”The Godfather”的”Director”，则用户输入”godfather director”的可能性一般比输入”director godfather”的可能性高 实体数据元素与其所属的类的数据元素之间的距离的远近并不太重要 ”director superman film”[“Director”，”Superman(Film)”，”Film”]，则查询更可能是”Superman(Film)”的”Director”拍的Film，这也与我们前面的每个关键词都是有用的假设相一致。 形式化公式：已知关键词元素KEm = {kEm1, kEm2,…kEmm}以及增强Schema图 关键词元素权重 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

33 前k条查询的图探索 间接数据图元素---边元素(点元素类似) 边元素不是type边元素。
边元素不是与用户查询直接相关的数据图元素，边元素没有没有出现在KEm中。 边元素关联的两个顶点emi与emj必须都出现在KEm中，即emi与emj在KEm中必须有相互对应的顶点kEml与kEmt。 如果kEmi是实体顶点，kEmj是类顶点且i<j或者kEmi是类顶点，kEmj是实体顶点且i>j，则β= 0, dist(kEmi, kEmj)=|i-j| 如果kEmi与kEmj同是类顶点，则β= 0且dist(kEmi, kEmj)=0 否则β= γ*[(1+dist(kEmi, kEmj)/m)*C(ke)]，其中γ是一个(0,1)之间的参数, dist(kEmi, kEmj)=|i-j| 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

34 前k条查询的图探索 间接元素为type边时的权重 C(type)=μ*C(ke)
注意每条路径都是独立被计算的，这就表明如果一个元素出现在多条路径之上，那么路径中的这个元素的权重被重复计算多次 通过实验对比，我们将λ设为0.1，γ设为0.5，μ设为0.5效果较优。但由于时间仓促，我们并没有深入研究各个参数之间的关联关系，这也将是未来工作的一部分。 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

35 前k条查询的图探索 图探索 找到最小权重联通子图，使得子图包含所有关键词元素 图探索算法的输入包括： 数据结构
带权重的增强Schema图AGS 关键词元素序列KEm = {kEm1, kEm2,…kEmm} 进行图探索生成前K个子图结构的k值 限制算法在图中探索的最大长度maxDistance 数据结构 cursor(n, kEm, parent, distance, cost)：记录已经访问的路径 PathInfos，其数据结构为(C1,…,Cm)，其中Ci是一个cursor的有序链表，表示从数据图元素kEmi到n的不同的路径：记录图元素n的相关信息以及在探索中发现的到n的不同路径 全局变量LQ。其内包含m个有序列表，分别对应m个关键词元素 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

36 前k条查询的图探索 图探索基本思想： 以关键词元素kEmi (1=<i<=m)开始进行探索。一开始，对于第i关键词元素(1=<i<=m)，创建一个带有空路径记录的cursor，并将cursor置入按照权重非递减的有序列表Qi中(在权重相同时按照插入顺序的先后依次排序) 。在探索过程中，每次都会从LQ中选择权重最小的cursor进行进一步探索。在每一步的cursor探索中，会为当前被访问的数据图元素的邻居元素创建新的cursor。在每进行一次探索后，会调用Topk函数，检测当前被访问的元素是否是一个连接元素(connecting element) 或者当前是否可以安全终止探索。 安全终止条件：LQ为空或者探索距离超过maxDistance或者产生了前k条查询 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

37 前k条查询的图探索 前K个子图结构的计算： 连接元素：一个元素与所有关键词元素都有至少一条路径的元素
候选子图集LG：如果一个元素是连接元素，则其会产生若干候选子图。其被加入全局列表LG中，LG按照权重进行非递减排列。 剩余子图集RG：除去候选子集中的子图，剩余所有的子图(即未包含所有的关键词元素的那些子图)组成的子图集。 核心思想：使得LG中权重最大的子图比RG中权重最小的子图都要小的时候便将LG中的子图分别进行查询映射，转换为各自对应的SPARQL查询。 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

38 前k条查询的图探索 为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

39 流程 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

40 实验评估 有效性评估 性能评估 利用MRR值： 2018/11/28
为了更有效的进行图探索，我们预处理数据图，建立图索引。图索引本质上是对数据图的一个摘要，仅仅包含类型元素，即其是数据图的Schema图。在进行查询处理时，系统通过添加来自于关键词映射中的数据图元素来增强这个图索引。这个增强的Schema图将含有总够的信息来产生用户需要的查询。 2018/11/28

41 流程 研究背景 基础知识与问题定义 星型查询的探索 前k条查询的图探索 实验评估 总结 2018/11/28

42 关键词到语义搜索 谢谢！ 2018/11/28