空间数据库中混合数据组最近邻查询

蒋祎莹，张丽平，金飞虎，郝晓红

哈尔滨理工大学 计算机科学与技术学院，哈尔滨150080

随着基于位置服务的不断发展，空间数据库在交通路网系统、地理信息系统、决策支持系统等领域具有重要意义。近邻查询问题是当今数据库技术的热点，查询的结果通常是满足查询要求的空间数据或数据集合。最近邻查询是空间数据库查询领域的基础，由于查询需求的不断变化，产生了许多变体。如近邻查询、方向最近邻查询、聚集最近邻查询、组最近邻查询、约束最近邻查询、隐私保护最近邻查询等。组最近邻查询是最近邻查询的变体之一，最早由Papadias 等人在文献[11]中提出，并提出了三种基于R 树的组最近邻查询方法。文献[12]提出了空间数据库中基于Voronoi 图的线段组最近邻查询算法，该算法能够有效处理空间数据库中基于线段的组最近邻查询问题，弥补了现有的研究成果无法有效处理基于线段的组最近邻查询问题的不足。文献[18]考虑到现实生活中许多大型空间对象不适合抽象为点，提出了障碍环境中线段组最近邻查询研究。

以上都是将数据对象抽象为点或线段进行研究。在对现实中的对象进行研究时，查询对象集和目标对象集的数据对象类型往往不是单一的，还要根据实际情况将空间对象抽象为包含点与线段的混合数据。例如，当游客去一个城市旅行时，期望的住宿地点要离自己所规划的景点、商业街、饭店、电影院以及车站等距离之和最小。其中饭店、电影院以及公交站点需要抽象为点，而旅游景点和商业街需要抽象为线段。这些需求涉及的往往是点与线段的混合数据，但是仅仅将数据对象抽象为单一的点或线段往往会影响其精确度及查询效率，所得到的结果可能会有很大的误差。如图1，给定混合查询对象集={,,}和混合数据对象集={,,…,p,,,…,pl}。如果基于传统的组最近邻查询，线段要先抽象为点，得到抽象后的查询对象集′={,,′}，数据对象集′={,,…,p,′,′,…,p′}。与′的距离(,′)=(,)+(,)+(,′)=11.5，而′与′的距 离为(′,′)=(′,)+(′,)+(′,′)=13.5。此 时距离′内各个查询对象距离之和最小的数据对象为。而实际与的据离为(,)=(,)+(,)+(,)=11,与的距离为(,)=(,)+(,)+(,)=8.2，可得(,)＞(,)，因此实际到内各个查询对象距离之和最小的数据对象为，此时用传统的组最近邻查询方法解决该问题存在较大误差。

图1 混合数据组最近邻Fig.1 Group nearest neighbor for mixed data

为了提高查询的精确度和查询效率，本文针对混合数据提出了混合数据组最近邻查询方法。本文的主要贡献有以下四方面:

（1）现实生活中的一些数据集不能简单地抽象为点集或线段集，有时还要根据实际情况将其抽象为包含点与线段的混合数据集。为解决此问题，本文提出了混合数据组最近邻查询问题，并给出了混合数据组最近邻查询的定义。

（2）针对数据集中数据对象为混合数据的情况，本文提出了混合Voronoi 的概念并给出了混合Voronoi的构建方法。

（3）根据混合Voronoi 图的性质，提出了剪枝算法。所提算法能过滤掉大量的冗余数据并准确、有效地得到混合数据组最近邻的候选集合。

（4）本文提出精炼算法，根据不同对象之间的距离计算方法，对剪枝阶段得到的候选集进行进一步的筛选，从而得到混合数据组最近邻查询结果。

1 定义与性质

根据已有的组最近邻和Voronoi 图的定义，本文提出混合数据组最近邻和混合Voronoi图的概念。

（混合数据Voronoi 图（mixed data Voronoi diagram，MDV））给定一组混合数据集={，,…,p,,,…,pl}。并给出混合数据集中每个线段的端点，其中2 ＜＜∞，且当≠时，p≠p，其中,∈I={1,2,…,};2 ＜＜∞，且当≠时，pl≠pl，其中,∈I={1,2,…,}。混合Voronoi 图将平面分成若干个相连区域，称为Voronoi单元，令∈,每个数据对象mp所生成的Voronoi单元可定义为(mp)，由()={(),(),…,(mp)} 所定义的图形称为混合Voronoi图。

