刘钰关于利用多臂赌博机（multi-armed bandits）计算top-k和thresholding SimRank查询的论文SimTab: AccuracyGuaranteed SimRank Queries through Tighter Confidence Bounds and MultiArmed Bandits被VLDB 2020接收。

      SimRank是衡量图中节点结构相似度的重要指标，而top-k和thresholding SimRank查询是两类具有广泛应用场景的查询。然而，已有SimRank研究主要集中于单对（single-pair）和单源（single-source）SimRank查询；对于top-k和thresholding查询，既不能从理论上保证精确度，在实际情况下也无法达到满意的效果。我们提出了一种SimTab（SimRank queries with Tighter confidence bounds and multi-armed bandits）算法同时回答两种查询。首先，我们使用一些技术使基于随机游走的蒙特卡洛采样的置信区间更紧致。其次，我们从多臂赌博机的角度对两类查询进行建模。因此，我们的算法大幅提升了理论复杂度，使之接近问题的困难度。在此基础上，我们提出了针对SimRank计算的采样策略，对基于MAB的解决方法同时提升了理论和实际效率。我们的算法首次对两类查询给出了理论上的精度保证，并且是唯一能在大图上同时保证高查询质量和快速查询时间的方法。同时，我们也首次对各种top-k和thresholding SimRank查询算法进行了深入的实验评估。