一个适用于所有情况的指数：实现针对每个阻尼因子的高效个性化PageRank计算

《Proceedings of the ACM on Management of Data》：One Index for All: Towards Efficient Personalized PageRank Computation for Every Damping Factor

针对个性化PageRank单源查询中不同衰减因子α的适应性难题，提出StackIndex元索引方法，通过构建高衰减因子ā的循环消除随机游走路径，实现单次索引即可支持所有α的查询转换，并设计动态更新机制适应图变化，实验验证其速度优势与精度保障。

　　

摘要

个性化PageRank（PPR）是一种基本的图谱邻近度度量方法，具有广泛的应用场景。单源个性化PageRank（SSPPR）查询旨在计算给定源节点所有节点的PPR值。由于精确计算SSPPR的成本较高，大多数现有解决方案都侧重于具有精度保证的近似查询。现有的近似SSPPR查询方法基于索引，通常是为单一的固定α值设计的。然而，现实世界的应用往往需要处理多个α值，而现有的基于索引的方法在不重建索引的情况下难以适应不同的α值。为了解决这一限制，我们提出了一种新颖且高效的SSPPR查询索引方法，该方法支持所有α值。我们方法的一个显著特点是它仅为所有可能的α值存储一个索引。这是通过利用PPR的循环消除α随机游走解释，并构建一个具有足够大阻尼因子ā的堆栈式元索引（StackIndex）来实现的。然后，我们开发了一种新技术，可以高效地将StackIndex转换为任何指定阻尼因子α的新索引，而无需重建索引。我们证明，我们的索引构建算法所需的时间复杂度为O(ωn)，空间复杂度也为O(ωn)，以确保查询的近似精度，其中ω和n分别表示样本大小和图中的节点数量。我们还开发了一种索引维护技术，用于在处理包含边插入和删除的动态图时更新StackIndex。在5个大型真实世界图上的广泛实验表明，与之前的基于索引的方法相比，StackIndex在处理不同α值的PPR查询时显著提高了查询速度，同时保持了相同的精度保证。