基于混合Voronoi 图的构建原理，得到混合Voronoi图的性质如下：

Voronoi 边上的点到这条Voronoi 边所在Voronoi多边形的生成对象的距离相等。

如果空间中某一对象在混合Voronoi 图的某个Voronoi 单元内，该对象的最近邻为其所在Voronoi单元的生成对象。

2 混合数据Voronoi图的构建

与构建传统Voronoi图相比，构建混合Voronoi图需要判断生成对象的类型和位置关系，还要考虑不同类型的对象之间的距离计算方式。

点与点之间的距离平分线为两点所连线段的垂直平分线，因此两点之间的Voronoi 边由两点连线的垂直平分线构成。点与线段之间距离平分线分两部分构建：在线段直接影响区域内，点与线段的距离平分线为以点为焦点，以线段为准线的抛物线；在线段直接影响区域外，点与线段的距离平分线为点与线段的端点连线的垂直平分线。当点在线段的直接影响区域内时如图2，给定点与线段，构建()，点与线段在()内的距离平分线为以点为焦点，线段为准线的抛物线；点与线段在()外的距离平分线为线段、的垂直平分线、。当点在线段的直接影响区域外时，如图2 中点与线段。

图2 点与线段距离平分线的构建Fig.2 Construction of bisector of distance between point and line segment

线段与线段的距离平分线分三部分构建，在两条线段共同的直接影响区域内，根据角平分线性质，两条线段的距离平分线为两线段延长线相交构成的角度的角平分线；在一条线段()的直接影响区域内一条线段()的直接影响区域外，两线段的距离平分线为以的一端点为焦点，以为准线的抛物线；在两条线段直接影响区域外，两条线段的距离平分线为两条线段端点连线的垂直平分线。如图3，在()与()内，、的距离平分线为；在()外()内，线段、的距离平分线为以的端点为焦点，为准线构成的抛物线；同理可得，()内()外的区域，为线段、的距离平分线；在()外()外的区域，线段、的距离平分线分别为线段、的垂直平分线、。、在各个区域内的距离平分线相交所构成的分界线为两条线段的距离平分线。

图3 线段与线段距离平分线的构建Fig.3 Construction of bisector of distance between line segments

本文采用增量法构建混合Voronoi图。与构建传统Voronoi图相比，构建混合Voronoi图要先确定生成对象的数据类型以及它们之间的位置关系，并根据不同的数据类型分别构建Voronoi 边，该过程的执行次数为有限次，因此根据增量法构建混合Voronoi 图的时间复杂度与传统Voronoi相同，均为(lb)。

3 混合数据组最近邻查询

本文提出的混合数据组最近邻查询方法分为3个阶段：构建混合Voronoi图；对数据集进行剪枝得到候选集；对候选集进行精炼得到混合数据组最近邻查询结果。对查询对象进行剪枝处理时，需要构建基于混合数据的查询凸包，本文称混合凸包。

定义3（混合凸包（mixed data convex hull，MDCH））将混合查询对象集中的查询对象相互连接构成一个凸多边形，使得所有查询对象均在此区域内，所围成的区域为混合凸包。与混合凸包相交的Voronoi单元的外边界构成的区域为混合查询对象集的影响区域，本文用()表示。

3.1 剪枝阶段

当查询对象为单个时，混合数据组最近邻查询即为混合数据最近邻查询，需要对查询对象为点和查询对象为线段分别进行处理。

当查询对象为点时，该点所在Voronoi单元的生成对象为此时的最近邻查询结果。

当查询对象为线段时，与线段相交的Voronoi单元的生成对象可能为最近邻查询结果。

如果查询对象为点，该点所在Voronoi 单元的生成对象为混合数据最近邻查询结果。

根据混合Voronoi 图的最近邻特性，查询点与其所在的Voronoi单元的生成对象的距离小于查询点与其他数据对象的距离。因此查询点所在的Voronoi单元的生成对象为最近邻查询结果。证毕。

如果查询对象为线段，与该查询对象相交的Voronoi单元的生成对象可能为混合数据最近邻查询结果。

