实验室动态

[2017 ACM TODS] Efficient SimRank-based Similarity Join

郑卫国的论文(Efficient SimRank-based Similarity Join)被 ACM Transactions on Database Systems (ACM TODS) 所录用。

图模型已经被广泛用于建模实际应用中的复杂数据,回答图数据上的顶点集合的连接查询是一个十分有意义的研究任务,它可以用来辅助在社交网络上进行朋友推荐或链接预测。本文采用 SimRank 作为衡量两个顶点之间的相似度量,具体而言,给定两个顶点集合,计算出其中 SimRank 分值高于阈值的顶点对。为了提高计算效率,本文提出了一个基于最短路径计算 SimRank 上界来过滤顶点对的方法。此外,本文提出了一个有效的索引(h-go cover+)来计算单个顶点对之间的 SimRank,即只需要物化一小部分的顶点对的 SimRank,基于此任何顶点对之间的 SimRank 可以很容易地计算出来。为了计算这个索引,我提出了一个不需要构建顶点对图的方法,从而可以支持规模很大的图数据。在真实数据和人工数据上的大量实验验证了方法的有效性。