空间数据库分类查询算法研究与实现

摘要： 空间数据库是指地理信息系统在计算机物理存储介质上存储的与应用相关的地理空间数据的总和。由于传统的查询方法效率低，查询信息单一，如何在庞大的数据中快速有效地挖掘出有特定意义的信息是空间数据查询研究的一个重要方面。为了更深入的挖掘空间数据库的信息，进行的空间数据查询使用了范围查询，K最近邻算法查询，反最近邻查询算法的优化和实现对大量已分类的空间数据进行查询。使用反最近邻查询算法得到的结果是在所有属于一类点的集合中，把某一位置作为离其最近的地点的点的集合，并用数据实验对算法进行了验证，利用算法帮助用户对大量空间数据进行分类查询，完成了最优查询的可行性。

关键词：空间数据库; K最近邻算法;反最近邻查询算法

0 引言

计算机技术和数据收集技术的飞速发展，使人们可以从更加广阔的范围和难以想象的速度收集与存储信息，希望能够对其进行更高层次的分析，以便更好地利用这些数据。由于空间数据库的数据量庞大，具有高可访问性、模型复杂和属性数据与空间数据联合管理等特点。导致了用户对丰富数据资源不能对其进行有效地利用。空间数据库技术已经代替传统的文件管理方式，逐步成为空间数据管理的主流技术。如今基于空间数据库的研究已成为计算机科技领域中应用研究技术内容最丰富的分支之一。如何在庞大的数据中挖掘出有特定意义的信息是空间数据研究的一个重要方面。

在Visual C++6.0环境下分别使用范围查询、K最临近分类算法查询、反临近查询（RNN）算法对处理过的数据进行查询。范围查询是在一个已知的点周围一定范围内找到某类型的点。K最临近分类算法是找出整个数据集中距离已知点最小的几个数据点。反近邻查询算法则是找出某个数据集中以已知点为最邻近点的地点。

1 经典查询算法

1.1范围查询算法。

指定空间中某一点和一个范围，在空间特征对象的图层中以指定点为中心，以设定的范围为半径，而在范围之内的点为结果。四方形a为指定的点，以该点位中心，一定范围为半径，落入该范围内的图中显示的圆内的点即为该范围查询的结果。

1.2 最近邻查询算法。

最近邻查询问题是由Kunth在1973年提出来的，即邮局问题。它可以描述为：给定N维空间内的n个点所组成的集合S，将这n个点存储在一种数据结构中，使得对于空间内的任何查询点q，都可以有效地找到大的最近邻，即在S中找到一个点p，是起到q的距离最近。最邻近的数目可以是一个，也可以是多个即KNN。K最近邻算法（KNN）：圆要被决定赋予哪个类，是三角形还是四方形？如果K=3，由于三角形所占比例为2/3，圆a将被赋予三角形那个类，如果K=5，由于四方形比例为3/5，因此圆a被赋予四方形类。

1.3 反最近邻查询算法

对于数据及S和查询点q，预先计算出数据集S中每个点p的最近邻，而后，使每个点与一个邻接圆（vicinity circle）相对应，再进一步建立这些圆的R-树索引结构，称其为RNN-树，应用这种索引结构，可以很容易求得q的最近邻。但由于RNN-树的建立目的在于反最近邻查询，而非最近邻查询，因此，Flip Korn和S.Muthukrishnan不得不建立另外的R-树来进行最近邻查询和其他空间查询[1]。

反最近邻算法（Reverse Nearest Neighbor，RNN），要判断哪些圆形和三角形将中间四方形认为是距离自己最近的四方形。先在所有圆形，三角形中求出距离自己最近的四方形，对于那些将中间四方形认为是距离自己最近的四方形的图形即为该反最近邻算法的结果。

2.算法的设计与实现

2.1范围查询。

范围查询算法实现首先获得用户所选择的空间特征对象所在的图层，并使用了MapX中CMapXLayer类的SearchWithinDistance函数。该函数专门用来对已知地点为中心，已知距离为半径，确定图层进行范围查询。将查询到的图元集合在新建的MapX图层中进行显示。

2.2最近邻查询算法实现。

首先新建立的数据结构CMFeature类的数组对象。将特征对象即图元集合分离出来。计算此图元集合中每一个图元与已知点的距离，将这个距离按插入排序到CMFeature类的数组中。如果这个图元按距离计算可以插入到上述数组中，那么将这个图元和它距离已知点的距离插入到数组中。

当所有图元集合都完成上述操作后，将CMFeature类的数组中的图元显示到地图中。

2.3反最邻近查询算法实现。

首先将特征对象即图元集合分离出来。根据定理以“我的位置”点为其所在平面的原点，以该点的水平线为线L1，依次将地图划分S1，S2，…S6六个区域。分别计算落入每个区域图元集合中距离已知点最近的那个图元并将该图元存入新建立的数据结构CMRnnFeature类的对象数组中。该数组中最多有6个对象。再分别以这6个对象的图元为中心点，在满足“位置点性质”特征的图元集合中找到它的KNN，如果它的KNN刚好是“我的位置”这个图元，那么把它加入到新的图层中并显示到地图上。

3 结语

空间数据库技术是地理信息系统数据组织的核心技术，也是地理科学、测绘科学、计算机科学和信息科学相结合的产物。空间数据库技术已经代替传统的文件管理方式，逐步成为空间数据管理的主流技术。但是由于空间数据库数据量大，导致了用户拥有丰富数据资源却不能对其进行有效地利用。实现了传统的输入地点名称在地图上进行查询，而且对所有地图数据按其性质对其分类。用户在分好类的地图中可以输入范围进行查询，可以查询地图中离我最近的某类的地点，还可以使用本系统对选址进行决策。

参考文献

[1]Liao Haojun，Han Jizhong，Fang Jinyun.All-Nearest-Neighbor Queries Processing in Spatial Databases.Journal of computer research and development，2011，48（1）：17～22.

作者簡介：许崇 女，1982年出生，实验师，就职于沈阳建筑大学