大规模图数据的符号表示和管理技术研究

The efficient and compact representation and operation of graph data containing billions of vertices and edges are the fundamental issues for large-scale data analysis and management. Representing graph data compactly can not only reduce the storage space of graph data, but also improve the managing efficiency of graph data. Graph data representation / storage, query / edit operations are the core technologies supporting large scale data management. According to the application requirements of large scale graph data, the mechanism to represent and operate graph using multi-valued decision diagrams will be studied so that the k2-MDD and kn-MDD representation methods supporting compact representation and efficient query of large scale graph data will be proposed. In terms of the management scheme of dynamic two-dimensional and multidimensional data, the dk2-MDD and dkn-MDD representation methods supporting efficient editing operations of large-scale dynamic graph data will be put forward. Based on the relationship between logical calculation of multi-valued decision diagrams and graph editing, the operation function libraries of graph based on above representation methods will be created so as to develop the efficient algorithms for graph data query and editing. It is hopeful that novel and effective theories, methods and techniques for large-scale data management will be presented.

对包含亿万个顶点和边的图数据进行高效、紧凑的表示和操作，是大规模图数据分析与管理的基础。紧凑的图数据表示不仅可以降低图数据的存储空间，而且还可以提高图数据的管理效率。图数据表示/存储、查询/编辑操作是大规模图数据管理的核心支撑技术。本项目拟从大规模图数据的应用需求出发，研究基于多值决策图的图表示和操作机制，建立能够支持对大规模图数据紧凑表示和高效查询的k2-MDD与kn-MDD表示方法；研究动态二维及多维图数据的管理技术，给出支持大规模动态图数据高效编辑操作的dk2-MDD与dkn-MDD表示方法。研究多值决策图的逻辑计算与图编辑之间的联系，提出图数据查询和编辑等操作的高效算法，构建基于这些表示方法的图的基本操作函数库。本项目将为大规模图数据的管理提供新的理论、方法和技术。

k2-tree是一种能够有效压缩和表示图的邻接矩阵的方法，在k2-tree的基础上，引入多值决策图（Multi-valued Decision Diagram，MDD），构建k2-MDD和kd-MDD，能对图数据进行更加紧凑的表示与管理。本项目主要工作及取得的研究成果如下：.（1）提出了一种基于稠密网格聚类算法DGC。将稠密网格聚类算法DGC与k2-tree技术相结合，提出了一种新的图数据压缩表示方法DGC-k2-tree，进一步压缩了图数据存储空间。在此基础上，提出了基于DGC-k2-tree的图查询算法，能够查询结点间的连通性。.（2）提出了一种新的基于聚类和k2-tree 的大规模图数据紧凑表示方法——k2-tree-cluster，然后用k2-tree 紧凑表示稠密块，在此基础上，给出了k2-tree-cluster 的顶点邻居查询算法，包括顶点的直接邻居查询算法和顶点的反向邻居查询算法。.（3）提出了一种基于决策图的时序图数据紧凑表示方法——kd-MDD，给出了基于kd-MDD的时序图的基本操作方法。.（4）提出一种基于多值决策图的Web服务组合模型k2-MDD-WS，采用多值决策图表示服务与服务输入/输出参数之间的关联关系，根据Web服务的相关定义和性质对Web服务集进行建模，并将Web 服务依赖图的直接邻居及反向邻居查询操作转化为多值决策图表示下的布尔逻辑运算操作，提高操作效率。.（5）提出了一种基于多区域的交叉加权聚合深度卷积特征描述算法RCroW。扩展RCroW 算法，提出多层卷积特征聚合生成图像特征向量的描述算法ML-RCroW，该算法将不同层不同分辨率的多个RCroW 特征级联生成最终的特征向量。.（6）给出一种基于中值频率平衡加权的焦点损失函数MFB_Focalloss。给出用于获取上下文信息的下采样块和用于恢复原始分辨率的上采样块的概念，提出一种端到端深度全卷积神经网络DenseU-Net。在DenseU-Net 的基础上，提出一种孪生密集U 型网络SiameseDenseU-Net。.（7）提出一种基于MDD的网络不相交路径可靠性分析算法 MDD_2SMPs。该算法利用MDD能够双向反映组件状态与系统状态关系的特点，构造相应操作函数直接获取工作路径的容量，并通过在组合过程中引入约束剪枝策略过滤路径无效容量状态，简化了可靠性评估过程。