首页> 中文会议>第29届中国数据库学术会议 >不确定图上期望最短距离的计算

不确定图上期望最短距离的计算

页面导航

摘要
著录项
相似文献
相关主题

摘要

研究了不确定图上的最短距离问题,提出了期望最短距离的概念,证明了该问题不存在多项式时间的算法.为了解决该问题,使用了随机采样技术获得不确定图的一些可能世界,在每个可能世界上计算有穷的最短距离,最后计算出平均值作为期望最短距离的估计值.为提高计算效率,使用了过滤条件来减少采样过程中采样的边数从而加快随机采样.在此基础上,提出了一种基于对称变量的、无偏的随机采样近似算法,并证明了与直接随机采样方法相比,该方法在不增加时间开销的同时能减小采样方差.通过真实数据上的实验表明,提出的算法在时间开销和采样方差上均明显好于直接随机采样方法.

著录项

来源
《第29届中国数据库学术会议》|2012年|2208-2220|共13页
会议地点合肥
作者
Li Mingpeng; 李鸣鹏; Zou Zhaonian; 邹兆年; Gao Hong; 高宏; Zhao Zhengli; 赵正理;
展开▼
作者单位

中国计算机学会;

展开▼
会议组织
正文语种
原文格式 PDF
中图分类 TP311.131;
关键词
不确定图; 最短距离; 随机采样技术; 计算方法;

相似文献

中文文献
外文文献
专利

1. 不确定图上期望最短距离的计算 [J] . 李鸣鹏 ,邹兆年 ,高宏 . 计算机研究与发展 . 2012,第010期
2. 一种高效的不确定图上k步可达查询处理算法 [J] . 仲悦 ,杜明 ,周军锋 . 新一代信息技术 . 2021,第005期
3. 一种高效的不确定图上k步可达查询处理算法 [J] . 仲悦 ,杜明 ,周军锋 . 新一代信息技术 . 2021,第005期
4. 不确定图上Top-k最大影响力边查询算法 [J] . 胡阳 ,黄金晶 ,刘光富 . 计算机工程 . 2018,第011期
5. 一种基于MapReduce的不确定图上的相似性连接方法 [J] . 缪丰羽 ,王宏志 ,阮群生 . 计算机科学 . 2018,第012期
6. 基于点云间最短距离“中位值”的变形计算 [C] . 徐进军 ,覃邵峰 ,韩达光 . 中国测绘地理信息学会2014工程测量分会与矿山测量专委会年会暨全国变形与安全监测学术研讨会 . 2014
7. 不确定图上期望最短距离的研究与应用 [A] . 李鸣鹏 . 2012

不确定图上期望最短距离的计算

摘要

著录项

相似文献

相关主题

期刊订阅