随着信息技术的快速发展,查询与推荐在许多方面发挥着越来越重要的作用,人们需要根据相似性的紧密程度进行推荐,SimRank作为一种常用的相似性度量模型已经被广泛应用于推荐系统、协同过滤、链路预测等领域中。在图中基于SimRank度量的单源点Top-k问题因其广泛应用受到了越来越多的关注。大部分已有算法在解决单源点Top-k问题时面临查询时间和空间效率不高的问题,特别是在比较稠密的图中。所以,需要设计时空高效的单源点Top-k算法。本文提出了两种策略来解决该问题。第一种策略利用局部探测方法来解决单源点Top-k问题,主要通过局部路径枚举并结合剪枝技术来减小探测空间,从而加速求解过程。第二种策略利用蒙特卡洛模拟来解决单源点Top-k问题,设计了新的抽样方法,利用路径抽样来代替路径枚举,高效解决了单源点Top-k问题。具体工作如下:基于局部探测的单源点Top-k算法。该方法主要利用局部探测来避免全局计算,利用SimRank值上界来剪枝探测空间从而加速求解Top-k。首先给出了局部探测Top-k的思想及基础方法,然后进一步提出了高效的LST算法。该算法主要分为两步:第一步,根据待查询顶点的邻域信息生成初始的Top-k候选集;第二步,利用所提出的尚未进入候选集的顶点的SimRank值上界与候选集中顶点的当前SimRank最小值在后续局部探测过程中进行剪枝,减小探测空间。算法的时间复杂度为O(d^2l),空间复杂度为O（d^l）,其中d是图中顶点的平均入度,l是随机游走的最大步长。基于蒙特卡洛模拟的单源点Top-k算法。该方法主要利用路径抽样来代替路径枚举,从而降低计算复杂度。首先提出了LMST-US算法,该算法从待查询顶点出发进行均匀抽样来探测Top-k候选集。然后提出了采用分层抽样的LMST-SS算法,并在其基础上分别提出了利用抽样路径树结构的LMST-Tree算法和利用阈值截断的LMST-δ算法。上述算法的时间复杂度为O（rd^l）,空间复杂度为O（d^l）,其中r是抽样数量。该类不同方法在实际中效果不一样,可根据具体情况选择合适的方法。实验结果及分析。实验中首先测试了不同参数对本文提出算法的影响。然后将本文算法与主流的TopSim类算法、KM-SR算法和Sling算法在Top-k查询时间、空间以及准确率等方面进行了比较。实验结果表明,在保证一定准确率的前提下,本文算法在查询时间和空间方面性能优异。在查询时间方面,明显优于KM-SR和TopSim类算法,其中LST算法和需要预处理的Sling查询时间接近,并且在某些数据上优于Sling。在空间方面,本文提出的算法空间占用都较小,特别是基于蒙特卡洛模拟的算法空间占用约为对比算法的10%-55%。