基于大规模图数据的可达性查询处理技术

Large-scale data graphs are frequently generated in the ear of big data and artificial intelligence with complex, large and dynamically updated structures, which are usually used to represent the relationship of Semantic Web, social networks, transportation networks, and biological networks, etc. Among all operations on data graphs, reachability query processing is one of the fundamental operations, which are frequently used to help mining the valuable information behind the given data graphs. Considering the limitation of existing approaches w.r.t. reachability query processing, this project aims to solve the key problems with multiple constrains applied to reachability queries, including (1) general representation of reachability queries, such that to define queries more flexible, (2) pluggable index structures, such that to satisfy the requirement of query constraints, (3) scalable indexing and query processing strategies, such that to process queries more efficiently, (4) partitioning, storing, indexing and queries processing strategies under distributed environment, such that to reduce the synchronization and communication costs, (5) effective graph compression strategies, such that to reduce the index sizes, and (6) efficient updating techniques. This research will provide new solutions and expanding the application areas of large-scale data graphs, and the research results will have important theoretical significances and practical values.

大数据和人工智能时代的来临催生了大量结构复杂、规模庞大且动态变化的数据图，用以描绘数据之间复杂多变的关联性，如语义网、社交网、路网以及生物基因网络等。可达性查询处理是对图数据进行研究和分析，从而挖掘隐藏在数据背后有价值信息最核心的基本操作之一。本项目针对已有方法的特点和应用局限性，研究基于多种约束情况下可达性查询处理的关键技术难题，包括（1）通用可达性查询表示机制，以便灵活指定可达查询，（2）可插拔的索引结构，以满足查询约束的多样性，（3）可扩展的索引构建和查询处理技术，以便高效处理可达查询，（4）基于分布式环境的大图分配存储策略、索引构建策略及并行查询处理策略，以便降低分布式环境下的同步和通讯代价，（5）有效的数据图压缩策略，以降低索引空间，（6）高效的索引更新技术。相关研究成果将为大规模图数据的管理提供新的解决方案，进一步拓宽大规模图数据的应用范围，具有重要的理论意义与实际应用价值。

图可以表示数据之间复杂多变的关联性。随着移动互联网、大数据等技术的普及，产生了大量的规模庞大且动态变化的图数据。可达性查询是对大规模图数据处理的核心操作之一。项目通过四年研究，完成了项目设定的预期目标。提出了大规模图数据可达性查询及K步可达性查询处理方法；对更为复杂的标签约束条件下可达性查询进行了研究，并优化压缩了索引规模；针对动态图更新，提出一种新的BFS生成树更新策略，可以支持有向图上BFS生成树的高效更新。对大规模图数据查询系统而言，项目所研究和解决的问题，可以提高系统的执行效率及准确率，为大规模图数据查询的实用化奠定理论基础、提供技术支撑，具有广泛的应用前景。