基于图的大规模异质信息网络的匹配查询关键技术研究

Recently, graph data models have attracted increasing interests in both research and industrial community. In this proposal, we study the graph pattern match query over heterogeneous networks. Distinct from labelled-graphs, the heterogeneous networks are semtaic-rich data. The existing graph pattern match query algorithms are designed for the labelled-graph data. Thus, they are not suitable to work on heterogeneous networks. Therefore, we foucs on the pattern match query over heterogeneous networks from the two perspectives, i.e., query performance and query semantics. In order to improve the query perforamnce, we study the index strategy in the heterogeneous networks, the structured views and the distributed graph pattern query processing. To enable users to experess their query intent more naturally, we propose to study the natural language interface to query the hetegeneous network. Specifically, given a natural language question, we translate it into a query graph pattern, and retive the results by employing pattern match qurey algorithms.

近年来图数据研究引起了学术界和工业界的广泛关注。本项目研究异质信息网络数据中的图匹配查询问题。不同于简单标签图数据，异质信息网络具有丰富的语义信息，可更好地对于现实世界中的图结构数据进行建模，例如RDF语义网络和社会网络数据。由于传统的图模式匹配的方法主要集中在简单标签图，这些方法不能有效地解决语义丰富的异质信息网络的图模式匹配查询问题。为此，本项目的研究围绕图模式匹配这个核心问题，从查询性能和查询语义两个方面系统地研究海量异质信息网络图模式匹配查询。为了提高查询性能，拟提出面向丰富语义信息的异质信息网络的索引机制，基于图结构的物化视图方法，分布式并行环境下的图匹配查询方法等。同时为了支持公众用户在RDF语义网络知识搜索和社会网络数据检索中更方便表示其查询语义，本项目拟研究支持用户输入自然语言问题检索异质信息网络数据的方法，具体指将输入的自然语言问题转换为异质信息网络上的图模式匹配查询图。

围绕着海量异质网络数据问题，本项目开展了如下研究工作：.(1) 异质信息网络的索引技术研究.本项目以社交网络和语义网等真实数据为背景，以异质信息网络为模型，提出该模型下的面向图匹配的查询索引机制和查询优化等相关技术。.此方面，我们提出多种针对异质信息网络查询，包括Skyline查询，图的近似查询等索引结构，并构建相关的系统；论文发表在TKDE，VLDB等。具体见总结报告的第二部分和已发表论文列表。.(2) 基于图结构的物化视图的策略.由于传统的关系数据库是基于关系表结构的，它的物化视图通常也采用关系表来表示。异质信息网络是基于图模型的，传统的基于表的物化方法会带来大量物化空间的浪费。为此，本项目主要关注基于图结构的物化视图的构建，组织等策略来减少空间代价。此方面提出利用查询的日志来挖掘图结构数据中的概念信息，对数据进行物化处理，相关工作发表在EDBT等会议中。.(3) 分布式并行环境下基于语义的异质信息网络的划分策略.不同于传统的图划分的研究，异质信息网络具有大量的语义信息。传统的图划分主要根据图的结构，例如最小切策略 。本项目将着重分析在海量异质信息网络中，基于语义的图数据划分方法。此方面提出了多种分布式环境下的SPARQL查询方法，并构建了相关分布式RDF图数据库系统Distributed gStore，相关工作发表在TKDE和VLDB Journal等国际顶级期刊中。.(4) 基于自然语言问题理解的图模式匹配方法.本项目将研究从自然语言问题到图模式匹配查询的转化。从而支持用户利用自然语言问题的输入来检索带有丰富语义信息的异质信息网络数据。此方面提出了将用户自然语言转换为查询图，并进行匹配得到查询答案，将自然语言问题中的消歧和查询执行结合起来，既提高查询效率，也提高了查询的准确度，论文发表在SIGMOD等。.我们开发了一项开源的图数据库系统gStore，可以支持20-30边亿规模图数据的存储和SPARQL查询工作；其分布式版本可以支持100亿规模的图数据的存储和SPARQL查询。开源系统发布https://github.com/Caesar11/gStore 上。本项目发表论文26篇，其中计算机领域顶级期刊和会议论文12篇(CCF-A)。该项目部分研究成果《海量图结构数据存储和查询优化理论研究》获得2014年中国计算机学会自然科学奖二等奖（邹磊排名第一）