Name
Abstract | ||
|---|---|---|
Personalized PageRank (PPR) has been successfully applied to various applications. In real applications, it is important to set PPR parameters in an ad-hoc manner when finding similar nodes because of dynamically changing nature of graphs. Through interactive actions, interactive similarity search supports users to enhance the efficacy of applications. Unfortunately, if the graph is large, interactive similarity search is infeasible due to its high computation cost. Previous PPR approaches cannot effectively handle interactive similarity search since they need precomputation or approximate computation of similarities. The goal of this paper is to efficiently find the top-k nodes with exact node ranking so as to effectively support interactive similarity search based on PPR. Our solution is Castanet. The key Castanet operations are (1) estimate upper/lower bounding similarities iteratively, and (2) prune unnecessary nodes dynamically to obtain top-k nodes in each iteration. Experiments show that our approach is much faster than existing approaches. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2463676.2463717 | SIGMOD Conference |
Keywords | Field | DocType |
personalized pagerank,similarities iteratively,efficient ad-hoc search,approximate computation,interactive similarity search,ppr parameter,key castanet operation,high computation cost,previous ppr,top-k node,interactive action,graph database | PageRank,Graph,Data mining,Graph database,Ranking,Precomputation,Computer science,Theoretical computer science,Nearest neighbor search,Bounding overwatch,Computation | Conference |
Citations | PageRank | References |
22 | 0.75 | 29 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yasuhiro Fujiwara | 1 | 292 | 25.43 |
| Makoto Nakatsuji | 2 | 225 | 13.16 |
| Hiroaki Shiokawa | 3 | 153 | 12.82 |
| Takeshi Mishima | 4 | 41 | 3.56 |
| Makoto Onizuka | 5 | 369 | 33.84 |