路网环境下的最近邻查询技术-鲍金玲 , 王斌 , 杨晓春 , 朱怀杰.pdf

上善若水

21页

0次

2022-05-19

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2018,29(3):642−662 [doi: 10.13328/j.cnki.jos.005442] http://www.jos.org.cn

路网环境下的最近邻查询技术

∗

鲍金玲

1,2

王

斌

杨晓春

朱怀杰

(东北大学计算机科学与工程学院,辽宁沈阳 110169)

(白城师范学院计算机科学学院,吉林白城 137000)

通讯作者: 杨晓春, E-mail: yangxc@mail.neu.edu.cn

摘要: 最近邻查询作为基于位置服务的重要支持性技术之一,引起了众多学者的广泛关注和深入研究.相对于

欧式空间而言,路网环境下的最近邻查询更贴近人们的生活,有着更重要的研究意义.路网环境下庞大的数据量和复

杂的数据结构,使得最近邻查询的操作代价变得非常昂贵,如何有效地提高查询效率,是研究者面临的主要挑战.对

路网环境下的最近邻查询技术进行综述,分别从最近邻查询采用的索引结构和查询处理过程对现有路网环境下的

最近邻查询方法进行了分析和比较,也介绍了路网环境下最近邻的变体查询技术的研究情况,最后探讨路网上最近

邻查询技术未来的研究重点.

关键词: 基于位置的服务;路网;最近邻查询;欧式距离;路网距离

中图法分类号: TP311

中文引用格式: 鲍金玲,王斌,杨晓春,朱怀杰.路网环境下的最近邻查询技术.软件学报,2018,29(3):642−662. http://www.jos.

org.cn/1000-9825/5442.htm

英文引用格式: Bao JL, Wang B, Yang XC, Zhu HJ. Nearest neighbor query in road networks. Ruan Jian Xue Bao/ Journal of

Software, 2018,29(3):642−662 (in Chinese). http://www.jos.org.cn/1000-9825/5442.htm

Nearest Neighbor Query in Road Networks

BAO Jin-Ling

1,2

, WANG Bin

, YANG Xiao-Chun

, ZHU Huai-Jie

(School of Computer Science and Engineering, Northeastern University, Shenyang 110169, China)

(School of Computer Science, Baicheng Normal College, Baicheng 137000, China)

Abstra ct : Nearest neighbor query, as one of the building blocks of location-based service, has become a hot research topic in recent

years. Compared with Euclidean space, road network is a more practical model in real applications; hence, nearest neighbor query in road

network has received broader research efforts. In road network, tremendous data are generated along with sophisticated data structure,

making nearest neighbor query computationally expensive. This poses a major challenge to spatial database community on its effort to

effectively improve the query processing efficiency for nearest neighbor query. This work summarizes existing nearest neighbor query

techniques in road network, and conducts analysis and comparison among them, from various perspectives including indexing structure

and algorithm implementation. Additionally, several variants of nearest neighbor query are also summarized in this work. Finally, future

research focus and trend for nearest neighbor query in road network are discussed.

Key words: location-based service; road network; nearest neighbor query; Euclidean distance; road network distance

∗ 基金项目: 国家自然科学基金(61532021, 61572122); 中央高校基本科研业务费专项资金(N161606002); 辽宁省“百千万人才

工程”经费

Foundation item: National Natural Science Foundation of China (61532021, 61572122); Fundamental Research Funds for the

Central Universities (N161606002); Liaoning BaiQianWan Talents Program

本文由基于图结构的大数据分析与管理技术专刊特约编辑林学民教授、杜小勇教授、李翠平教授推荐.

收稿时间: 2017-07-31; 修改时间: 2017-09-05; 采用时间: 2017-11-07; jos 在线出版时间: 2017-12-05

CNKI 网络优先出版: 2017-12-06 15:23:23, http://kns.cnki.net/kcms/detail/11.2560.TP.20171206.1522.007.html

鲍金玲等:路网环境下的最近邻查询技术

643

随着无线技术的高速发展和移动通信设备的不断普及,基于位置的服务(location-based service,简称 LBS)

得到了广泛的应用.其中的最近邻(nearest neighbor,简称 NN)查询作为基于位置服务中最重要的支持性技术之

一,引起了学者们的广泛关注.

NN 查询问题起源于 Knuth 在 1973 年提出的邮局问题

[1]

.该问题可以简单地描述为:已知 N 维空间中集合 P

