文档介绍：沈阳建筑大学
硕士学位论文
空间数据库中GRkNN查询研究
姓名:于程程
申请学位级别:硕士
专业:计算机应用技术
指导教师:宋晓宇
2011-02
硕士研究生学位论文摘要 I
摘要
卫星遥控、传感器网络等空间信息获取技术的快速发展推动了地理信息系统、空间设
施布局选址的应用。由于空间数据量庞大,结构复杂,查询处理代价昂贵,空间数据查询
必将成为以上应用的研究重点和难点。
反 k 最近邻(Reverse k-Nearest-Neighbors , RkNN) 查询是在 k 最近邻
(k-Nearest-Neighbors,kNN) 查询问题的基础上产生的,获得将查询对象作为 kNN 的数据
对象集合。RkNN 查询用于评价一个站点位置对周围环境的影响,可应用于建筑选址、设
施评价等应用。例如超市连锁公司想在某一地点设立一个新超市,这必然会对附近的超市
或商场(假设人们一般选择就近购物)带来影响,所设地点的 RkNN 结果可以作为评价其
影响力的依据。
现有的RkNN查询均针对单个查询点进行处理。考虑一个实际情况,用户需要查询一
个商业区或一个连锁店(由一组空间对象组成)的RkNN结果。针对这一应用需求,本文提出
一种新的针对空间数据库的RkNN查询—— GRkNN查询(Group RkNN,GRkNN),该查询可
以用于评价一组对象的影响。解决该问题的直接方法是计算单个查询对象的RkNN,再求
出所有查询结果的并集,即为查询点集合的RkNN结果。显然,当组内对象较多时,由于
未能利用组内对象的紧邻关系进行查询,查询效率会较差。
本文采用过滤-提纯的框架模型,过滤阶段,计算包含所有查询点的最小覆盖圆,以
该圆为整体结合一组数据集子集来计算该组查询点 RkNN 的搜索区域,在这个查询区域
的所有对象都是该 GRkNN 查询的候选集,而计算这个搜索区域的算法是 CINCH(Circle
INtersections' Convex Hull);提纯阶段,结合 Range-k 验证法来去除非 GRkNN 查询结果
的候选者,从而最终得到查询结果。利用真实数据集对算法进行充分测试,实验结果表明
提出的算法的效率在查询点集合是一组邻近的空间对象时优于直接算法。
最后,将 GRkNN 查询应用到“十一五”国家科技支撑计划课题“村镇工程基础设施
数据库与评价模拟系统研究(2006BAJ11B07-01)”中,在系统中实现了 GRkNN 查询算法,
并完成了基于 GRkNN 查询的基础设施的影响力评价,解决了基础设施网络优化选址问
题。通过实际应用系统验证了所提出的 GRkNN 查询算法的有效性和实用性。

关键词:反 k 最近邻;GRkNN 查询;R 树;最小覆盖圆
Abstract 硕士研究生学位论文
Abstract
The rapid development of spatial information retrival and processing technology, such as
telecontrol systems for satellites, works and so on, has impelled the applications of
geographic information system (GIS) and spaitial facility location. The size immensity and
plexity of spatial data result in the high cost of query processing. Thus the spatial
data query es a significant and difficult problem.
Reverse k-Nearest-Neighbor (RkNN) query is proposed based on the k-Nearest-Neighbor
(kNN) query, which finds objects that take the query object as one of their kNN. RkNN query
can be applied to evaluate a site influence in the surrounding environment. For example, a
supermarket pany wants to make a good location for a new super