光熙论坛第762期:大规模图分析关键技术研究

光熙论坛第762期:大规模图分析关键技术研究

主讲人:万晓珑 哈工大计算学部博士研究生

时间:2021年12月25日 9:00~10:00

地点:腾讯会议ID: 796 620 331

研究方向:图数据分析

内容简介:
       图数据分析是当下研究的热点问题,其在社交网络,生物网络,道路网络,语义网络等等,都具有广泛的应用。然而,由于近年来内外存存储介质的发展差异,图数据体积的爆炸性增长,以及图模型中混合复杂信息等因素,传统图分析算法在处理大规模图分析任务时面临着如下挑战:(1)大规模图内外存计算的代价昂贵。传统内存算法需要将全部图数据导入内存中,计算环境设备配置价格昂贵。外存算法需要保证在内存空间很小的情况下算法依旧可以运行,计算时间代价昂贵,难以应用于目前的大规模图数据。(2)大规模图复杂信息引发的特定环境下高效图分析问题。例如,在大规模标签图数据中,相比于两点之间是否可达,目前两点间是否在一定限制内可达更加复杂,在实际应用中也更为重要。
       针对上述两个挑战,本人从图分析的四个基础操作的角度,即:深度优先搜索、强连通分量计算、可达性查询和子图匹配问题,开展以下研究,并取得了一定的研究成果。
       1.高效的半外存深度优先搜索算法
       2.高效的半外存强连通分量计算算法
       3.知识图谱上的标签和子结构受限的可达性查询
       4.内存受限性情况下的大规模知识图谱近似查询算法