面向大规模图查询问题的通用无损压缩框架研究
结题报告
批准号:
62002236
项目类别:
青年科学基金项目
资助金额:
24.0 万元
负责人:
卢璨
依托单位:
学科分类:
数据科学与大数据计算
结题年份:
2023
批准年份:
2020
项目状态:
已结题
项目参与者:
卢璨
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
客服二维码
微信扫码咨询
中文摘要
图规模庞大且图上计算非常耗时,研发能加速图计算的技术与系统紧迫而必要。图压缩技术通过把顶点合并或把子图压缩成超级顶点来减小其规模,提高查询效率。本项目中,我们将分析当下图压缩和图摘要技术的挑战,提出一个压缩框架用以把具有特定结构的部分压缩成超级顶点,同时赋予其摘要以描述被压缩部分的信息。压缩图具有紧密结构,也能给予经常访问的数据更高优先级。对一系列的查询问题,我们的压缩框架具有通用性与无损性。此外,这些查询的现有算法也可以通过简单修改匹配压缩框架。通常,查询算法仅利用超级顶点摘要便可获得准确结果。本项目旨在解决以下三个问题:面向大规模图查询的通用无损压缩框架,多层次结构的压缩框架,对压缩图的动态维护算法。最后,我们将整合以上技术,提出一个通用无损的压缩框架原型系统。本项目预期产生具有国际影响力的研究成果,包括高水平论文5篇以上,以及自主研发的面向大规模图查询的通用无损的压缩框架的原型系统。
英文摘要
Graphs in real world are often huge and graph computations are always expensive, highlighting the need for developing techniques and systems for speeding up graph computations. Graph contraction is to reduce the scale of big graphs and improve the performance of querying tasks through merging nodes or replacing subgraphs with individual nodes. In this project, we first analyze the challenges in current graph contraction and graph summarization techniques. Then we propose a contraction framework that contracts obsolute componenets as well as structrural components into a supernode with a synoposis that encodes various information of the contracted parts. The contracted graph have a compact form and prioritizes frequently visited data. The contraction scheme is generic and lossless for a number of querying problems. Moreover, existing algorithms for these queries can be readily adapted to compute exact answers by leverging the synopsis when possible, and decontracting the supernodes only when necessary. Specifically, this project aims at solving the following three issues: a generic and lossless contraction framework for large-scale graph querying tasks, an advanced contraction framework in a hierarchical structure, and an incremental contraction algorithm in response to updates. Finally, we will integrate all the above techniques, and plan to propose a generic and lossless graph contraction prototype system for various querying tasks. The expected outputs of this project include more than five high quality papers, as well as a generic and lossless graph contraction prototype system that can support various querying tasks.
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
DOI:10.1007/s00778-022-00731-7
发表时间:2023
期刊:VLDB JOURNAL
影响因子:4.2
作者:Fan, Wenfei;Li, Yuanhao;Liu, Muyang;Lu, Can
通讯作者:Lu, Can
国内基金
海外基金