论文标题
具有增量索引更新方案的演变图表上的个性化Pagerank
Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme
论文作者
论文摘要
{\ em个性化的pagerank（ppr）}是图挖掘中的基本接近度度量。由于计算确切的SSPPR查询答案是过于良好的，因此大多数现有的解决方案转向具有保证的近似查询。用于近似SSPPR查询的最新解决方案是基于索引的，主要关注静态图，而实际图通常是动态变化的。但是，现有的索引更新方案无法达到次线性更新时间。在此激励的情况下，我们提出了一个有效的索引方案，以在每个图表更新后将索引随机步行保持预期$ O（1）$。为了减少空间消耗，我们进一步提出了一种新的采样方案，以删除顶点的辅助数据结构，同时仍支持$ o（1）$ o（1）$ index更新成本。广泛的实验表明，我们的更新方案达到了在现有基于索引的动态方案上更新性能的速度速度，而无需牺牲查询效率。
{\em Personalized PageRank (PPR)} stands as a fundamental proximity measure in graph mining. Since computing an exact SSPPR query answer is prohibitive, most existing solutions turn to approximate queries with guarantees. The state-of-the-art solutions for approximate SSPPR queries are index-based and mainly focus on static graphs, while real-world graphs are usually dynamically changing. However, existing index-update schemes can not achieve a sub-linear update time. Motivated by this, we present an efficient indexing scheme to maintain indexed random walks in expected $O(1)$ time after each graph update. To reduce the space consumption, we further propose a new sampling scheme to remove the auxiliary data structure for vertices while still supporting $O(1)$ index update cost on evolving graphs. Extensive experiments show that our update scheme achieves orders of magnitude speed-up on update performance over existing index-based dynamic schemes without sacrificing the query efficiency.