查询线段被Voronoi 单元切分为不同的部分，根据混合Voronoi图的最近邻特性，各个部分与其所在的Voronoi单元的生成对象的距离小于到其他任意一个数据对象的距离。因此混合数据最近邻一定在与查询线段相交的Voronoi单元的生成对象中。证毕。

基于以上讨论，本文给出单个查询对象的组最近邻查询过滤算法。

MDNN_FILTER()

输入：查询对象集，混合数据对象集。

输出：最近邻查询结果候选集。

1.←∅；

2.Create_MDV()；

3.if 查询对象为点

4.for=1 to.

5. if∩(mp)≠∅

6.←mp；

7. else 对mp进行剪枝；

8.if 查询对象为线段

9.for=1 to.

10.if∩(mp)≠∅

11.←mp；

12.else 对mp进行剪枝；

13.return.

算法1 先构建混合Voronoi 图，判断查询对象的类型。如果查询对象为点，将该点所在的Voronoi 单元生成对象加入候选集；如果查询对象为线段，将与该线段相交的Voronoi单元生成对象加入候选集。该算法利用for 语句进行循环，设数据集对象共有个，for 循环语句的执行次数为次，因此该算法的时间复杂度为()。

当混合查询对象集中查询对象个数大于1 时，首先判断查询对象是否能够构成凸包，然后根据Voronoi 的特性以及查询对象的影响区域，分别给出查询对象能构成凸包和查询对象不能构成凸包的过滤算法，得到混合数据组最近邻查询候选集。

当各个查询对象首尾相连在一条线段上时，不能构成查询凸包。

当查询对象不能构成凸包时，对于任意一个不与该线段相交的Voronoi 单元的生成对象，在与该线段相交的Voronoi单元的生成对象中一定存在一个数据对象′，使得′到各个查询对象的距离之和小于到查询对象的距离之和。

如图4，任取两个数据对象构成混合查询对象集={,},为查询线段，为查询点，′与、、所在的Voronoi 单元相交。任取一个不与相交的Voronoi单元的生成点，例如。为的一个端点，为的一个端点，为线段与Voronoi边的交点。到各个查询对象的距离之 和(,)=()+()=||+||。到各个查询对象的距离之和(,)=()+()=||+||+||，根据Voronoi图性质可知||=||，因此||=||+||。由三角形三边关系可得||+||＞||。因此||＞||。同理可证||＜||，因此到各个查询对象的距离之和大于到各个查询对象的距离之和。同理可得，对于任意一个不与查询对象相交Voronoi单元的生成对象，在与查询对象相交的Voronoi 单元的生成对象集中一定存在一个数据对象，到各个查询对象的距离之和小于到各个查询对象的距离之和。证毕。

图4 查询对象的剪枝Fig.4 Pruning of query objects

当查询对象集能构成凸包时，构建()和()。

对于任意一个()外的对象，在()内，一定存在一个对象到各个查询对象的距离之和小于到各个查询对象的距离之和。

如图4，任取数据对象、、构成混合查询对象集={,,},为()内一数据对象，为()外的一个数据对象，到查询各个对象的距离之和为(,)=(,)+(，)+(,)，到查询各个对象的距离之和为(,)=(,)+(,)+(,)。连接与Voronoi 边的交点为的中点。做的垂直平分线，因此||＞||,||＞||,||＞||,(,)＞(,)。可证得如果查询对象能够构成凸包，()内的生成对象到各个查询对象的距离之和一定小于()外的对象到各个查询对象的距离之和。同理，对于任意一个()外的数据对象，在()内一定存在一个数据对象到各个查询对象的距离之和小于到各个查询对象的距离之和。

如果查询对象集中所有查询对象均与同一个Voronoi多边形相交，那么该Voronoi多边形的生成对象一定是混合数据组最近邻查询结果。

根据Voronoi图的最近邻特性可知，查询对象集中所有查询对象与同一Voronoi 多边形相交，那么每个查询对象的最近邻均为该Voronoi单元的生成对象。因此该生成对象到各个查询对象的距离之和小于任意其他对象到各个查询对象的距离之和，那么该Voronoi单元的生成对象一定是混合数据组最近邻查询结果。如图4，混合查询对象集={,，}都在数据对象的Voronoi 单元中，因此为的组最近邻查询结果。

