庞悦关于无索引高效可达性算法的论文《IFCA: Index-Free Community-Aware Reachability Processing Over Large Dynamic Graphs》被ICDE 2023录用。

可达性查询检查有向图上是否存在从源顶点到目标顶点的路径，是一种基本的图查询。当前最先进的基于索引的可达性处理框架离线预计算部分或全部可达性信息的概要，以加速在线查询，能够高效处理静态图。然而，近年来越发频繁出现的高度动态图数据向基于索引的方法提出了新的挑战。对于静态索引，随着图的动态变化重建索引会产生大量开销；对于支持动态更新的索引，当更新频繁时，维护成本仍然很高。

为了解决这些挑战，我们提出了一种无索引、社区感知（Index-Free Community-Aware, IFCA）的可达性处理框架。该框架受高效的个性化PageRank（Personalized PageRank）近似算法的启发，能够动态识别图中的社区结构以加速查询。在此基础上，我们设计了一种社区收缩技术来弥合不同社区中顶点之间的鸿沟，并设计了一种基于成本的策略选择程序来有效地处理收缩后的图。我们在大型真实动态图上基于贴近实际的查询负载开展了实验，实验结果表明与当前基于索引和无索引的最先进方法相比，我们的方法更为高效。