Efficient Ad-hoc Search for Personalized PageRank

Summary: Castanet enables efficient ad-hoc top-k Personalized PageRank search for interactive similarity on large graphs. It iteratively bounds similarities and dynamically prunes nodes to yield exact rankings without precomputation, outperforming prior approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4712
Venue: SIGMOD
Year: 2013
Pagerank: 9.6436348e-05
Overall Rank: 1,838 | 87.40%
DOI: 10.1145/2463676.2463717

Incoming Non-self Citations Over Time

Authors

1. Yasuhiro Fujiwara (Nippon Telegraph and Telephone Corporation)
2. Makoto Nakatsuji (Nippon Telegraph and Telephone Corporation)
3. Hiroaki Shiokawa (Nippon Telegraph and Telephone Corporation)
4. Takeshi Mishima (Nippon Telegraph and Telephone Corporation)
5. Makoto Onizuka (Nippon Telegraph and Telephone Corporation)

BibTeX Citation

@inproceedings{fujiwara_sigmod13,
        title = {{Efficient Ad-hoc Search for Personalized PageRank}},
        author = {Fujiwara, Yasuhiro and Nakatsuji, Makoto and Shiokawa, Hiroaki and Mishima, Takeshi and Onizuka, Makoto},
        series = {{SIGMOD} '13},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2463676.2463717},
        url = {https://dl.acm.org/doi/10.1145/2463676.2463717},
        year = {2013}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,628	Fast and Unified Local Search for Random Walk Based K-Nearest-Neighbor Query in Large Graphs	2014	SIGMOD	0.00010186757
2,073	BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart	2017	SIGMOD	9.2209912e-05
2,173	Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push	2021	SIGMOD	9.0375634e-05
2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB	8.9183159e-05
3,210	Zebra: When Temporal Graph Neural Networks Meet Temporal Personalized PageRank	2023	VLDB	7.6352864e-05
3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD	7.5274958e-05
3,892	Massively Parallel Algorithms for Personalized PageRank	2021	VLDB	7.0430255e-05
4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD	6.9479974e-05
4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB	6.821373e-05
4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD	6.5497309e-05
6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD	5.927015e-05
6,655	Indexed Fast Network Proximity Querying	2018	VLDB	5.8125709e-05
8,062	Efficient Personalized PageRank Computation: The Power of Variance-Reduced Monte Carlo Approaches	2023	SIGMOD	5.4949527e-05
12,153	Scaling Manifold Ranking Based Image Retrieval	2015	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
285	ObjectRank: Authority-Based Keyword Search in Databases	2004	VLDB	0.00022365284
556	Fast Incremental and Personalized PageRank	2011	VLDB	0.00016564032
945	Fast Personalized PageRank on MapReduce	2011	SIGMOD	0.00013066956
1,414	Fast and Exact Top-k Search for Random Walk with Restart	2012	VLDB	0.00010848387
3,021	SCARAB: Scaling Reachability Computation on Large Graphs	2012	SIGMOD	7.8401031e-05
5,749	RankMass Crawler: A Crawler with High Personalized PageRank Coverage Guarantee	2007	VLDB	6.1008193e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,714	Personalized PageRank on Evolving Graphs with an Incremental Index-Update Scheme	2023	SIGMOD
2	6,284	Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach	2022	SIGMOD
3	5,250	Parallel Personalized PageRank on Dynamic Graphs	2018	VLDB
4	1,339	Computing Personalized PageRank Quickly by Exploiting Graph Structures	2014	VLDB
5	5,741	Efficient Algorithms for Finding Approximate Heavy Hitters in Personalized PageRanks	2018	SIGMOD
6	4,225	Realtime Top-k Personalized PageRank over Large Graphs on GPUs	2020	VLDB
7	4,024	TopPPR: Top-k Personalized PageRank Queries with Precision Guarantees on Large Graphs	2018	SIGMOD
8	2,225	HubPPR: Effective Indexing for Approximate Personalized PageRank	2017	VLDB
9	3,315	Distributed Algorithms on Exact Personalized PageRank	2017	SIGMOD
10	2,362	Incremental and Accuracy-Aware Personalized PageRank through Scheduled Approximation	2013	VLDB