当查询对象集中的查询对象数量不为1 时，分为查询对象能够构成凸包和查询对象不能构成凸包两种情况，可得剪枝规则3～5。

当所有查询对象不能构成凸包时，即所有查询对象首尾相连在一条线段上时，对不与该线段相交的Voronoi单元的生成对象进行剪枝。

当所有查询对象能够构成凸包时，如果一个数据对象生成的Voronoi 单元不在()内，那么这个数据对象一定不是混合数据组最近邻查询结果。

如果所有查询对象与同一个Voronoi单元相交，那么该Voronoi 单元生成对象为组最近邻查询结果。

多个查询对象的组最近邻过滤算法如下。

MDGNN_FILTER()

输入：混合查询对象集，混合数据对象集。

输出：最近邻候选集，MDGNN()。

1.Create_MDV()；

2.if 所有的查询对象与同一个Voronoi单元相交

3.return 该Voronoi 单元生成对象为

4.if 查询对象不能构成凸包

5.将查询对象依次连接构成新的查询线段

6.for=1 to.

7.if∩(pl)≠∅

8.←pl；

9.else if 查询对象能构成凸包

10.for=1 to.

11.创建()；

12.for=1 to.

13. if()∩(pl)≠∅

14.←pl；

15.return.

算法2 首先构建混合Voronoi 图，如果所有查询对象均与同一个Voronoi单元相交，则该Voronoi单元的生成对象为混合数据组最近邻的查询结果。接着根据查询对象集是否能构成凸包，分别对数据对象进行剪枝，得到混合数据组最近邻查询的候选集。设数据集中数据对象的个数为，查询对象的个数为，执行的次数最多为×次，则时间复杂度为()，构建凸包的时间复杂度为()，因此算法2 的时间复杂度为()。

3.2 精炼阶段

精炼阶段主要是根据剪枝阶段得到的候选集，对数据进行进一步筛选，最后得到混合数据的组最近邻查询结果。

查询对象与数据对象之间的距离计算分为点与点、点与线段、线段与线段之间距离的计算。

（1）点与点之间的距离：点与点之间的距离为两点之间的欧式距离。

（2）点与线段之间的距离：点与线段的距离分为两种情况进行计算。当在()外时，点与线段的距离为与两端点距离的最小值。当点在()内时，过点作线段的垂线段，点与垂足的距离就为此时点与线段的最短距离。

（3）线段与线段之间的距离：计算线段与线段的距离需要先确定两条线段的位置关系。

线段与线段的位置关系，需要借助内倾端点与外倾端点来判断。如图5，给定线段、、,设点∈,∈。、在线段的直接影响区域内，过点、做的平行线段、，线段与线段在的两侧，称为线段相对于线段的外倾端点；线段与线段在的同一侧，因此称为线段相对于线段的内倾端点。

（1）线段与线段的位置关系1：一条线段的两个端点都在线段直接影响区域内，则该线段的两个端点到的最小距离为两条线段的最小距离。

如图5，给定线段、,令,∈()，为相对于的外倾端点，(,)＞(,)。则与的最短距离为点到的距离。

（2）线段与线段的位置关系2：两条直线各有一个点在另一条线段的直接影响区域中。当一个点为内倾端点，一个点为外倾端点时，外倾端点到另一条线段的距离为两条线段的最小距离。当两个点都为内倾端点时，则两条线段的另外两个端点之间的距离为两条线段的最小距离。

如图5，给定线段、、，点∈() 且为相对于的外倾端点；点∈()且为相对于的内倾端点，则(,)=(,)。∈()。点∈()且为相对于的内倾端点，当点∈()且为相对于的内倾端点，则(,)=(,)。

（3）线段与线段的位置关系3：只有一条线段的一个端点在另一条线段的直接影响区域内时，如果这个端点为外倾端点，则这个端点到线段的最小距离为两条线段的最小距离。如果这个端点为内倾端点，则这个端点所在线段的另一个端点与另一条线段两个端点的最小距离为两条线段的最小距离。

如图5，给定线段、、，点∈()且为相对于的外倾端点，则(,)=(,)。同理(,)=(,)。

图5 线段与线段位置关系Fig.5 Position relationship between line segments

