障碍物环境下的动态单纯型连续近邻链查询

李 松，张丽平，刘 艳，郝晓红，杨和禹

(哈尔滨理工大学a.计算机科学与技术学院;b.计算中心，哈尔滨 150080)

1 概述

数据集中的近邻查询问题在空间数据库、海量数据查询与分析、大数据处理、数据挖掘、图像处理和交通控制等领域具有重要的研究意义。国内外学者对近邻查询问题进行了广泛研究，在简单最近邻、反向最近邻、组最近邻、线段最近邻和最近对查询等方面取得了一些重要研究成果［1］。

近年来，由于数据量的显著增长和实际应用的需要，数据集中的近邻查询及其变种问题成为研究的热点。国内外的研究进一步拓展到移动查询点的最近邻查询［2］、道路网中的连续最近邻查询［3-4］、连续集合最近邻查询［5］、不确定数据集中的受限最近邻查询［6］、可视最近邻查询［7］、可视反向最近邻查询［8］、高维数据近似最近邻查询［9］、不确定数据集的概率频繁最近邻查询［10］、基于Voronoi 图的反向最近邻查询［11］等方面。所取得的成果解决了最近邻查询领域的一系列重要问题。

作为最近邻查询领域的一个变种问题，单纯型连续近邻链(Simple Continues Near Neighbor Chain，SCNNC)查询在空间数据挖掘、数据相似性分析和智能推理等领域具有较大的作用。已有的研究成果［2-11］无法有效地查询单纯型连续近邻链，为处理单纯型连续近邻链问题，文献［12］基于计算几何中的Voronoi 图对数据集中单纯型连续近邻链问题进行了研究，提出了一种查询数据集中单纯型连续近邻链的方法。文献［13］基于空间索引结构R 树给出了动态数据集中的单纯型连续近邻链查询的算法:SCNNC_R_ST 算法，SCNNC_R_SD 算法和SCNNC_R_XZ 算法。为处理预定数据链规模的单纯型连续近邻链问题，文献［14］基于空间Hilbert 曲线给出了查询算法和更新算法。但文献［12-14］的研究成果主要适用于无障碍环境下的单纯型连续近邻链查询，不适合处理存在空间障碍物情况下的近邻链查询问题。由于在现实中空间障碍物的存在较为常见，并且空间数据集往往不是恒定不变的，随时间和应用的变化，空间数据集经常动态地增加或减少。因此研究障碍物环境下的动态数据集的单纯型连续近邻链的查询具有一定的实际意义。针对已有方法的不足，本文对障碍物环境下的动态数据集的单纯型连续近邻链的查询方法进行研究。

2 基本定义

为了研究障碍物环境下的动态数据集合中的单纯型连续近邻链查询方法，本节首先给出文中所需的基本定义。

定义1 最近邻查询［1］

假设有一d 维空间的点集W 和一个查询点q，最近邻查询就是找出子集NN(q，W):NN(q，W)={w∈W|∀v∈W:D(q，w)≤D(q，v)}。若要找出w 个最近邻，该定义则可扩展成w 个最近邻的查询，即:wNN(q，W)={v1，v2，…，vw}，其中，∀v∈W -wNN(q，W)，w∈wNN(q，W)且D(q，w)≤D(q，v);D(vi，q)≤D(vj，q)，1≤i ＜j≤w。

在定义1 中，D(q，w)和D(q，v)等表示2 个数据点之间的距离。在不强调数据集的情况下，NN(q，W)也可简写为NN(q)，表示q 的最近邻。

基于定义1，下面给出单纯型连续近邻链查询的形式化定义。

定义2 单纯型连续近邻链查询［12］

设有一d 维空间中的数据点集V，V 中一组有序数据点的集合记为CL，CL={vm，vm+1，vm+2，…，vn-1，vn}。其中，vi+1∈NN(vi)(或vi+1∉NN(vi)且vi+1∈wNN(vi))，i=m，m+1，…，n-1，称CL 为V 集中的一条连续近邻链，vm称为链首点，vn称为链尾点。若CL 满足以下条件，则称CL 为单纯型连续近邻链:

(1)∀vi，vj∈CL，若i≠j，则有vi≠vj;

(2)∀vi，vj∈CL，若vi+1≠vj+1，则有vi≠vj;

(3)∀vi∈CL，vi+1∉{vm，…，vi};

(4)∀vi∈CL，若vi+1∉NN(vi)且vi+1∈wNN(vi)，则有(w-1)NN(vi)⊆{vm，…，vi}。

在数据集V 中查找一条单纯型连续近邻链的查询称为单纯型连续近邻链查询，简记为SCNNCquery。

