论文摘要
计算两点之间的最短距离是标记图的基本操作之一。对于大图,根据路标节点估算两点之间最短距离的方法来提高查询效率。现有的路标节点选择策略不能在中心性和计算量小两方面同时满足,路标节点存储到其他节点的距离信息,存储量仍然很大。对于大规模有向图来说,路标节点选取策略保证中心性的同时减少了计算量,使用了DBSCAN聚类思想将节点划分成不同的类,选择具有联通性的向前和向后核心节点作为向前和向后路标节点;存储类内路标节点与普通节点之间的距离信息以及类间路标节点之间的距离信息来减少存储量;源节点通过向后路标节点和向前路标节点到达目标节点,采用上界和下界的最小均值作为估计值。理论证明算法策略在时间复杂度和空间复杂度方面与传统方法相比降低了。实验证明对于大图在平均相对误差方面与传统方法误差数量级相同。
论文目录
文章来源
类型: 期刊论文
作者: 吕伟,宋文爱,富丽贞,许文
关键词: 图数据,边受限制,预处理,最短距离查询
来源: 计算机工程与应用 2019年07期
年度: 2019
分类: 信息科技,基础科学
专业: 数学,计算机软件及计算机应用
单位: 中北大学软件学院
基金: 国家自然科学基金(No.61602427),山西省自然科学基金(No.201601D202037)
分类号: O157.5;TP301.6
页码: 71-81+86
总页数: 12
文件大小: 1923K
下载量: 111
相关论文文献
- [1].如何利用轴对称求最短距离[J]. 语数外学习(初中版) 2019(10)
- [2].立足数学本质 追求解法自然[J]. 中国数学教育 2017(07)
- [3].初中最短距离问题的解法探究[J]. 数学学习与研究 2018(03)
- [4].从最短距离浅析数学的抽象问题[J]. 数学学习与研究 2017(20)
- [5].利用轴对称求最值[J]. 数理天地(初中版) 2016(04)
- [6].例谈直线上最短距离的求解方法[J]. 中学生数学 2017(06)
- [7].茶,接轨国际的最短距离[J]. 普洱 2017(04)
- [8].物体表面上的最短距离[J]. 中学生数理化(八年级数学)(配合人教社教材) 2017(03)
- [9].基于地图API的最短距离批量计算[J]. 数码世界 2017(07)
- [10].跟笨蛋一起谈恋爱[J]. 喜剧世界(上半月) 2015(02)
- [11].例谈立体图形表面最短距离[J]. 高中数理化 2019(20)
- [12].中考题中常见的最短距离问题剖析[J]. 数学学习与研究 2013(16)
- [13].两点间最短距离及应用[J]. 数理化解题研究(高中版) 2014(11)
- [14].巧解生活中的最短距离问题[J]. 中小学数学(初中版) 2015(11)
- [15].云环境下保护隐私的最短距离计算方法研究[J]. 华中科技大学学报(自然科学版) 2013(S2)
- [16].轴对称与最短距离的不解之缘[J]. 初中生之友 2012(29)
- [17].如何移动煤球[J]. 高中生 2009(22)
- [18].利用轴对称求最短距离的几点思考[J]. 考试周刊 2018(06)
- [19].初中数学中最短距离之例选[J]. 青少年日记(教育教学研究) 2014(02)
- [20].最短距离的深入学习[J]. 中学生数学 2020(20)
- [21].初中几何中常见的3类最短距离问题探究[J]. 中学教研(数学) 2019(05)
- [22].求最短距离的利器——轴对称[J]. 中学生数理化(八年级数学)(配合人教社教材) 2010(Z1)
- [23].从将军饮马问题谈利用轴对称求最短距离的几种模型[J]. 科教导刊(下旬刊) 2020(07)
- [24].找对称 巧转化 重策略——最短距离典型例题赏析[J]. 中学生数理化(八年级数学)(配合人教社教材) 2014(12)
- [25].论述轴对称中最短距离与实际运用[J]. 新课程学习(社会综合) 2009(09)
- [26].基于最短距离的打包任务定价模型[J]. 现代商业 2018(10)
- [27].“两点之间,线段最短”在最短距离问题中的运用[J]. 中学教学参考 2013(05)
- [28].困惑的小蚂蚁——例谈初中数学中的最短距离[J]. 中学教学参考 2018(14)
- [29].最短距离问题的解题策略[J]. 中学数学研究(华南师范大学版) 2014(Z1)
- [30].初中数学中最短距离问题例析[J]. 中学教学参考 2018(23)