Efficient Similarity Search for Sets over Graphs

摘要

Measuring similarities among different nodes is important in graph analysis tasks, such as link prediction, and recommendation. Among different similarity measures, SimRank is one of the most popular and promising ones, and has received a lot of research attention. While most current studies focus on single-pair, single-source/top-k, and all-pairs SimRank computation, few of them have studied finding similar pairs given a set of node pairs, which has attractive applications in personalized search and recommendation tasks. In this paper, we present Carmo, an efficient algorithm for retrieving the top-k similarities from an arbitrary set of pairs. In addition, we introduce two types of indexes to boost the efficiency of Carmo: one is hub-based, the other is tree-based. We show the effectiveness and efficiency of our proposed methods by extensive experiments.