（4）线段与线段的位置关系4：两条线段的两个端点均不在另一条线段的影响区域中，两条线段的最近距离为两条线段的端点之间的距离的最小值。

基于以上讨论，下面给出计算最短距离的算法。

(，)

输入：空间对象，。

输出：(，)。

1.if，均为点；

2.(，)=(，)；

3.if，一个为点，一个为线段，令为点，为线段，的左右端点为，；

4.Create()；

5.if在()内

6.(，)为点到线段垂线段的距离；

7.else在()外

8(，)=min{(，)，(，)}；

9.if，均为线段

10.令为且端点为，，令为且端点为，；

11.Create()，()；

12.if，满足位置关系1

13.if，in()

14. 令∈(，)为外倾端点，

15.(，)=(，)；

16.else if，in()

17. if∈(，)为外倾端点

18.(，)=(，)；

19.if，满足位置关系2

20.令为在()内的端点，为在()内的端点；

21.if为的内倾端点且为的外倾端点

22.(，)=(，)；

23.if为的外倾端点且为的内倾端点

24.(，)=(，)；

25.if为的内倾端点且为的内倾端点

26.′在()外，′在()外；

27.(，)=(′,′)；

28.if，满足位置关系3

29. if为在()内的端点

30. if为的外倾端点

31.(，)=(，)；

32. else if为的内倾端点

33. 令′为在()外的端点；

34.(，)=(′，)；

35. if∈{，}andin()

36. if为的外倾端点

37.(，)=(，)；

38. else if为的内倾端点

39. 令′为在()外的端点；

40.(，)=(，)；

41.if，满足位置关系4

42.(，)=min((，)，(，)，(，)，(，))；

43.return(，).

算法3 首先判断传入的两个对象是点还是线段，如果均为点，可直接计算两点间的距离(1～2 行)；如果一个为点，一个为线段，根据点与线段的位置关系计算点与线段的最短距离(3～8 行)；如果两个数据对象均为线段，根据两条线段的直接影响区域判断两条线段的位置关系，分段计算两个对象之间的最短距离(9～42行)。其中候选集中的数据对象的数量与查询对象的数量均为常数，因此判断对象的类型、构建线段直接影响区域、计算两个数据对象的最短距离的执行次数均为有限次，最终算法3 的时间复杂度为()。

得到混合数据组最近邻查询结果需要对过滤阶段得到的候选集合进行进一步筛选，根据不同数据类型之间的距离计算方式，本小节给出精炼算法。

MDGNN_REFINE(，)

输入：候选集，混合查询对象集。

输出：′。

1.for mpin

2.(mp，)=0；

3.for mqin

4.(mp，)+=(mp，mq)；

5.if＞(mp，)

6.=(mp，)，′←mp;

7.return′.

算法4 首先判断候选集中数据对象个数是否为1，如果中数据对象个数为1，可直接得到组最近邻查询结果()。如果中数据对象个数大于1，根据点与点、点与线段、线段与线段的距离计算方法计算每个数据对象到各个查询对象的距离之和(mp,)。通过比较(PL,)的大小最终得到组最近邻查询结果。

MDGNN_Query(，)

输入：混合查询对象集，混合数据对象集。输出：查询对象的组最近邻。

1.Create_MDV()；

2.if的数量为1

3.CS←MDGNN_FILTER()；

4.if的数量大于1

5.CS←MDGNN_FILTER()；

6.MDGNN←MDGNN_REFINE(，)；

7.return MDGNN.

设的数量为，首先对构建混合Voronoi图，时间复杂度为(lb)；然后判断内查询对象的数量，调用MDGNN_FILTER()算法或MDGNN_FILTER()算法得到候选集；接着调用MDGNN_REFINE(,)进一步对进行筛选。最终混合数据组最近邻查询的时间复杂度为(lb)。

4 实验与结果

本章使用两种对比算法与本文算法进行实验比较，分别测试数据对象的数量与查询对象的数量对运行时间的影响，数据对象的密度对候选点数量的影响，查询次数对算法准确率的影响。本文研究对象为混合数据集，但是目前已有成果中并没有直接解决这种复杂混合数据的组最近邻查询方法，因此无法和已有方法直接进行实验比较，现将已有的算法进行适当调整，得到两个对比算法。

