SimRank是一种基于图拓扑结构来评估顶点相似性的方法。基于SimRank的单源Top-k查询问题,是求解与给定查询顶点SimRank相似度最高的k个顶点,其广泛应用于大规模数据图挖掘、协同过滤等领域。现有算法在计算单源顶点的Top-k结果集时,需要预先计算所有顶点与查询顶点之间的SimRank相似度,然后排序筛选出Top-k结果集。由于现有算法在计算过程中存在许多无效计算,导致求解Top-k结果集的效率较低。针对该问题,本文对单源Top-k查询问题进行研究,具体的研究内容如下。首先,提出基于SimRank上下界的Top-k结果集查询算法—HitSim。与现有算法直接计算所有顶点的SimRank不同,HitSim通过缩减所需计算的顶点规模,来提升查询Top-k结果集的效率。其具体思想是:先对顶点进行分类,对不同类顶点分别求出相应的SimRank上界,然后在求解过程中维护Top-k结果集的SimRank下界。通过比较Top-k结果集的下界和不同类顶点集的SimRank上界,来减少所需处理的顶点数量。其次,提出针对稠密图的优化算法HitSim-OPT。由于HitSim对稠密图的顶点进行分类时,顶点可能会集中在一个顶点集中,导致HitSim剪枝效果变差。为解决这一问题,HitSim-OPT直接计算出所有顶点的SimRank上界,在计算过程中维护Top-k结果集的SimRank下界,通过比较上下界,来确定是否需要处理相应的顶点。同时,对需要处理的顶点,使用其SimRank上界来减少反向游走的次数。最后,基于8个真实数据集进行测试,实验结果表明,本文所提出的HitSim算法和HitSim-OPT算法在保证查询结果准确率的基础上,查询效率比现有算法提升近三个数量级。