大规模图数据管理中结构相似度查询处理技术研究

Graph is a universal data structure that can be used to express complex structures and semantics. There exist graph-related applications everywhere in the real world, such as transportation networks and social relations, etc. As long with the proliferation of entity sizes in practice, the sizes of graph data are growing rapidly, which poses severe challenges to the management and analytics of large-scale graph data. This project investigates structural similarity query processing over large-scale graph data; it aims to present an efficient structural query processing solution, to meet the needs of current massive graph data management. Following research is proposed and planed: (1) Regarding structural similarity measures, we will put forward a unified classification framework to assist the selection of appropriate measures for tailored requirements; (2) We will devise a practical measure on multi-attribute heterogeneous networks. Employing the extensible distributed computing platform and existing graph partitioning strategies, we will further design efficient structural similarity query processing algorithms with index support, improving system response time; (3) As to dynamic evolving graphs, we will propose effective partition management mechanism to update the graphs, with dual-target of minimizing communication cost and balancing workload; and (4) On top of rigid theoretical analyses, extensive experiments will be conducted on real massive graphs to demonstrate the efficiency and scalability of the proposed techniques.

图作为一种通用的数据结构可表示复杂的结构和语义，现实世界中与图相关的应用几乎无所不在，如交通网络和社交关系等。真实世界中实体规模的扩张导致相应图规模激增，大规模图数据对其管理与分析技术提出了巨大挑战。本项目研究大规模图数据管理中结构相似度查询处理技术，旨在提出高效的结构查询解决方案，满足当前处理大规模图数据需要。拟开展以下研究：1）在结构相似度度量方面，提出统一的分类框架，辅助用户筛选满足应用需求的度量；2）针对多属性异构信息网络，构造实用合理的结构相似度度量；采用可扩展分布式计算平台处理大规模图数据，基于现有图划分优化策略，设计高效的结构相似度查询算法和索引支持，提高系统查询响应性能；3） 考虑动态演进图，提出有效的图划分管理机制，支持图结构的持续更新，并满足通信代价最小化和负载均衡的目标；4） 基于严格理论分析的基础上，在真实大规模图数据上开展广泛实验论证所提技术的高效性和可扩展性。

图作为一种通用的数据结构可表示复杂的结构和语义，现实世界中与图相关的应用几乎无所不在，如交通网络和社交关系等。真实世界中实体规模的扩张导致相应图规模激增，大规模图数据对其管理与分析技术提出了巨大挑战。本项目研究大规模图数据管理中结构相似度查询处理技术，旨在提出高效的结构查询解决方案，满足当前处理大规模图数据需要。.在项目的支持下，开展了以下计划书中规定的研究：1）统一的结构相似度度量分类框架及算法支持；2）面向大规模多属性异构图的结构相似度查询方法；3）适应动态演进网络图的结构相似度查询方法；4）基于真实数据的对比验证和技术有效性评估。除此之外，还根据研究需要考察了：5）面向大规模单幅图的频繁子图挖掘算法；6）分布式子图挖掘中的通信开销与调度优化技术。.通过科研攻关，取得了一系列重要科研成果：1）在图结构相似度检索问题上，采用无固定尺寸、不相互重叠的子结构作为索引，提出了一种基于图划分的解决方案；2）在大规模单图上的频繁子图发现问题上，利用分布式大图处理框架Pregel，设计了一种高效可扩展的频繁模式挖掘算法；3）在节点相似度匹配问题上，基于SimRank提出了一种增量算法，用于高效的top-k点对的快速检索；4）在大图计算模型上，针对现有大数据计算模型对图计算的不适配，改进了一种基于分离器和组合器的BSP大图计算模型；5）针对动态图模式匹配问题，设计了一种基于结构分解的动态模式匹配方法，通过动态维护匹配结果集实现高效求解。.至此，已达成了关于人才培养、国内外学术交流等方面预期目标，尤其是在1）高水平学术论文方面，在项目执行期间共发表学术论文29篇，SCI检索6篇，并包括了VLDB Journal、SIGIR、IEEE TNNLS等国际高水平期刊和会议论文和《软件学报》《计算机学报》等国内高水平期刊论文；2）知识产权保护方面，申请和受理国家发明专利18项，国防发明专利2项，其中2项已授权，其余均已进入实质审查阶段。