基于双索引的子图和超图查询方法研究

Subgraph and supergraph querying are research hotspots in graph mining field. With the new graphs constantly being discovered, the interest of graph querying is changing, and therefore the graph query stream is mainly in the form of query graph set. Existing querying methods only build index on graph database, without applying query stream information. It results in low usage of public information on query stream, and degrade the querying efficiency. This project focuses on the feature extraction and index building approaches based on existing querying methods, proposes a double index structure on the graph database and the query stream to improve the querying efficiency. The research content includes the following aspects: (1) Choosing (combine) frequent subtrees or graph topology information (walks and spectra or Laplacian spectra of graph) as index features; (2) Building double index structure on graph database and query stream features, optimizing the index structure according to computation-sharing framework; (3) Obtaining result set through filtering and verification. The research of this project has a very important significance to improve the querying efficiency for query stream.

子图查询和超图查询是图挖掘领域中的研究热点。随着新的图模式不断出现，图查询的兴趣也在不断改变，导致查询流是以查询图集合的形式出现。现存的子图和超图查询方法仅对图数据库建立索引，并未提供查询流的信息，使得查询流的公共信息缺乏有效利用，降低了查询效率。本课题拟结合现存查询方法，研究特征提取和索引建立的方法，提出在图数据库和查询流上建立双索引的方案，实现针对查询流的子图和超图高效查询方法。本课题主要研究内容包括以下三方面：(1)选取频繁子树，或者组合频繁子树和图拓扑结构信息（路径，图谱，拉普拉斯图谱等）作为索引特征；(2)基于索引特征，对图数据库和查询流建立双索引，并且在计算共享框架上优化索引；(3)经过过滤和验证的处理，得到结果集。本课题主要贡献是：将多个图属性组合的方法为特征选取提供了新的思路，并且对图数据库和查询流建立双索引的方案为高效处理子图和超图查询提供了更加宽泛的研究空间。

随着图数据的大规模应用，特别是知识图谱的提出，图数据库上的相关研究成为了新一波的研究热点。本项目针对查询图集合在图数据库上的图查询问题，提出了一些新的解决方法。借鉴现存图查询的方法和思路，挖掘出频繁子树等图特征，并将现存超图查询方法中的计算共享框架应用到子图查询问题中，利用共享最大收益目标选取部分图特征作为索引特征，建立双层索引去加速查询效率。这些方法面向不同类型的图结构进行研究，提出了性能较好的算法，并且为项目组后续的工作奠定了牢靠的理论基础。.在提出的图查询方法基础上，面向建筑行业中设计规范，在构建领域知识图谱过程中提出实体节点和实体间的关系抽取和存储方法，目标是应用图查询方法进行领域信息检索。其中，借鉴图查询双层索引的机制，构建了两类不同词典：i）前序词典和ii）专用词典，并设计了基于词典索引的快速查询方法。该项工作运用提出的图挖掘和图查询方法，对轨道交通领域设计行业的相关信息抽取提供了理论依据。同时，我们也开始和中铁一院进行项目合作，对应的相关网站正在设计和开发。这些成果为轨道交通领域的信息化、智能化、自主化奠定了部分理论基础。.同时，鉴于图可以清晰描述复杂结构，本项目还在提出的双层索引和实体节点提取方法的基础上，对数据库安全访问权限的特性，设计了不同的图结构来表示访问权限控制策略。结合图编码的表示方法，将资源访问矩阵以向量形式存储，提出了基于图结构的访问控制模型。在用户和资源抽象为节点的基础上，访问权限抽象为关系边，提出了面向大数据平台的权限知识图谱构建方法。该项工作为大数据平台的数据访问安全提供了理论基础，并且进一步加强了校企合作。其中，本项目已经和腾讯公司进行共同开发和实现数据安全访问控制，部分功能已经开始在腾讯蓝鲸云平台开始试点应用。