一种改进的基于道路网络距离的K近邻查询算法

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

一种改进的基于道路网络距离的K近邻查询算法

肖晖, 杨必胜

文章导航 > 武汉大学学报 ● 信息科学版 > 2008 > 33(4): 437-439

肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法[J]. 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.

引用本文:

肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法[J]. 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.

XIAO Hui, YANG Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 437-439.

Citation:

XIAO Hui, YANG Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 437-439.

一种改进的基于道路网络距离的K近邻查询算法

肖晖^1,2,
杨必胜¹

¹武汉大学交通研究中心,武汉市珞喻路129号430079;²武汉大学遥感信息工程学院,武汉市珞喻路129号,430079

基金项目: 国家973计划资助项目(2006CB705500)

作者简介:
肖晖,博士生,从事移动对象数据库研究及移动GIS研究。

中图分类号: P208

An Improved KNN Search Algorithm Based on Road Network Distance

XIAO Hui^1,2,
YANG Bisheng¹

¹Transportation Research Center,Wuhan University,129 Luoyu Road,Wuhan 430079,China;²Institute of Remote Sensing and Information Engineering,Wuhan University,129 Luoyu Road,Wuhan 430079,China

Funds: 国家973计划资助项目(2006CB705500)

摘要: 研究了空间网络数据库中的K近邻查询,提出了一种新的基于道路网络距离的KNN查询算法。这种方法以已有的道路网络模型框架为基础,通过预计算NN表,减少了昂贵的最短路径计算,利用两个链表记录已访问弧段的信息,避免了不必要的磁盘I/Os,从而有效地提高了算法效率。实验结果表明,在目标点分布比较密集的情况下,本算法明显优于其他算法。
- 空间网络数据库 /
- KNN查询 /
- 道路网络
Abstract: In this paper we investigate K nearest neighbor searches in spatial network databases.A new algorithm for KNN queries is proposed.Based on the road network architecture proposed by Papadias et al.,we incorporate the precomputed NN lists into the algorithm for decreasing expensive calculation of the shortest path,and record the information of visited edges in the two lists for avoiding unnecessary disk I/Os.Experiments show that the algorithm outperforms other algorithms in high object density.
- spatial network databases /
- K nearest neighbor queries /
- road network

