Computer Engineering and Applications计算机工程与应用2011,47(10)
1 引言
空间数据库是近年的热点研究邻域,是一门非常前沿的
交叉学科,它在地理信息系统、计算机辅助设计、多媒体信息
系统以及数据仓库技术等诸多邻域中都起着非常重要的作
用。与传统文件方式相比,空间数据库技术有明显的技术优
势,包括海量数据管理能力、图形和属性数据一体化存储、多
用户并发访问、完善的访问权限控制和数据安全机制等。空
间数据库技术正在取代传统文件,成为越来越多的大中型空
间数据库应用系统的空间数据存储和查询的解决方案。
反向最近邻(RNN)
[1]
查询是空间数据库中最重要的算法
之一,是在最近邻查询的基础上提出的一种新的查询类型。
反向最近邻查询是人们在现实生活中经常遇到的一种查询,
例如:一家百货商店新开张,这必然会影响到周围同类的商
店,而受影响最大的就是其反向最近邻查询的结果。移动对
象的反向最近邻查询在实际应用中充当了重要的角色,它被
应用于决策支持系统、数据流、文件数据库和生物信息技术等
领域,并激发了一类新的应用系统,如军事指挥系统、智能运
输系统以及自动导航系统等。
移动对象的反向最近邻查询最早是由 Kron F 和 Muth-
ukrishnan S 提出的
[1]
,近年来,相应的研究机构投入了大量的
人力和物力来从事该领域的研究。目前在反向最近邻查询问
题的研究中,国外已经提出了几种处理模型和相应的算法,进
行了大量的模拟分析和评测工作,结合理论和实践,积累了较
多的经验。国外的研究主要集中在数据集是动态的情况下的
反向最近邻查询,方法主要有:YuFei Tao 提出的数据点集是
动态情况的反向最近邻查询方法
[2]
;Korn 提出基于数据流的反
向最近邻问题的研究,并给出了反向最近邻聚集的概念,通过
它可以形式化地探索和研究基于数据流的反向最近邻问题
[3]
;
Stanoi 用到了空间修剪方法
[4]
;Benetis 将 TPR-tree 作为底层的
索引结构
[5]
,TPR-tree 引入了时间参数,可以查询在某时间片段
内的移动对象的最近邻和反向最近邻。除了以上的反向最近
邻查询方法外,还提出了大图中的反向最近邻查询问题、连续
的反向最近邻查询问题和在特定维上进行反向最近邻查询。
而国内,对移动对象的反向最近邻查询问题的研究还刚刚起
步,目前只有少量的相关论文发表。哈尔滨理工大学的郝忠
孝教授带领的研究小组对反向最近邻查询问题作了专门研
究,并发表了一系列论文,提出了对半平面修剪策略的改进方
法,构建了新的时空索引结构
—
—TPR
DNN
-tree 和 SRdnn-tree,
移动对象反向最近邻查询处理技术研究进展
曹泽文,谭川豫,王晓辉
CAO Zewen,TAN Chuanyu,WANG Xiaohui
国防科技大学 C4ISR 技术国防科技重点实验室,长沙 410073
Key Lab of C4ISR Technology National Defense Sci. and Tech.,National University of Defense Technology,Changsha 410073,China
CAO Zewen,TAN Chuanyu,WANG Xiaohui.Review on techniques for reverse nearest neighbor query processing of
moving objects.Computer Engineering and Applications,2011,47(10):138-141.
Abstract:With the rapid development o f wireless communica tion tech nology and advances in personal mobile communi-
cation terminals,mobile computing technology has a more broad application background,especially,the Reverse Nearest Neighbor
(RNN) query processing technologies are gaining researchers’widespread concerns.This paper studies the methods of RNN
query in recent years.And based on the process of query processing,this paper sorts RNN query techniques into pretreatment
based methods and space pruning based methods.The effective solutions and new development are concluded,and finally the
future directions about the techniques for RNN query processing of moving objects are pointed out.
Key words:moving objects;Reverse Nearest Neighbor(RNN) query;pretreatment;space pruning
摘 要:随着移动通信技术的快速发展和个人移动通信终端功能的不断完善,移动计算技术有了更加广阔的应用背景,尤其是移
动对象的反向最近邻查询处理技术得到了研究人员的广泛关注。对近几年提出的移动对象反向最近邻查询方法进行了研究,根
据其查询处理过程,将反向最近邻查询方法分为基于预处理的方法和基于空间修剪的方法;总结了近年来提出的有效解决方法
和研究进展,最后介绍了移动对象反向最近邻查询处理技术的最新发展趋势。
关键词:移动对象;反向最近邻查询;预处理;空间修剪
DOI:10.3778/j.issn.1002-8331.2011.10.039 文章编号:1002-8331(2011)10-0138-04 文献标识码:A 中图分类号:TP311.131
基金项目:国家自然科学基金(the National Natural Science Foundation of China under Grant No.70771110)。
作者简介:曹泽文(1967—),男,博士,副教授,研究领域为信息综合处理与辅助决策;谭川豫(1986—),男,硕士研究生;王晓辉(1984—),男,硕士
研究生。E-mail:tanchuanyu66@126.com
收稿日期:2009-09-30;修回日期:2009-12-15
138