如图1 所示，{v1，v2，v3，v4，v5，v6，v7，v8，v9，v10，v11，v12，v13，v14，v15}即是1 条以v1为链首点，v15为链尾点，共包含15 个数据点的单纯型连续近邻链。

图1 单纯型连续近邻链和空间障碍线

定义3 前驱点/后继点

在单纯型连续近邻链CL 中，设前后有序的相邻2 个数据点为vi和vj，则称vi是vj的链内直接前驱点，vj是vi的链内直接后继点。本文用PRE(vj)表示vj的链内直接前驱点，ACE(vj)表示vj的链内直接后继点。对于CL 中的一个数据点vi，本文称在CL中排序在vi之前的数据点集为vi的链内前驱点集，记为QU(vt)，在CL 中排序在vi之后的数据点集为vi的链内后继点集，记为HJ(vt)。

例如，在图1 中，v12的链内直接前驱点为v11，链内直接后继点为v13，HJ(v11)则为{v12，v13，v14，v15}。

定义4 障碍线

本文中，空间内的障碍物被抽象为直线段或曲线段，统称为障碍线，记为TLl(如图1 所示);障碍线的端点称为障碍边缘点，记为h。一条障碍线具有2 个障碍边缘点(如图1 中的h1和h2所示)。对于数据点对(v，w)，设lVw是v，w 间的直线段，若存在TLl，使得lVw∩TLl≠∅且lVw∩TLl∉h，则称数据点v和w 被TLl阻断，表示为OB(TLl，(v，w));否则，称数据点v 和w 未被TLl阻断，表示为┐OB(TLl，(v，w))。

定义5 最短绕障折线

若OB(TLl，(v，w))，称数据点v 和w 之间的最短距离为最短绕障距离，记为MIN_BL(v，w)，v 和w之间的最短绕障距离连线称为最短绕障折线，记为lm，lm∩TLl∈h。如图1 中的折线段v3h2v30。若数据点对(v，w)的绕障折线仅和一条障碍线相关，则称(v，w)被单级阻断。

在本文中，如无特殊说明，v 和其无障环境下的最近邻(NN(v))在有障环境下若被障碍线阻断，则v和NN(v)被单级阻断。

定义6 最近邻判定圆域

设v 和w 之间的最短距离为MIN(v，w)，则以v为圆心，MIN(v，w)为半径生成的圆域称为v 的判定圆域。记为Circle(v，MIN(v，w))。若w 是v 的最近邻，则称该圆域为v 的最近邻判定圆域，记为Circle(v，NN_MIN(v，w))。

如图1 所示，Circle(v8，NN_MIN(v8，v9))即为v8的最近邻判定圆域。

3 障碍物环境下动态单纯型SCNNC 查询

在现实中，空间数据集往往不是静态不变的，而是经常会发生动态变化。本文中，障碍物环境下的动态数据集的动态变化主要分为2 类。第1 类是数据集动态增大;第2 类是数据集动态减少。显然，单纯型连续近邻链查询结果往往会随着数据集的变化而动态改变。本文3.1 节给出了数据集增大情况下的单纯型连续近邻链查询方法;3.2 节给出了数据集减小情况下的单纯型连续近邻链查询方法。

3.1 数据集增大情况下的单纯型连续近邻链查询

由于障碍物环境下的动态数据集中的单纯型连续近邻链的查询是由数据集的某个初始状态开始的。本节首先讨论障碍物环境下的初始静态数据集中的单纯型连续近邻链的一种启发式查询方法(称为OB_STASCNNC_Search 算法)，其主要思想为:由链首点pm 开始调用基于空间索引结构(如空间填充曲线、四叉树等)的最近邻查询算法进行计算，若查询点与其最近邻之间无障阻断，则继续递归进行;如果被阻断，则进行最近邻的二次判断计算，更新部分结果集，递归进行，直到查询出符合要求的近邻链。其中，最近邻的二次判断计算可利用障碍判定圆进行。OB_STASCNNC_Search 算法在无障碍物环境下基于空间索引结构进行单个数据点的最近邻查询的时间复杂度为O(logn)，计算含w 个连续近邻链点的最近邻的复杂度为O(wlogn)，设受障碍物影响的链中近邻点对的个数为m，进行最近邻二次判定的平均计算量为s，则该算法总时间复杂度为O(wlogn+ms)。

