基于匹配节点裁剪的图数据库关键词搜索的优化理论与方法

With the rise of the NoSQL movement, and also because more and more valuable graph data become available in the popular applications like social networks, graph database has become one of the most important research trends. Meanwhile, a wide range of industry products related to graph database are being developed rapidly. As a typical technology in the field of information retrieval, keyword search has been one of the major ways of querying graph databases currently. It enables users to retrieve structured information without having to know the complex query languages and database schemas at all. Hence, keyword search on graph databases is a very promising new technology. However, keyword search on graph databases is also known as a very hard problem because of its extremely high computational complexity. Due to the lack of effective solutions, its efficiency and scalability are very poor. This project will study the optimization theory and techniques for keyword search on graph databases. The main research objectives include the follows. Design a heuristic matched vertex pruning strategy which does not depend on the specific search algorithms. By using the pruning strategy, we can reasonably setup constraints of the quality and semantic patterns of search results for reducing the search space. Through statistical analysis of user behavior and data association, identify a set of semantic patterns in which users are interested. Develop an efficient algorithm to match a large number of semantic patterns in the graph at once. By effectively organizing local topological and semantic information in the graph database, construct an index structure that can be used to pruning matched vertices quickly before the search. To support large-scale graph databases, develop the technologies of distributing the index and constructing the index in a parallel way.

随着NoSQL运动的兴起和在社交网络等热门应用中产生了越来越多有价值的图数据，图数据库开始成为重要研究趋势并正被迅速地产业化。将信息检索领域的关键词搜索用于图数据库的查询，能让用户不必掌握复杂的查询语言和数据库模式就能查找结构化信息，成为了一种应用前景非常光明的新技术。然而，图数据库关键词搜索的计算复杂度极高，其效率和可伸缩性问题一直缺乏有效的解决途径。本项目将研究图数据库关键词搜索的优化理论与技术，主要研究内容包括：设计一种启发式的不依赖于具体搜索算法的匹配节点裁剪策略，可合理约束搜索结果的质量和语义模式以缩减搜索空间；通过对用户行为和数据自身关联的统计分析，发现用户感兴趣的语义模式集，并设计可同时与大量语义模式进行高效匹配的算法；有效组织与利用图数据库中的局部拓扑与语义信息，构造一个可实现在搜索前快速裁剪匹配节点的索引结构，并研发索引的分布并行处理技术以更好地支持大规模图数据库。

本项目自2012年获得国家自然科学基金委批准立项之后，项目组全体成员围绕项目研究目标兢兢业业开展科研工作，逐步完成了所计划的研究内容，并且获得了比较理想的实验结果，基本上实现了立项时的研究目标。.在过去三年内，图数据库的发展十分迅猛，逐渐成为了一种重要的数据库类型，在很多行业和领域得到了广泛应用，这和我们立项时的预期是相符的。在此背景下，本项目在图数据库的关键词搜索方面所做的研究，确实具有很强的现实意义和应用价值。严格按照本项目的研究目标，我们研究了一种图数据库关键词搜索的优化理论与方法，在设定的搜索结果的质量和语义约束条件下，通过有效组织与利用图数据库中局部拓扑与语义信息构建索引，实现在搜索前快速、准确、可靠地裁剪匹配节点，提高图数据库关键词搜索的效率与可伸缩性。首先，在研究过程中，我们借鉴信息检索领域的相关研究成果，创新性地在图数据库搜索领域提出了用户搜索意图分类，即分为已知项搜索和探索性搜索，并且分别探讨了两种搜索意图的优化理论。其中，已知项搜索据统计在搜索历史中占大部分比例，其特点非常符合使用本项目所提出的基于匹配节点裁剪的优化方法，因此成为了我们的重点研究对象。然后，我们按计划开展了三个方面的研究。第一，我们研究了一种启发式的匹配节点裁剪策略，以可能存在的错误裁剪为代价，尽力而为地缩减搜索空间。我们提出了以答案树的高度作为其质量衡量指标，从而设计方法利用图中的局部拓扑信息来预测从一个匹配节点出发的搜索路径能否为生成高质量的答案树做出贡献。第二，我们研究了一种用户兴趣驱动的语义模式获取方法，通过对用户行为的统计分析方法，从查询、点击、评价等历史数据中发现用户感兴趣的语义模式。第三，我们重点研究了一种专门的MVP（Matched Vertex Pruning）索引技术，使得在接收到具体的查询时，能够快速地进行在线的匹配节点裁剪，从而保证裁剪过程的耗时远小于为搜索过程节约的时间。此外，我们在Hadoop平台设计和实现了分布式MVP 索引，并采用MapReduce 框架来开发并行的索引生成程序。.在本项目的研究基础上，我们发表了十余篇相关论文，其中包括3篇CCF B类论文，5篇C类论文，1篇A类短文和1篇国内权威期刊论文，申请国家发明专利1项，培养了多名研究生，形成了一个比较优秀的研究梯队，超额完成了项目的预期成果。