Probesim: scalable single-source and top-k simrank computations on dynamic graphs

Show full item record



Permalink

http://hdl.handle.net/10138/307767

Citation

Liu , Y , Zheng , B , He , X , Wei , Z , Xiao , X , Zhen , K & Lu , J 2017 , ' Probesim: scalable single-source and top-k simrank computations on dynamic graphs ' , Proceedings of the VLDB Endowment , vol. 11 , no. 1 , pp. 14-26 . https://doi.org/10.14778/3151113.3151115

Title: Probesim: scalable single-source and top-k simrank computations on dynamic graphs
Author: Liu, Yu; Zheng, Bolong; He, Xiaodong; Wei, Zhewei; Xiao, Xiaokui; Zhen, Kai; Lu, Jiaheng
Contributor: University of Helsinki, Department of Computer Science
Date: 2017-09-01
Belongs to series: Proceedings of the VLDB Endowment
ISSN: 2150-8097
URI: http://hdl.handle.net/10138/307767
Abstract: Single-source and top-k SimRank queries are two important types of similarity search in graphs with numerous applications in web mining, social network analysis, spam detection, etc. A plethora of techniques have been proposed for these two types of queries, but very few can efficiently support similarity search over large dynamic graphs, due to either significant preprocessing time or large space overheads. This paper presents ProbeSim, an index-free algorithm for single-source and top-k SimRank queries that provides a nontrivial theoretical guarantee in the absolute error of query results. ProbeSim estimates SimRank similarities without precomputing any indexing structures, and thus can naturally support real-time SimRank queries on dynamic graphs. Besides the theoretical guarantee, ProbeSim also offers satisfying practical efficiency and effectiveness due to non-trivial optimizations. We conduct extensive experiments on a number of benchmark datasets, which demonstrate that our solutions outperform the existing methods in terms of efficiency and effectiveness. Notably, our experiments include the first empirical study that evaluates the effectiveness of SimRank algorithms on graphs with billion edges, using the idea of pooling.
Subject: 113 Computer and information sciences
111 Mathematics
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
1709.06955.pdf 426.1Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record