当空间数据点动态增加时，障碍物环境下，由链首点vm开始的单纯型连续近邻链的查询变得更为复杂。处理该问题的一个较直接的方法(称为OB_ZJB_UPDATE 方法)即是数据集每次动态更新时，均调用障碍物环境下的静态数据集的单纯型连续近邻链查询算法(如OB_STASCNNC_Search 算法)进行重新计算。该方法操作较为简单，但忽略了新增点vnew对查询的影响细节，对数据集没有进行预先的过滤判断，往往会增加许多冗余计算，在数据量较大时，计算代价较大。为了弥补该方法的不足，本小节着重考虑新增点对初始近邻链的影响情况，对数据集进行有效筛选和过滤，提出了新的算法。

针对新增点vnew，为了利用判定圆域对空间数据集进行筛选和过滤，本节首先给出首位点的概念。

定义7 首位点

以一条单纯型连续近邻链CL 中的各个点(链尾点除外)为圆心，以其到链路内直接后继点的最短距离为半径所生成的圆域集称为链内最近邻判定圆域集。圆域集中的一些圆域互相交叠。本文将新增点vnew所位于的链内最近邻判定圆域所对应的圆心点中在链内相对位置最靠前(即链内序号最小)的数据点称为vnew相对于判定圆域的首位点。

依据单纯型连续近邻链和判定圆的定义与性质可知，在初始单纯型连续近邻链CL 生成的情况下，新增点vnew对CL 的影响情况的分析如下:

(1)若新增点vnew落在CL 链内最近邻判定圆域集之外，则对CL 不产生影响。

(2)若新增点vnew落在CL 的链内最近邻判定圆域集之内，则分2 种情况进一步判断vnew和其在CL中的首位点vt的关系:

1)若vnew和vt之间没有被障碍物阻断，则vnew成为vt新的链内直接后继点;

2)若vnew和vt之间被障碍物阻断，则计算vnew和vt之间的最短绕障距离MIN_BL(vt，vnew)，并和vt及其在CL 中的链内直接后继点ACE(vt)的距离D(vt，ACE(vt))相比较，若MIN_ BL(vt，vnew)大于D(vt，ACE(vt))，则vnew对CL 不产生影响;若MIN_ BL(vt，vnew)小于D(vt，ACE(vt))，则vnew成为vt新的链内直接后继点。若MIN_ BL(vt，vnew)等于D(vt，ACE(vt))，则根据实际需求确定vt的链内直接后继点是否更新。

由以上讨论，可得出障碍物环境下数据集动态增大情况下的单纯型连续近邻链查询算法如算法1所示。

算法1 OB_DYNSCNNC_ADD(V，vm，BL，w，vnew)

输入 空间数据点集V，数据起始点vm，障碍线集BL，待查链的数据点数目w，新增数据点vnew

输出 由链首点vm开始的包含w 个数据对象点的一条更新后的单纯型连续近邻链CL

* 判断新增点vnew和CL 中的数据点的最近邻判定圆域的位置关系;

//确定vnew所在的数据点的最近邻判定圆域集NR

//确定vnew相对于NR 的首位点vt

//更新单纯型连续近邻链CL

//更新单纯型连续近邻链CL