包含 n 个数据点,在集合 P 中找出一个数据点 p,使得 p 到查询点 q 的距离最近.而 k(k≥1)NN 查询是 NN 查询

的一般化形式.如果数据对象子集 NN(q)中仅含有一个对象,则该查询是 NN 查询;如果数据对象子集 NN(q)中含

有 k(k>1)个对象,则是 kNN 查询.

目前,对于 NN 查询的研究主要基于欧式空间和路网环境.欧式空间中的 NN查询问题的研究已趋成熟

[2−13]

现有方法大多采用 R-tree 索引结构,基于分支界定策略的剪枝技术缩小查询空间.其中的 DF(depth-first)算法

[2]

和 BF 算法(best-first)算法

[4]

是欧式空间 NN 查询技术中的经典算法,为其他 NN 查询技术奠定了一定的理论基

础.然而,欧式空间的 NN 查询是理想情况下的研究,在欧式空间,两点之间的距离指直线距离,这一距离仅仅取决

于两点的坐标值,而且对象可以处在空间的任何位置.相比较而言,路网环境下 NN 查询的应用更贴近人们的生

活,这方面的研究也有着更重要的意义.但在路网环境中,对象的位置和运动都被约束在网络上,对象之间的距

离受限于它所处的网络,由路网的连通性决定(如公路交通网等).这就导致路网环境下的 NN 查询空间检索范围

更广,路径计算量更大.因此,欧式空间中的解决方法是不能通过简单的修改就应用于路网环境的.

路网环境下庞大的数据量和复杂的数据结构给 NN 查询带来了极大的挑战,主要体现在以下两个方面.

(1) 有效的剪枝策略.由于搜索空间较大,NN 查询处理的关键在于剪枝效果.如何构造有效的索引结构和

高效的剪枝策略是关键,也是研究的难点.空间索引结构的不断改进在一定程度上提高了对空间数据

的处理能力,但是由于空间数据的特殊性,空间索引结构仍无法彻底改变高维数据所带来的束缚.每

种索引结构都有自己的优缺点,要想找到一种能够适应各种空间数据类型的索引结构是非常困难的;

(2) 可伸缩性.不同区域的路网规模不同,对象分布密度不同,用户查询的 k 值也会不停地变化,路网本身也

会时时更新,一个好的查询方法要具有很强的伸缩性,更好地适应这些变化.

目前,许多大学和研究机构已经对路网环境下的 NN 查询展开了深入的研究,如南加州大学

[14]

、马里兰大

学

[15,16]

和宾西法尼亚州立大学

[17]

、奥尔堡大学

[18−20]

、香港科技大学

[21]

、香港大学

[22,23]

和清华大学

[24]

等.路网

环境下的 NN 查询技术的研究取得了许多有价值的研究成果,然而目前缺少对这些研究成果的归纳和总结.文

献[25]中对路网环境下的最近邻查询技术进行了分析和比较,不过涉及到的只有 5 种比较典型的最近邻查询方

法:INE

[21]

,IER(incremental euclidean restriction)

[21]

,DisBrw

[16]

,ROAD

[23]

和 G-tree

[24]

方法.因此,本文主要对路网

环境下的 NN 查询技术进行综述.

本文着重讨论路网环境中的 NN 查询技术,分别从路网数据模型、索引结构和查询过程等方面阐述路网环

境下的 NN 查询技术的研究进展.第 1 节介绍路网数据的存储模式.第 2 节介绍查询的处理过程,研究路网环境

下主要的 NN 查询技术,并对现有常用的 NN 查询技术进行分析和比较.第 3 节探讨 NN 查询的变体查询技术的

研究情况.第 4 节总结全文并展望未来的研究重点.

1 路网数据模型

路网数据模型的建立不仅能够真实地描述道路网络的特性,而且还支持各种基于路网环境的查询研究,而

掌握路网数据的一些特有性质,是构建路网数据模型和完成查询处理的关键.

1.1 路网数据的特征

普通意义上的数据具有选择性、可靠性、时间性、完备性、详细性和综合性等特点,而路网数据作为一种

特殊的空间数据,除了具有一般数据的全部特征以外,还有一些区别于一般数据的特征

[26]

,主要表现在以下几个

方面.

(1) 数据结构的复杂性和多样性.对于路网数据来说,对象的信息不但包含其位置信息,还包含对象之间

的拓扑结构信息,因此在存储的过程中,需要根据具体情况选择合适的数据结构.这就导致存储路网

of 21

免费下载

软件学报计算机技术

关注

评论