大规模图数据中可达性索引技术研究

With the rapid development of social networks, biology, ontology and other emerging areas, there are a lot of graph data in real applications. In the era of Big Data, data growth rate has been far beyond our imagination. Reachability query is one of the fundamental queries in graphs. To greatly improve the efficiency of reachability query, a lot of reachability index are proposed. These approaches have been widely used in many areas of computer science, such as software engineering, programming languages, distributed computing, social network analysis, biological network analysis, XML database, RDF databases, routing planning and other fields. In this project, we first survey the state of the art of reachablity indexing. Then, according to the problems existing of these index in real applications, this project systematic explore the processing of reachablity query on large-scale graph data, including static graph data and dynamic graph data, and we mainly focus on three key issues: index creating, index updating and processing of reachability query. These studies will provide new ideas and technical support for related researches on software engineering, programming languages, distributed computing, social network analysis, biological network analysis, XML database, RDF databases, routing planning and other fields.

随着社交网络，生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据。在“Big Data” 时代，数据规模增长的速度已经远远超出了人们的想象。可达性查询是有向图上最基本的查询。可达性索引方法的提出大大提高了在大图数据上的可达性查询效率，已经被广泛应用于多个计算机科学领域，如软件工程、 编程语言、分布式计算、社交网络分析、 生物网络分析、XML和RDF数据库、路由规划等领域。本项目深入分析了国内外可达性索引技术的研究现状。在此基础上，本项目针对现有可达性索引技术存在的问题，系统研究大规模图数据上可达性查询处理问题，包括静态以及动态两类图数据，重点研究索引构建技术、索引更新技术以及可达性查询处理技术。通过本项目的研究为软件工程、 编程语言、分布式计算、社交网络分析、 生物网络分析、XML和RDF数据库、路由规划等领域的相关研究提供技术支撑和新的思路。

随着社交网络，生物信息网、本体等新兴领域的飞速发展，在现实应用中涌现出大量的图数据。可达性查询是有向图上最基本的查询。可达性索引方法的提出大大提高了可达性查询处理的效率。但现有可达性索引方法面临三个挑战性问题：扩展瓶颈、难以支持受限可达性查询、难以处理动态图数据。项目组针对这三个挑战性问题展开研究：1）针对热点查询，项目组提出一种HotRI索引模式，该方法能够依据热点的热度设计索引，做到按需分配；2）针对受限的可达性查询，项目组提出一种支持查询节点受限查询的可达性索引方法（k-GRIFS索引）以及一种支持距离受限查询的可达性索引方法（DCRI索引）；3）针对动态图数据，项目组提出一种基于划分的总分式动态索引技术（DynamicRI索引）。实验结果表明项目组提出的几类索引模式在处理大规模数据时具有高效性，有效地缓解了扩展瓶颈问题。项目成果最终可为文本语义分析、 语义网、分布式计算、社交网络分析、 生物信息网络分析，本体、XML 和 RDF 数据库、路由规划等领域的相关研究提供技术支撑和新的思路。