由算法1 的核心步骤可知，该算法初始时调用OB_ STASCNNC_Search 算法生成初始单纯型连续近邻链的时间复杂度为O(wlogn +ms)。根据新增点vnew的空间位置，利用链内最近邻判定圆域确定受影响的链内点vs的平均时间复杂度为O(s')，由vs为链首点开始调用OB_STASCNNC_Search 算法生成部分近邻链的时间复杂度为O(w'logn +m's')，其中，w'是vs之后需要确定的链内数据点的个数;m'是需要二次计算和判断的数据点的个数。该算法核心步骤总的时间复杂度即为O(w+w')logn+ms+m's')。该算法的效率和空间障碍物的数量、空间数据点的数量和受新增点vnew影响的链内点的位置关系较大。

3.2 数据集减小情况下的单纯型连续近邻链查询

数据集的动态变化的另一种情况是数据集的动态减小。与3.1 节的讨论类似，处理该类问题也可用较为直接的方法(OB_ZJB_UPDATE 方法)。OB_ZJB_UPDATE 方法的主要思想是在数据集每次动态减少时，均调用障碍物环境下的静态数据集的单纯型连续近邻链查询算法进行重新计算。由于有大量的冗余计算，该方法的计算代价较高。本小节考虑减少点对初始近邻链的影响情况，对数据集进行有效筛选和过滤，提出新的算法。

依据单纯型连续近邻链和判定圆的定义与性质可知，在初始单纯型连续近邻链CL 生成的情况下，减少点vdel对CL 的影响情况的分析如下:

2015年在2013年所采集的产生抗药性种群13JLGY-6、13JLGY-9、13JYJD-1、13JCWJ-3的原采集地采集看麦娘种子，分别命名为15JLGY-6、15JLGY-9、15JYJD-1、15JCWJ-3，采用整株生物测定法测定其抗药性。结果发现，这4个种群看麦娘对精唑禾草灵的相对抗性倍数在9.36～31.79倍之间(表5)。

(1)若减少点vdel不是CL 中的数据点，则CL 不受影响;

(2)若减少点vdel是CL 中的数据点，则减少vdel仅对vdel的链内后继点集有影响，对vdel的链内前驱点集没有影响。只需考虑vdel的链内后继点集的变化更新。

由以上讨论，可得出障碍物环境下数据集动态减少情况下的单纯型连续近邻链查询算法如算法2所示。

算法2 OB_DYNSCNNC_DET(V，vm，w，TL，vdel)

输入 空间数据点集V;数据起始点vm;待查链的数据点数目w;障碍线集TL;减少的数据点vdel

输出 由链首点vm开始的包含w 个数据对象点的一条更新后的单纯型连续近邻链CL

判断满足输入条件的初始单纯型连续近邻链CL 是否已生成;

由算法2 的核心步骤可知，该算法初始时调用OB_STASCNNC_Search 算法生成初始单纯型连续近邻链的时间复杂度为O(wlogn+ms)。根据删减点vdel与CL 的关系确定受影响的vdel的链内后继点集的平均时间复杂度为O(s')，由vdel的链内直接前驱点vq开始调用OB_STASCNNC_Search 算法生成部分近邻链的时间复杂度为O(hlogn +ts);该算法总的时间复杂度为O((w+h)logn +(m+t)s)，其中，h 是vq之后需要确定的链内数据点的个数;t 是vq之后需要考虑的被障碍物阻断的点对个数。该算法的效率与空间障碍物的数量、空间数据点的数量、数据链CL 中受vdel影响的数据点的数量之间的关系较大。

4 实验结果与分析

本文第3 节研究了障碍物环境下的动态数据集的单纯型连续近邻链查询方法。分别提出了OB_DYNSCNNC_ADD 算法和OB_DYNSCNNC_DET 算法。本节在Pentium4，3.2 GHz CPU、8 GB 内存，Windows XP 环境下，利用C++builder 6.0 对所提出的算法进行实验分析。实验数据是在二维空间中利用笔者开发的空间数据生成软件GEDATA4.0 随机生成的模拟数据。

设数据集包含的数据量为n，障碍线的个数为g，待查询的单纯型连续近邻链所包含的数据点的数目为w。ζ 表示在不同条件下OB_DYNSCNNC_ADD算法和OB_DYNSCNNC_DET 算法相对于反复调用障碍物环境下的静态数据集的单纯型连续近邻链查询算法进行计算的直接方法(即OB_ZJB_UPDATE方法)的计算效率的比率。图2 主要展示了以下3种情况的实验结果:

情况1 OB_DYNSCNNC_ADD 算法相对于OB_ZJB_UPDATE 方法的计算效率的比较。条件为n 不同，g 和w 相同;(图2(a)中，g=177，w=225，纵坐标ζ 表示OB_DYNSCNNC _ADD 算法相对于OB_ZJB_UPDATE 方法的计算效率的比率;横坐标表示数据集中包含的数据量，单位为4K，K=1 024)。

情况2 OB_DYNSCNNC _ADD 算法相对于OB_ ZJB_UPDATE 方法的计算效率的比较。条件为w不同，n 和g 相同;(图2(b)中，n=10K，g=175，纵坐标ζ 表示OB_DYNSCNNC _ADD 算法相对于OB_ZJB_UPDATE 方法的计算效率的比率;横坐标表示所查询的单纯型连续近邻链所包含的数据点的个数，单位为K/10，K=1 024)。

情况3 OB_DYNSCNNC_DET 算法相对于OB_ZJB_UPDATE 方法的比较。条件为n 不同，g 和w 相同;(图2(c)中，g=126，w=210，纵坐标ζ 表示OB_DYNSCNNC_DET 算法相对于OB_ZJB_UPDATE 方法的计算效率的比率;横坐标表示数据集中包含的数据量，单位为3K，K=1 024)。

由图2(a)可知，当障碍线的个数g，连续近邻链所包含的数据点的数目w 一定时，随着数据集包含的数据量增多，OB_DYNSCNNC_ADD 算法相对于OB_ZJB_UPDATE 方法的计算效率的比率将明显增大。图2(a)中，当n 为12K 时，其计算效率的比率为2.2，当n 增加到60K 时则提高到4.3。由图2(b)可知，当数据集包含的数据量n，空间障碍线的个数g 一定时，随着连续近邻链所包含的数据点的数目w的增多，OB_DYNSCNNC_ADD算法的计算效率将明显优于OB_ZJB_UPDATE 方法。在图2(b)中，当w 为0.2K 时，其计算效率的比率为2.0，当w 增加到1.6K 时则提高到5.5。由图2(c)可知，当障碍线的个数g，连续近邻链所包含的数据点的数目w 一定时，随着数据集包含的数据量n 增多，OOB_DYNSCNNC_DET 算法的计算效率将优于OB_ZJB_UPDATE 方法。在图2(c)中，当n 为3K时，其计算效率的比率为1.8，当n 增加到57K 时则提高到4.0。

图2 实验结果比较

由图2 的实验比较可知，在数据集的数据量，待查链包含数据点的个数和障碍线的个数较多时，本文提出的算法的优势更为明显。在查询过程中，算法对大量的冗余的数据点进行了预先判断和过滤，减少了不必要的冗余计算，从而较大程度地提高了查询效率。

5 结束语

为了处理障碍物环境下的动态数据集中的单纯型连续近邻链查询问题，本文对数据集动态增大和数据集动态减小2 种情况下的障碍物环境下的单纯型连续近邻链查询问题进行研究，分别提出了OB_DYNSCNNC_ADD 算法和OB_DYNSCNNC_DET 算法，并分3 种情况对所提算法进行了实验比较和分析。理论研究与实验表明，当数据集的数据量、待查链包含数据点的个数和障碍线的个数较多时，本文提出的算法的优势较为明显。未来的研究工作主要集中在以下两方面:(1)将本文的方法和区域关系(如Vague 区域关系［15］)结合处理受限区域中的复杂单纯型连续近邻链查询问题。(2)障碍物环境下的不确定单纯型连续近邻链查询问题。

［1］郝忠孝.时空数据库查询与推理［M］.北京:科学出版社，2010.

［2］Song Zhexuan，Roussopoulos N.K Nearest Neighbor Search for Moving Query Point［C］//Proc.of the 7th International Symposium on Advances in Spatial and Temporal Databases.Berlin，Germany:Springer-Verlag，2001:79-96.

［3］Mouratidis K，Yiu M L，Papadias D.Continuous Nearest Neighbor Monitoring in Road Networks［C］//Proc.of VLDB.Seoul，Korea:［s.n.］，2006.

［4］Hu Ling，Jing Yinan，Ku W S，et al.Enforcing k Nearest Neighbor Query Integrity on Road Networks［C］//Proc.of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.Redondo Beach，USA:ACM Press:346-349.

［5］Elmongui H G，Mokbel M F，Aref W G.Continuous Aggregate Nearest Neighbor Queries［J］.Geo Informatica，2013，17(1):63-95.

［6］Cheng R，Chen J，Mokbel M F.Probabilistic Verifiers:Evalutaing Constrained Nearest-neighbor Queries over Uncertain Data［C］//Proc.of International Conference on Data Engineering.Chicago，USA:［s.n.］:2008:973-982.

［7］Nutanong S，Tanin E，Zhang Rui.Incremental Evaluation of Visible Nearest Neighbor Queries ［J］.IEEE Transactions on Knowledge Engineering，2010，22(7):665-681.

［8］Gao Yunjun，Zheng Baihua，Chen Gencai，et al.Visible Reverse k-Nearest Neighbor Query Processing in Spatial Databases［J］.IEEE Transactions on Knowledge and Data Engineering，2009，21(5):1314-1327.

［9］袁培森，沙朝锋，王晓玲，等.一种基于学习的高维数据c-近似最近邻查询算法［J］.软件学报，2012，23(8):2018-2031

［10］苗东菁，石胜飞，李建中.一种局部相关不确定数据库快照集合上的概率频繁最近邻算法［J］.计算机研究与发展，2011，48(10):1812-1822.

［11］李 松，郝忠孝.基于Voronoi 图的反向最近邻查询方法研究［J］.哈尔滨工程大学学报，2008，29(3):261-265.

［12］李 松，张丽平，蔡志涛，等.数据集中单纯型连续近邻链查询方法［J］.计算机工程，2012，38(4):82-83，87.

［13］Zhang Liping，Li Song，Li Lin，et al.Simple Continues Near Neighbor Chain Query of the Datasets Based on the R Tree ［J］.Journal of Computational Information Systems，2012，8(22):9159-9160.

［14］张丽平，李 林，李 松，等.预定数据链规模的单纯型连续近邻链查询［J］.计算机工程，2012，38(10):51-53.

［15］李 松，郝忠孝.立体空间中的含核Vague 区域系表示与分析［J］.高技术通讯，2011，21(2):157-161.