Cache-Efficient Approach for Index-Free Personalized PageRank
Personalized PageRank (PPR) measures the importance of vertices with respect to a source vertex. Since real-world graphs are evolving rapidly, PPR computation methods need to be index-free and fast. Unfortunately, existing index-free methods suffer from cache misses. They follow the state-of-the-art...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2023-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10018394/ |
| _version_ | 1797944116781252608 |
|---|---|
| author | Kohei Tsuchida Naoki Matsumoto Andrew Shin Kunitake Kaneko |
| author_facet | Kohei Tsuchida Naoki Matsumoto Andrew Shin Kunitake Kaneko |
| author_sort | Kohei Tsuchida |
| collection | DOAJ |
| description | Personalized PageRank (PPR) measures the importance of vertices with respect to a source vertex. Since real-world graphs are evolving rapidly, PPR computation methods need to be index-free and fast. Unfortunately, existing index-free methods suffer from cache misses. They follow the state-of-the-art algorithm that first performs the Forward Push (FP) phase and subsequently runs the random walk Monte-Carlo simulation (MC) phase. Although existing methods succeed in reducing cache misses in the FP phase, an inefficient data layout limits their performance improvement. Besides, existing methods have overlooked the importance of reducing cache misses in the MC phase. In this paper, we propose a cache-efficient approach that accelerates both FP and MC phases. In the FP phase, we first reorder the data layout with low overheads. Specifically, we utilize the Breadth First Search result so that vertices near the source vertex are co-located on the reordered data layout. We subsequently perform optimized FP, namely Distance-Extension Forward Push (DEFP). By preferentially proceeding FP around the source vertex, DEFP improves memory access locality. In the MC phase, we perform optimized MC, namely Vertex-Centric Random Walk (VCRW). VCRW aggregates random walks at each vertex to eliminate redundant memory access for repeatedly obtaining neighbor vertices. We prove that most of the random walks can be aggregated while maintaining accuracy guarantees. Experimental results show that the proposed method is up to 4.7x faster than existing index-free methods and outperforms the state-of-the-art index-oriented method under rigorous accuracy guarantees. |
| first_indexed | 2024-04-10T20:33:31Z |
| format | Article |
| id | doaj.art-05c3d59626524f30919b854360218346 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-10T20:33:31Z |
| publishDate | 2023-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-05c3d59626524f30919b8543602183462023-01-25T00:00:20ZengIEEEIEEE Access2169-35362023-01-01116944695710.1109/ACCESS.2023.323773810018394Cache-Efficient Approach for Index-Free Personalized PageRankKohei Tsuchida0https://orcid.org/0000-0002-5576-357XNaoki Matsumoto1Andrew Shin2https://orcid.org/0000-0002-0969-9925Kunitake Kaneko3Graduate School of Science and Technology, Keio University, Kanagawa, JapanResearch Institute for Digital Media and Content, Keio University, Kanagawa, JapanResearch Institute for Digital Media and Content, Keio University, Kanagawa, JapanResearch Institute for Digital Media and Content, Keio University, Kanagawa, JapanPersonalized PageRank (PPR) measures the importance of vertices with respect to a source vertex. Since real-world graphs are evolving rapidly, PPR computation methods need to be index-free and fast. Unfortunately, existing index-free methods suffer from cache misses. They follow the state-of-the-art algorithm that first performs the Forward Push (FP) phase and subsequently runs the random walk Monte-Carlo simulation (MC) phase. Although existing methods succeed in reducing cache misses in the FP phase, an inefficient data layout limits their performance improvement. Besides, existing methods have overlooked the importance of reducing cache misses in the MC phase. In this paper, we propose a cache-efficient approach that accelerates both FP and MC phases. In the FP phase, we first reorder the data layout with low overheads. Specifically, we utilize the Breadth First Search result so that vertices near the source vertex are co-located on the reordered data layout. We subsequently perform optimized FP, namely Distance-Extension Forward Push (DEFP). By preferentially proceeding FP around the source vertex, DEFP improves memory access locality. In the MC phase, we perform optimized MC, namely Vertex-Centric Random Walk (VCRW). VCRW aggregates random walks at each vertex to eliminate redundant memory access for repeatedly obtaining neighbor vertices. We prove that most of the random walks can be aggregated while maintaining accuracy guarantees. Experimental results show that the proposed method is up to 4.7x faster than existing index-free methods and outperforms the state-of-the-art index-oriented method under rigorous accuracy guarantees.https://ieeexplore.ieee.org/document/10018394/Personalized pagerankindex-freegraph reorderingforward pushrandom walk monte-carlo simulation |
| spellingShingle | Kohei Tsuchida Naoki Matsumoto Andrew Shin Kunitake Kaneko Cache-Efficient Approach for Index-Free Personalized PageRank IEEE Access Personalized pagerank index-free graph reordering forward push random walk monte-carlo simulation |
| title | Cache-Efficient Approach for Index-Free Personalized PageRank |
| title_full | Cache-Efficient Approach for Index-Free Personalized PageRank |
| title_fullStr | Cache-Efficient Approach for Index-Free Personalized PageRank |
| title_full_unstemmed | Cache-Efficient Approach for Index-Free Personalized PageRank |
| title_short | Cache-Efficient Approach for Index-Free Personalized PageRank |
| title_sort | cache efficient approach for index free personalized pagerank |
| topic | Personalized pagerank index-free graph reordering forward push random walk monte-carlo simulation |
| url | https://ieeexplore.ieee.org/document/10018394/ |
| work_keys_str_mv | AT koheitsuchida cacheefficientapproachforindexfreepersonalizedpagerank AT naokimatsumoto cacheefficientapproachforindexfreepersonalizedpagerank AT andrewshin cacheefficientapproachforindexfreepersonalizedpagerank AT kunitakekaneko cacheefficientapproachforindexfreepersonalizedpagerank |