本文第1 个对比算法MDGNN_Basic1 为在已有算法基础上进行综合调整得出的，MDGNN_Basic1主要调用文献[12]中提出的基于Voronoi 图的线段组最近邻查询算法（line segment group nearest neighbor，LGNN）和文献[13]中提出的基于Voronoi图的组最近邻查询算法（group nearest neighbor，GNN）两个已有的算法共同完成混合数据组最近邻查询任务。主要思想是将混合查询数据集中的查询点和查询线段分开处理，所有的查询点组成新的查询点集为，调用文献[13]中的GNN 得到查询点集的组最近邻查询结果候选集；所有的查询线段组成新的查询线段集，调用文献[12]中的LGNN 得到查询线段集的组最近邻查询结果候选集，将两次调用的结果进行组合，通过计算比较得到混合数据组最近邻结果。本文的第2 个对比算法为MDGNN_Basic2，利用文献[2]中提出的基于SI-树的LNN 算法和文献[4]中所提出的KNNSearch(,)算法，令为1，KNNSearch(,)算法即为查找的最近邻NNSearch()，找到查询对象集中每个点和每条线段的最近邻，然后将它们进行合并处理后进行计算比较，从而实现混合数据组最近邻查询。

本文通过实验对所提算法的性能进行分析。实验环境为：2.50 GHz CPU，8 GB 内存，500 GB 硬盘，用Microsoft Visual Studio.NET2003 编程实现，Windows10系统。实验使用的数据集由真实数据集和人工合成数据集两部分组成，在实验中对数据集进行了适当的调整和优化。真实数据集是圣华金县（TG）道路网络，共有18 263 个节点，数据集包括节点ID、标准化坐标、标准化坐标(http://www.cs.utah.edu/～lifeifei/research/tpq/TG.cnode)。人工合成数据集主要是取部分真实数据集中的点两两连接，连接成线段。所有的点均不在线段上，所有的线段均互不相交。执行100 次查询取平均值，然后对比3 种算法的测试结果。

首先分析数据集中数据对象的数量对运行时间的影响。随机选取真实对象集中的节点，并随机选取真实对象集中的节点两两连接生成线段，构成包含混合数据的数据对象集与包含混合数据的查询对象集。数据对象的数量分别为1 000、2 000、3 000、4 000、5 000、6 000、7 000。如图6，在数据集的数量逐渐增多的情况下，MDGNN_Query 算法平均执行时间分别为0.099 s、0.260 s、0.462 s、0.601 s、0.747 s、0.839 s、1.001 s；MDGNN_Basic1 算法平均执行时间分别为0.167 s、0.378 s、0.581 s、0.800 s、0.962 s、1.121 s、1.261 s；MDGNN_Basic2 算法平均执行时间分别为0.322 s、0.580 s、0.798 s、1.112 s、1.208 s、1.400 s、1.552 s，本文算法相对于其他两种算法平均分别提升了23.8%、42.4%。

图6 数据对象的数量变化对运行时间的影响Fig.6 Impact of changes in the number of data objects on running time

实验条件不变，进一步分析数据集中数量变化对算法I/O 代价的影响，如图7 所示。在数据集的数量逐渐增多的情况下，MDGNN_Query 算法的I/O 代价分别为100、150、197、255；MDGNN_Basic1 算法的I/O 代价分别为135、181、235、315；MDGNN_Basic2算法执行的I/O 代价分别为224、266、464、237，本文算法相对于其他两种算法平均分别提升了18.9%、41.0%。

图7 数据对象的数量变化对I/O 代价的影响Fig.7 Impact of changes in the number of data objects on I/O cost

图8 给出了数据对象的密度对候选对象数量的影响。随机选取真实对象集中的节点，再随机选取真实对象集中的节点两两连接生成线段，构成包含混合数据的数据对象集与包含混合数据的查询对象集。每单位面积数据对象的个数分别为15、30、45、60、75、90。从图中可以看出随着单位面积内数据对象数量不断增加，本文算法相对于其他两组算法平均分别提升了17.9%、35.1%。

图8 数据对象的密度对候选对象数量的影响Fig.8 Impact of density of data objects on the number of candidate objects

接着分析查询对象集的数量变化对运行时间的影响。随机选取真实对象集中的节点，并随机选取真实对象集中的节点两两连接生成线段，构成包含混合数据的数据对象集与包含混合数据的查询对象集。查询对象的数量为2、4、6、8、10、16、24、32。测试不同数量的查询对象对算法CPU 时间的影响。如图9，查询对象的数量逐渐增多时，MDGNN_Query算法执行的平均时间分别为0.322 s、0.401 s、0.523 s、0.606 s、0.712 s、0.823 s、0.920 s；MDGNN_Basic1 算法执行的平均时间分别为0.404 s、0.582 s、0.717 s、0.830 s、0.997 s、1.093 s、1.117 s；MDGNN_Basic2 算法执行的平均时间分别为0.500 s、0.720 s、0.997 s、1.107 s、1.110 s、1.350 s、1.471 s。本文算法相对于其他两种算法平均提升了18.7%、39.1%。

图9 查询对象的数量变化对运行时间的影响Fig.9 Impact of the number of query objects on running time

进一步分析不同数量的查询对象对I/O 代价的影响。如图10 所示，在查询对象的数量逐渐增多的情况下，MDGNN_Query 算法的I/O 代价分别为102、117、157、221；MDGNN_Basic1 算法执行的I/O 代价分别为135、149、216、284；MDGNN_Basic2 算法执行的I/O 代价分别为180、223、319、379。本文算法相对于其他两种算法平均分别提升了11.1%、36.7%。

图10 查询对象的数量变化对I/O 代价的影响Fig.10 Impact of the number of query objects on I/O cost

最后对算法的准确率进行测试，随机选取真实对象集中的节点，并随机选取真实对象集中的节点两两连接组成数据线段集，构成数据对象集与查询对象集。在实验中其他条件均一致时，分别测试查询次数为20、40、60、80、100、120、140 时三组算法的准确率，最终结果取其平均值。如图11，在查询次数逐渐增多时，本文算法相对于其他两种算法在准确率上平均分别提升了7.9%、13.5%。

图11 查询次数对算法准确率的影响Fig.11 Impact of the number of query objects on accuracy of algorithm

由实验分析可得，在处理混合数据组最近邻查询问题时，本文提出的MDGNN_Query 算法在运行时间、I/O 代价、算法准确率等方面均优于其他两组对比算法，且具有更高的查询效率和准确度。因为MDGNN_Basic1 算法需要对查询点集和查询线段集分别构建基于点的Voronoi 图和基于线段的Voronoi图，将点和线段分开处理，会造成搜索区域相重合，会对查询时间和I/O 代价造成影响。MDGNN_Basic2算法需要计算每一个查询对象的最近邻，再对每次查询的结果进行处理，搜索区域相重合的现象更为严重，降低了算法性能，增加了运行时间以及I/O 代价。而本文所提MDGNN_Query 算法直接针对混合数据集进行剪枝，精炼且不需要对结果集进行额外的处理，直接得到组最近邻查询结果，因此MDGNN_Query 算法的运行时间最短，I/O 代价相对最低，查询效率相对最高。在查询的准确率方面，其他两种对比算法是对点和线段分别进行查询，然后对结果集进行组合处理得到查询结果，查询效率低并且查询结果往往会有一定的误差；而本文算法是在混合数据集的基础上进行的组最近邻查询，准确率较高，并且在查询过程中能够更快地达到较高的准确率。

5 结束语

本文研究了混合数据的组最近邻查询问题，提出了点和线段混合的组最近邻查询的概念，将查询过程分为剪枝和精炼两个过程。剪枝阶段根据查询对象的数量和分布情况以及Voronoi图的性质进行筛选得到满足查询条件的候选结果集，然后在精炼阶段再次对候选结果进行筛选，得到最终结果。由于本文直接对混合数据进行处理，在查询效率及准确度等方面都更优。理论和实验研究表明，所提算法能够较好地解决点和线段混合数据的组最近邻问题。尽管本文在多方面的性能较优，但是本文算法也存在不足，因为本文先构建查询凸包，通过构建查询对象的影响区域来对数据对象进行剪枝，在查询对象距离过于分散时，查询对象的影响区域范围过大，剪枝效果会受到较大程度的影响。未来的研究重点是主要集中处理不确定数据的混合组最近邻查询问题并对本文算法进行改进。