| Autor: |
Hou, Guanhao, Guo, Qintian, Zhang, Fangyuan, Wang, Sibo, Wei, Zhewei |
| Rok vydání: |
2022 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
{\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. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
