面向大规模图数据的凝聚子图搜索技术研究

批准号:
61902184
项目类别:
青年科学基金项目
资助金额:
27.0 万元
负责人:
袁龙
依托单位:
学科分类:
F0202.系统软件、数据库与工业软件
结题年份:
2022
批准年份:
2019
项目状态:
已结题
项目参与者:
--
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
近年来,随着社交网络,移动互联网等技术的发展,基于图数据分析的应用大量涌现。其中,图数据上的凝聚子图搜索有着重要的社会意义和商业价值。但是,随着大数据时代的到来,图数据的规模不断增大,增长速度不断加快,给传统的搜索技术带来了极大的挑战。本项目围绕着大规模图数据上的凝聚子图搜索问题,从模型有效性、算法高效性和可扩展性三个方面对该问题进行深入研究。在模型有效性方面,本项目将引入结果相关性评价模型,改善搜索结果质量,提高用户体验。在算法高效性方面,本项目将结合凝聚子图的结构特点,挖掘基于内存计算模型的在线搜索算法的潜力,提高搜索性能。在算法可扩展性方面,本项目将研究基于外存计算模型的高效凝聚子图搜索算法,通过将图数据和相关信息存放在外存中,同时设计外存索引结构来实现可扩展的高效凝聚子图搜索。本项目的研究将解决面向大规模图数据的凝聚子图搜索中存在的问题,为相关实际应用打下坚实的基础。
英文摘要
With the development of social network and mobile Internet, lots of applications and services based on graph data analysis and processing appear. Among them, cohesive subgraph search based on the graph data owns important social significance and commercial value. However, in this big data era, not only the volume but also the growing velocity of graph data are big, which brings great challenges to existing technology. In order to address this problem, this project focuses on the cohesive subgraph search problem in big graph data and aims to develop effective, efficient and scalable solutions for the cohesive subgraph search problem. Specifically, regarding effectiveness, this project introduces the relevance evaluation model to refine the search result and improve user experience. Regarding efficiency, this project develops online main memory algorithm through exploring the topological structure properties of cohesive subgraphs to further improve the search efficiency. Regarding scalability, this project leverages the external memory model and investigates the external memory cohesive subgraph search algorithm. To obtain a scalable search algorithm, this project stores the graph data and intermediate results on external memory and devises compact index to achieve the efficient cohesive subgraph search solution. The project can not only address the cohesive subgraph search problem in big graphs but also benefit the related real applications.
近年来,随着社交网络,移动互联网等技术的发展,基于图数据分析的应用大量涌现。其中,图数据上的凝聚子图搜索有着重要的社会意义和商业价值。但是,随着大数据时代的到来,图数据的规模不断增大,增长速度不断加快,给传统的搜索技术带来了极大的挑战。本项目围绕着大规模图数据上的凝聚子图搜索问题,从模型有效性、算法高效性和可扩展性等方面对该问题进行深入研究,提出了包括(k,τ)-truss模型,高效可扩展极大平衡团在线搜索方法,基于索引的(α,β)-core高效可扩展搜索方法等,有效地提高了凝聚子图的搜索效率,为面向大规模图数据的凝聚子图搜索提供有效、快速、可扩展的技术解决方案,为相关实际应用打下坚实的基础。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
Efficient shortest path index maintenance on dynamic road networks with theoretical guarantees
具有理论保证的动态路网最短路径索引高效维护
DOI:10.14778/3377369.3377371
发表时间:2020-01
期刊:Proceedings of the VLDB Endowment
影响因子:2.5
作者:Dian Ouyang;Long Yuan;Lu Qin;Lijun Chang;Ying Zhang;Xuemin Lin
通讯作者:Xuemin Lin
DOI:10.1109/tkde.2021.3137955
发表时间:2023-04
期刊:IEEE Transactions on Knowledge and Data Engineering
影响因子:8.9
作者:Zi Chen;Long Yuan;Li Han;Zhengping Qian
通讯作者:Zhengping Qian
Efficient (α, β)-core computation in bipartite graphs
二分图中的高效 (α, β) 核心计算
DOI:10.1007/s00778-020-00606-9
发表时间:2020
期刊:The VLDB Journal
影响因子:--
作者:Boge Liu;Long Yuan;Xuemin Lin;Lu Qin;Wenjie Zhang;Jingren Zhou
通讯作者:Jingren Zhou
Shortest-Path Queries on Complex Networks: Experiments, Analyses, and Improvement
复杂网络上的最短路径查询:实验、分析和改进
DOI:10.14778/3551793.3551820
发表时间:2022-07
期刊:PVLDB
影响因子:--
作者:Junhua Zhang;Wentao Li;Long Yuan;Lu Qin;Ying Zhang;Lijun Chang
通讯作者:Lijun Chang
Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach
道路网络上高效的标签约束最短路径查询:树分解方法
DOI:10.14778/3494124.3494148
发表时间:2021-11
期刊:Proc. VLDB Endow.
影响因子:--
作者:Junhua Zhang;Long Yuan;Wentao Li;Lu Qin;Ying Zhang
通讯作者:Ying Zhang
国内基金
海外基金
