论文部分内容阅读
语义万维网通过赋予信息明确的结构和语义,使得机器不仅可以显示这些信息,更能够理解、处理和整合它们。近年来,随着链接开放数据和DBpedia等项目的全面展开,语义Web数据源的数量激增,大量以RDF为数据模型的图结构语义数据被发布。互联网正从仅包含网页和网页之间超链接的文档万维网转变成包含大量描述各种实体和实体之间丰富关系的数据万维网。在这种背景下,以谷歌为代表的各大搜索引擎公司纷纷以此为基础构建知识图谱来改善搜索质量,从而拉开了语义搜索的序幕。与传统的文档检索不同,语义搜索需要处理粒度更细的结构化语义数据,因此也面临着更大的前所未有的挑战。原有成熟的针对非结构化的Web文档的存储与索引技术对RDF数据不再适用。现有的排序算法也不能直接应用到面向实体和关联的语义搜索中。SPARQL查询支持和面向异构语义数据源的数据整合是全新的问题。此外,支持用户熟悉的关键词查询对于语义搜索推广的至关重要。本文旨在全面系统地解决了面向大规模RDF数据的语义搜索所面临的挑战:支持大规模图数据存储与索引,支持包含关键词的图结构查询,支持以实体为中心的结构化排序,支持面向多数据源的异构数据融合,和支持友好的用户交互等。论文各章的主要内容和贡献如下列出:第一章为绪论,介绍了研究背景,总结了语义搜索的国内外研究现状并详细描述了面向大规模RDF的语义搜索所面临的主要挑战。第二章首次使用信息检索的方法来搜索数据万维网。通过利用和扩展倒排索引来支持高效的单变量树型混合式查询处理。在此基础上,我提出了一种基于关系的排序算法来返回相关的实体,使用分面浏览来允许用户交互性地构造混合式查询,以及基于块的索引来支持增量式索引更新。第三章扩展了第二章的结构化查询能力,提出了一个高效的RDF查询引擎来执行更一般的SPARQL查询。此外,我通过收集特定的RDF统计信息来估计查询计划的执行代价,并设计了一个全新的查询优化算法来确定最优的联结顺序,将SPARQL查询图转换为最优的查询计划。第四章讨论了基于RDF图模式的高效查询处理。本章介绍了两种模式选择策略,一种通过启发式规则来选择RDF频繁子图,另一种使用查询历史来选择用户偏好的子图结构。在前两章的基础上,我进一步提出基于图模式的高效索引,通过模式树来表示查询计划,并将SPARQL查询转换为子模式覆盖问题来解决。第五章提出了一个二阶段整合的解决方案来解决面向大规模RDF图数据的语义搜索中的实体匹配问题。通过分块来快速筛选候选实体对以解决可扩展性方面的问题。接着,利用实体的局部结构特性在每个分块内部进行聚类,取得最终的匹配结果。本项工作也是首次尝试通过利用开放链接数据中现有的sameAs三元组在大规模场景下进行广泛的实体匹配效果评估。第六章研究了一种新颖且友好的关键词搜索交互方式,即在大规模图数据(特别是RDF数据)上如何进行高效的关键词查询翻译。我提出了一个新颖的前k子图搜索算法,将关键词查询转化为结构化查询,而不是直接计算查询结果。我还利用摘要技术来生成只包含图模式信息的聚合图,来加速查询翻译过程。第七章介绍了一个支持按需支付数据整合的数据万维网搜索基础架构。本章将查询翻译扩展到在异构的万维网数据源上,即将用户关键词翻译为一个跨越多个数据源的语义结构化查询。此外,我详细介绍了数据万维网上进行分布式查询处理的技术,特别是映射联结。它利用第五章提到的大规模实体匹配方法来预先计算数据层映射,并对从异构数据源中获得的结果进行高效合并。第八章将语义搜索应用场景扩展到同时包含图结构数据、网页以及相应语义标注的混合网络环境中。通过整合信息检索和数据库技术来构建一个可以扩展到大量文档、图结构数据和语义标注的数据库。此外,我提出了一个新颖的数据结构来表示混合搜索返回的(中间)结果,并设计了一系列针对混合查询处理的高效算法。第九章总结了本文主要工作和成果并对语义搜索的进一步研究做了展望。