基于SimRank相似性度量的图中Top-k查询

论文摘要

随着信息技术的快速发展,查询与推荐在许多方面发挥着越来越重要的作用,人们需要根据相似性的紧密程度进行推荐,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(d2l),空间复杂度为O（dl）,其中d是图中顶点的平均入度,l是随机游走的最大步长。基于蒙特卡洛模拟的单源点Top-k算法。该方法主要利用路径抽样来代替路径枚举,从而降低计算复杂度。首先提出了LMST-US算法,该算法从待查询顶点出发进行均匀抽样来探测Top-k候选集。然后提出了采用分层抽样的LMST-SS算法,并在其基础上分别提出了利用抽样路径树结构的LMST-Tree算法和利用阈值截断的LMST-δ算法。上述算法的时间复杂度为O（rdl）,空间复杂度为O（dl）,其中r是抽样数量。该类不同方法在实际中效果不一样,可根据具体情况选择合适的方法。实验结果及分析。实验中首先测试了不同参数对本文提出算法的影响。然后将本文算法与主流的TopSim类算法、KM-SR算法和Sling算法在Top-k查询时间、空间以及准确率等方面进行了比较。实验结果表明,在保证一定准确率的前提下,本文算法在查询时间和空间方面性能优异。在查询时间方面,明显优于KM-SR和TopSim类算法,其中LST算法和需要预处理的Sling查询时间接近,并且在某些数据上优于Sling。在空间方面,本文提出的算法空间占用都较小,特别是基于蒙特卡洛模拟的算法空间占用约为对比算法的10%-55%。

论文目录

文章来源

类型: 硕士论文

作者: 王玉龙

导师: 霍红卫

关键词: 局部探测,蒙特卡洛模拟,剪枝

来源: 西安电子科技大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 西安电子科技大学

分类号: O157.5

DOI: 10.27389/d.cnki.gxadu.2019.001891

总页数: 88

文件大小: 3651K

下载量: 43

相关论文文献

• [1].基于蒙特卡洛模拟的机载光电平台测角精度分析[J]. 电子测量与仪器学报 2015(03)
• [2].基于蒙特卡洛模拟的非匀质长浅边坡失稳风险评估方法[J]. 城市地理 2017(02)
• [3].基于蒙特卡洛模拟和挣值分析的项目完工预测优化[J]. 科技管理研究 2019(17)
• [4].基于蒙特卡洛模拟的海上边际油田开发经济评价[J]. 商场现代化 2012(06)
• [5].γ射线吸收系数蒙特卡洛模拟验证与展望[J]. 工程技术研究 2020(14)
• [6].拟蒙特卡洛模拟方法在期权定价中的应用研究[J]. 科学与管理 2017(01)
• [7].蒙特卡洛模拟模型在投资决策中的应用[J]. 中国管理信息化 2012(08)
• [8].氦气在氩霜表面吸附的巨正则蒙特卡洛模拟[J]. 低温工程 2014(01)
• [9].基于蒙特卡洛模拟的连续下降运行间隔分析[J]. 交通信息与安全 2018(06)
• [10].蒙特卡洛模拟在工程经济评价中应用研究[J]. 科技风 2019(26)
• [11].蒙特卡洛模拟在全国矿产资源潜力评价中的应用[J]. 地球物理学进展 2012(05)
• [12].浅谈风险决策实验教学的蒙特卡洛模拟分析框架[J]. 决策探索(下) 2018(12)
• [13].基于蒙特卡洛模拟的电力客户满意度测评[J]. 电网与清洁能源 2019(01)
• [14].基于蒙特卡洛模拟的有色多金属矿山边界品位动态优化管理[J]. 黄金科学技术 2014(02)
• [15].氧化铝薄膜的外逸电子蒙特卡洛模拟[J]. 新疆大学学报(自然科学版) 2010(02)
• [16].高速铁路电力系统防雷研究与应用[J]. 新型工业化 2020(03)
• [17].基于AWS云平台的蒙特卡洛模拟[J]. 现代信息科技 2018(12)
• [18].基于蒙特卡洛模拟的图像二值化增强算法（英文）[J]. Journal of Central South University 2019(06)
• [19].基于蒙特卡洛模拟的基本预备费估算[J]. 煤炭技术 2011(10)
• [20].基于蒙特卡洛模拟的境外矿业投资风险分析[J]. 工业技术经济 2019(03)
• [21].基于蒙特卡洛模拟的我国老年人长期照护需求测算[J]. 山东大学学报(医学版) 2019(08)
• [22].蒙特卡洛模拟在“计量经济学”教学中的应用研究[J]. 中国市场 2018(03)
• [23].基于蒙特卡洛模拟的工程项目网络计划进度风险分析[J]. 项目管理技术 2013(11)
• [24].基于蒙特卡洛模拟的房地产项目投资决策风险评估研究[J]. 住宅与房地产 2019(19)
• [25].改进拉丁超立方蒙特卡洛模拟[J]. 吉林大学学报(信息科学版) 2018(04)
• [26].国内结构化理财产品的定价问题研究[J]. 烟台大学学报(哲学社会科学版) 2018(04)
• [27].高中数学建模[J]. 高中数理化 2020(17)
• [28].运用蒙特卡洛模拟城市供水网络可靠性实例分析[J]. 甘肃科学学报 2013(01)
• [29].高中数学建模[J]. 高中数理化 2019(16)
• [30].高中数学建模[J]. 高中数理化 2020(07)

标签：局部探测论文;  蒙特卡洛模拟论文;  剪枝论文;