[1]	马京振, 孙群, 温伯威, 周炤, 陆川伟, 吕峥, 孙士杰. 结合轨迹数据的混合多特征道路网选取方法 . 武汉大学学报 ● 信息科学版, 2022, 47(7): 1009-1016. doi: 10.13203/j.whugis20190480
[2]	蔡先华, 刘凯丽, 胡卓良, 张远. 利用街区面块拓扑构建道路网络的算法 . 武汉大学学报 ● 信息科学版, 2021, 46(8): 1170-1177. doi: 10.13203/j.whugis20190348
[3]	田晶, 方华强, 刘佳佳, 赵风, 任畅. 运用复杂网络方法分析城市道路网的鲁棒性 . 武汉大学学报 ● 信息科学版, 2019, 44(5): 771-777. doi: 10.13203/j.whugis20150334
[4]	王腾, 王艳东, 赵晓明, 付小康, 蒋波涛. 顾及道路网约束的商业设施空间点模式分析 . 武汉大学学报 ● 信息科学版, 2018, 43(11): 1746-1752. doi: 10.13203/j.whugis20160558
[5]	田晶, 余梦婷, 任畅, 熊富全. 城市道路网元胞模式分析的网络景观指数分析法 . 武汉大学学报 ● 信息科学版, 2018, 43(10): 1588-1594. doi: 10.13203/j.whugis20150640
[6]	卢宾宾, 杨欢, 孙华波, 于清德. 利用Minkowski距离逼近道路网络距离算法研究 . 武汉大学学报 ● 信息科学版, 2017, 42(10): 1373-1380. doi: 10.13203/j.whugis20160225
[7]	田晶, 武晓环, 林镠鹏, 任畅. 城市道路网的度相关性及其与网络鲁棒性的关系研究 . 武汉大学学报 ● 信息科学版, 2016, 41(5): 672-678. doi: 10.13203/j.whugis20150046
[8]	张朋东, 石岩, 邓敏, 赵玲. 基于拓扑强度的城市道路网络层次表达 . 武汉大学学报 ● 信息科学版, 2016, 41(2): 178-183,213. doi: 10.13203/j.whugis20130798
[9]	李清泉, 曾喆, 杨必胜, 李必军. 城市道路网络的中介中心性分析 . 武汉大学学报 ● 信息科学版, 2010, 35(1): 37-41.
[10]	董明, 张海涛, 祝晓坤, 陈春希. 基于遥感影像的地图道路网数据变化检测研究 . 武汉大学学报 ● 信息科学版, 2009, 34(2): 178-182.
[11]	陈志荣, 刘仁义, 徐财江, 刘南. 一种面向网络发布的海洋遥感数据库引擎 . 武汉大学学报 ● 信息科学版, 2007, 32(12): 1107-1110.
[12]	朱庆, 李渊. 道路网络模型研究综述 . 武汉大学学报 ● 信息科学版, 2007, 32(6): 471-476.
[13]	李雪飞, 傅佩红, 刘经南. 一种基于道路网络的时空索引 . 武汉大学学报 ● 信息科学版, 2006, 31(7): 620-623.
[14]	廖楚江, 蔡忠亮, 杜清运, 王长耀. 基于最少换乘的公交最优路径算法的设计与实现 . 武汉大学学报 ● 信息科学版, 2006, 31(10): 904-907.
[15]	翁敏, 毋河海, 杜清运, 李林燕. 基于道路网络知识的启发式层次路径寻找算法 . 武汉大学学报 ● 信息科学版, 2006, 31(4): 360-363.
[16]	黎展荣, 杨如军, 周新忠. 关系数据库管理空间数据的方式下数据查询方法的研究 . 武汉大学学报 ● 信息科学版, 2005, 30(12): 1104-1106.
[17]	王永尚. 国家大地测量数据库网络化建设 . 武汉大学学报 ● 信息科学版, 2003, 28(S1): 41-43,47.
[18]	王密, 郭丙轩, 李德仁, 龚健雅. 多传感器与道路网数据用于汽车导航的研究 . 武汉大学学报 ● 信息科学版, 2001, 26(3): 205-208.
[19]	李霖. 空间数据库查询语言的特征 . 武汉大学学报 ● 信息科学版, 1997, 22(2): 107-110.
[20]	李杰文, 康朝贵. 一种基于时空棱柱的乘车行程可拼性判断模型 . 武汉大学学报 ● 信息科学版, 0, 0(0): -. doi: 10.13203/j.whugis20210633

WeChat

点击查看大图

计量

文章访问数: 540
HTML全文浏览量: 28
PDF下载量: 402
被引次数: 0

一种改进的基于道路网络距离的K近邻查询算法

肖晖^1,2,
杨必胜¹

¹武汉大学交通研究中心,武汉市珞喻路129号430079;²武汉大学遥感信息工程学院,武汉市珞喻路129号,430079

基金项目: 国家973计划资助项目(2006CB705500)

作者简介:
肖晖,博士生,从事移动对象数据库研究及移动GIS研究。

收稿日期: 2008-02-26
修回日期: 2008-02-26
刊出日期: 2008-04-05

中图分类号: P208

关键词:

空间网络数据库 /

摘要: 研究了空间网络数据库中的K近邻查询,提出了一种新的基于道路网络距离的KNN查询算法。这种方法以已有的道路网络模型框架为基础,通过预计算NN表,减少了昂贵的最短路径计算,利用两个链表记录已访问弧段的信息,避免了不必要的磁盘I/Os,从而有效地提高了算法效率。实验结果表明,在目标点分布比较密集的情况下,本算法明显优于其他算法。

English Abstract

肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法[J]. 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.

引用本文:

肖晖, 杨必胜. 一种改进的基于道路网络距离的K近邻查询算法[J]. 武汉大学学报 ● 信息科学版, 2008, 33(4): 437-439.

XIAO Hui, YANG Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 437-439.

Citation:

XIAO Hui, YANG Bisheng. An Improved KNN Search Algorithm Based on Road Network Distance[J]. Geomatics and Information Science of Wuhan University, 2008, 33(4): 437-439.

全文HTML

/

下载: 全尺寸图片幻灯片

分享

用微信扫码二维码

分享至好友和朋友圈

返回

我要投稿

投稿攻略

联系我们

二维码