Efficient SimRank-based Similarity Join Over Large Graphs

被引:44
作者
Zheng, Weiguo [1 ]
Zou, Lei [1 ]
Feng, Yansong [1 ]
Chen, Lei [2 ]
Zhao, Dongyan [1 ]
机构
[1] Peking Univ, Beijing, Peoples R China
[2] Hong Kong Univ Sci & Technol, Hong Kong, Hong Kong, Peoples R China
来源
PROCEEDINGS OF THE VLDB ENDOWMENT | 2013年 / 6卷 / 07期
基金
国家高技术研究发展计划(863计划);
关键词
D O I
10.14778/2536349.2536350
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
Graphs have been widely used to model complex data in many real-world applications. Answering vertex join queries over large graphs is meaningful and interesting, which can benefit friend recommendation in social networks and link prediction, etc. In this paper, we adopt "SimRank" to evaluate the similarity of two vertices in a large graph because of its generality. Note that "SimRank" is purely structure dependent and it does not rely on the domain knowledge. Specifically, we define a SimRank-based join (SRJ) query to find all the vertex pairs satisfying the threshold in a data graph G. In order to reduce the search space, we propose an estimated shortest-path distance based upper bound for SimRank scores to prune unpromising vertex pairs. In the verification, we propose a novel index, called h-go cover, to efficiently compute the SimRank score of a single vertex pair. Given a graph G, we only materialize the SimRank scores of a small proportion of vertex pairs (called h-go covers), based on which, the SimRank score of any vertex pair can be computed easily. In order to handle large graphs, we extend our technique to the partition-based framework. Thorough theoretical analysis and extensive experiments over both real and synthetic datasets confirm the efficiency and effectiveness of our solution.
引用
收藏
页码:493 / 504
页数:12
相关论文
共 50 条
[41]   Efficient Closest Community Search over Large Graphs [J].
Cai, Mingshen ;
Chang, Lijun .
DATABASE SYSTEMS FOR ADVANCED APPLICATIONS (DASFAA 2020), PT II, 2020, 12113 :569-587
[42]   Efficient Subgraph Search over Large Uncertain Graphs [J].
Yuan, Ye ;
Wang, Guoren ;
Wang, Haixun ;
Chen, Lei .
PROCEEDINGS OF THE VLDB ENDOWMENT, 2011, 4 (11) :876-886
[43]   Efficient Privacy Preserving Protocols for Similarity Join [J].
Hawashin, Bilal ;
Fotouhi, Farshad ;
Truta, Traian Marius ;
Grosky, William .
TRANSACTIONS ON DATA PRIVACY, 2012, 5 (01) :297-330
[44]   EFFICIENT STRING EDIT SIMILARITY JOIN ALGORITHM [J].
Gouda, Karam ;
Rashad, Metwally .
COMPUTING AND INFORMATICS, 2017, 36 (03) :683-704
[45]   UniWalk: Unidirectional Random Walk Based Scalable SimRank Computation over Large Graph [J].
Luo, XiongCai ;
Gao, Jun ;
Zhou, Chang ;
Yu, Jeffrey Xu .
2017 IEEE 33RD INTERNATIONAL CONFERENCE ON DATA ENGINEERING (ICDE 2017), 2017, :325-336
[46]   Efficient and Scalable Processing of String Similarity Join [J].
Rong, Chuitian ;
Lu, Wei ;
Wang, Xiaoli ;
Du, Xiaoyong ;
Chen, Yueguo ;
Tung, Anthony K. H. .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2013, 25 (10) :2217-2230
[47]   I/O-Efficient Similarity Join [J].
Paghl, Rasmus ;
Phaml, Ninh ;
Silvestril, Francesco ;
Stockel, Morten .
ALGORITHMS - ESA 2015, 2015, 9294 :941-952
[48]   I/O-Efficient Similarity Join [J].
Pagh, Rasmus ;
Pham, Ninh ;
Silvestri, Francesco ;
Stockel, Morten .
ALGORITHMICA, 2017, 78 (04) :1263-1283
[49]   I/O-Efficient Similarity Join [J].
Rasmus Pagh ;
Ninh Pham ;
Francesco Silvestri ;
Morten Stöckel .
Algorithmica, 2017, 78 :1263-1283
[50]   UniWalk: Unidirectional Random Walk Based Scalable SimRank Computation over Large Graph [J].
Song, Junshuai ;
Luo, Xiongcai ;
Gao, Jun ;
Zhou, Chang ;
Wei, Hu ;
Yu, Jeffery Xu .
IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 2018, 30 (05) :992-1006