-
最近邻（nearest neighbor，NN）查询就是找到离目标对象最近的邻居，它在地理信息系统（geographic information system，GIS）、数据库、图像检索、机器学习、智慧城市、医疗营救、物资分配等领域都发挥了重要作用。近年来，随着互联网技术和GIS的快速发展，最近邻查询算法越来越受到国内外学者的重视。
目前解决近邻问题所使用的索引结构主要包括R树（Rectangle tree）及其变种树、Voronoi图、Hilbert空间填充曲线、四叉树等。文献[1]提出了深度优先遍历R树的Depth First算法，减少访问不必要的子树，从而避免了对整个R树进行查询，提高了查询效率；文献[2]利用Voronoi图划分二维空间进行k-最近邻（k-nearest neighbors，k-NN）查询，查询和数据更新成本较低；文献[3]提出了一种基于密度网格索引的k-NN查询算法，利用矩形的几何特点获取候选搜索半径，再根据移动对象的密度分布情况从中选择适当的搜索半径进行距离过滤；文献[4]基于Voronoi图提出了基于概率的聚集最近邻查询方法；文献[5]在球面退化四叉树格网模型基础上，提出了一种动态多层次格网单元邻近搜索算法；文献[6]在Geohash编码格网基础上建立了自适应Geohash-Trees的空间索引，该索引能够根据轨迹密度划分空间，提高了范围查询效率；文献[7]提出了一种基于R树广度遍历和优化排序原理的最近邻查询算法，能适应不同空间分布的目标数据集；文献[8]将k-NN和Skyline查询相结合，对于一个给定的查询点q，可查询出在空间属性和非空间属性上不受支配，且距离最接近查询点q的k个数据点；文献[9]提出了一种生成自适应索引的方法来提高查询处理性能和存储使用率，实现了区域的k-NN查询；文献[10]通过应用空间填充曲线来确定哪些对象更适合分组索引移动对象，还设计了一个概率模型合理地量化每个对象成为查询结果的可能性，有效地解决了概率k-NN查询问题；文献[11]针对现有的高维空间近似k-NN查询算法在数据降维时不考虑维度间关联关系的问题，首次提出了基于维度间关联规则进行维度分组降维的方法。
路网环境下的k-NN查询就是根据用户的当前位置找到前k个距离用户最近的数据对象。目前，路网环境下的k-NN查询技术已经有了一定的进展。文献[12]提出了IER（incremental euclidean restriction）和INE（incremental network expansion）两种方法。其中，INE方法是Dijkstra算法的扩展，从查询位置逐步向邻近点扩展，直到获得k-NN结果集；IER方法利用空间修剪技术改进了INE方法，通过欧氏距离检索候选对象。文献[13]将欧氏距离存储为最短路径距离边界，以最佳优先方式在空间网络中找到k个最近邻居；文献[14]提出了一种高度平衡且可扩展的G-tree索引，可以进行有效查询；文献[15]分别从最近邻查询采用的索引结构和查询处理过程对现有路网环境下的最近邻查询方法进行了分析和比较；文献[16]提出了一种具有方向约束的连续最近邻查询方法，该方法的查询结果在满足最近的条件下，也满足方向约束。上述方法主要处理查询对象和数据对象类型单一的查询问题，然而在现实中，目标对象集的数据对象类型往往不是单一的，不同类型的对象组成了目标对象集，查询问题将会变得复杂。在路网中，目标对象可能是一家超市、一家医院或一座大桥，此时目标对象与路网不止有一个交点，而查询对象无论到哪个交点都可以到达目标对象，使查询问题也发生了变化。已有的解决路网最近邻查询的方法不能直接解决这类问题，需要对点和线段混合的数据进行最近邻查询。
针对现实应用问题，本文提出了路网环境下的混合数据最近邻查询（network mixed data nearest neighbor，NMNN）算法，拓宽了最近邻查询的研究领域。针对数据的多样性，当数据对象为线段时，使用线段与路网的交点来替代线段，将数据对象转化为数据点，便于计算。首先对数据进行预处理，将数据存放在数组中，形成一种映射关系；然后提出最短路径定理以及推论来进行剪枝；最后通过对距离的计算和对比有效地查询出最近邻结果。
-
道路网络由节点、边和边的长度组成，使用赋权有向图G（N，V，E）来构建路网模型。其中，N表示路网中节点的集合，V表示路网中相邻两个结点之间的距离，E表示路网中路段的集合。
在路网模型G（N，V，E）中，路网距离dn（q，pi）表示查询点q到数据点pi所经过的最短路径的长度，Path（q，pi）表示查询点q到数据点pi的最短路径。当两点之间没有路径存在时，设两点之间的路网距离为dn（q，pi）=∞。
Hilbert空间填充曲线[17]定义为S维空间Rs与一维空间R之间的一一映射，记作H：Rs→R。若点p∈Rs，则H（p）∈R，也称H（p）为点p的H值。对于点集{p1，p2…pn}，有H{p1，p2…pn}={H（p1），H（p2）…H（pn）}。
给定一个数据点集P和一组数据线段集L，P={p1，p2…pm}，L={l1，l2…ln}，其中2 < m <
，2 < n < ∞，且当i ≠ j时，pi≠ pj，li≠ lj。给定路网G（N，V，E），在路网上的数据点pi∈P，数据线段li∈L，其中2 < i < m，2 < j < n。如果数据线段li与路网有两个交点，则将其设为ai和bi，如果数据线段li与路网有且只有一个交点，则将其设为oi，交点所构成的集合与数据点集P合并构成一个新的集合P'，则路网环境下查询点q的混合数据最近邻NMNN（q）就是返回P'中到查询点q的路网距离最小的对象p'i，即满足dn（q， p'i）≤dn（q， p'j），其中，p'j是P'中不同于p'i的任一对象。 -
由于道路网络上不仅存在数据点，还存在数据线段，故本文在数据对象集中加入了数据线段，数据对象的位置分为两种情况：（1）数据对象与道路网络有且只有一个交点，此时的数据对象可以抽象成该数据对象与道路网络的交点进行处理；（2）数据对象与道路网络有两个交点，此时的数据对象可以抽象成该数据对象与道路网络的两个交点进行处理，但是在进行最短距离计算时需要比较查询点到这两个交点的最短路径，取较小值。数据对象与道路网络无交点的情况无意义，故不做考虑。
-
四叉树索引将空间递归划分为不同层次的树结构，以十字递归的方式将空间等分成4个相等的子空间，直到每个子空间只存在一个对象时划分结束。当空间数据对象分布比较均匀时，空间数据插入和查询效率较高。Hilbert空间填充曲线在二维空间中通过把一个矩形区域不断地分成4个小矩形区域，按照Hilbert曲线的穿越顺序把空间中的每一个小矩形区域线性地连接起来，使曲线填满整个空间，这样就实现了从高维空间到一维线性空间的映射。利用Hilbert曲线对网格进行排序，使得空间上位置相邻的对象在存储时也保持相邻。HR树（Hilbert R-tree）[18]是在R树的基础上，按照Hilbert曲线的顺序对数据矩形进行排列而得到的一种索引结构。
基于四叉树、Hilbert空间填充曲线和R树设计的QHR树（quad-Hilbert-R tree）通过四叉树的划分原理将整个索引空间划分成多个子空间，然后在每个子空间内对数据对象的位置关系进行判断来建立HR树。整个索引空间被四叉树划分成4个相等的子空间，使得每个子索引空间与空间内的树相对应，空间内的数据与索引空间建立空间关系。本文利用QHR树对数据集进行预处理和剪枝查询。
-
为了便于数据的查询，首先对数据集进行了预处理，将路网环境下的数据线段转化为点，将线段和路网的交点与数据线段形成一种映射关系，可以通过查询点的位置来查找对应的线段。将数据点与其所在单元格的H值也形成一一对应的关系，为之后的数据集约减和精炼过程提供方便。
首先查询出查询点q的H值，然后将q的邻近区域中的路段上的数据对象及其所在网格的H值进行保存，其中使用其与路段的交点所在单元格的H值来代替数据线段的H值，减少了剪枝过程的计算量。由于数组是有序的元素序列，通过数组下标的对应形成了一种映射关系，故使用数组对数据进行存储，由此提出了基于映射关系的数组生成算法——Array算法。具体步骤如下：（1）在查询区域内创建Hilbert曲线网格，根据Hilbert曲线的特点，计算出查询点q所在单元格的H值。（2）遍历数据点集中的数据点，将点pi放入数组P[i]中，将点pi所在单元格的H值放入数组Ph[i]中，继续遍历数据线段集中的数据线段，将线段lj放入数组L[j]中。（3）对数据线段与路网的交点数量进行判断，如果有且只有一个交点，则设为oj，将点oj放入数组Pl[j]中，点oj所在单元格的H值放入数组Lh[j]中；如果有两个交点，则设为ai和bi，将点ai和bi的集合放入到数组Pl[j]中，点ai和bi所在单元格的H值的集合放入数组Lh[j]中，最终返回相关的数组。
数组P[i]和数组Ph[i]存在一一对应关系，一个数据点对应一个H值；数组L[j]与数组Pl[j] 存在一一对应关系，一条线段所对应的是一个线段与路网交点的集合；数组Pl[j]与数组Lh[j]也存在一一对应关系，线段与路网交点的集合所对应的是一个H值的集合。
由于欧氏空间中两点之间的距离是两点之间的直线距离，在路网中两点间的距离是道路网络中的距离，而两点之间的直线距离最短，那么在路网环境下查询点q到其最近邻的距离一定不大于到其余数据对象的距离。如果欧氏空间中的最近邻点与查询点q在同一条路段上，此时两点之间的直线距离与路网距离相等，则欧氏空间上最近邻结果即为路网环境下的最近邻。由此给出了剪枝方法1、2。
剪枝方法1：如果在欧氏空间上查询点q到数据对象pi的距离大于在路网下查询对象q到其最近邻的距离，那么在路网环境下查询对象q到数据对象pi的距离一定不小于在路网下查询对象q到其最近邻的距离，将pi进行剪枝。
剪枝方法2：如果欧氏空间下的最近邻点与查询点q在同一条路段上，则查询点q在欧氏空间上与路网环境下的最近邻结果相同。
由于欧氏空间中查询点q到数据对象的距离是两点之间的直线距离，在路网中查询点q到数据对象的距离是两点之间道路网络中的距离，而两点之间的路网距离一定不小于直线距离，那么路网环境下查询点q到其欧氏最近邻的距离一定不小于欧氏空间下查询点q到其最近邻的距离，因此路网最近邻结果一定在以欧氏空间下查询点q到其最近邻的距离为半径的圆外，需构造以欧氏空间下查询点q到其欧氏最近邻的距离为半径的圆。由于在路网环境下查询点q到其欧氏最近邻的距离是两点间的路网距离，如果以路网环境下查询点q到其欧氏最近邻的距离为半径的圆内没有数据点，则说明路网环境下的最近邻就是其欧氏空间下的最近邻；反之，如果以路网环境下查询点q到其欧氏最近邻的距离为半径的圆内存在数据点，则说明路网环境下的最近邻就在这些数据对象之中。由此本文给出了剪枝方法3。
剪枝方法3：设NN（q）表示查询点q的最近邻，如果欧氏空间下的最近邻点与查询点q不在同一条路段上，则以查询点q为圆心，以欧氏空间下查询点q到其欧氏最近邻的距离为半径构造圆，记为Circle（q，de（q，NN（q））），再以查询点q为圆心，以路网环境下查询点q到其欧氏最近邻的距离为半径构造圆，记为Circle（q，dn（q，NN（q）））。将位于这两个圆组成的圆环中的数据点加入到候选最近邻集合中，将与此圆环相交的网格中的数据点也加入到候选最近邻集合中。
根据三角不等式性质可知，对于任何边 < ni，nj > ∈E，都有Path_length（ni，nj）≤ Path_length（ni，nk）+ Path_length（nk，nj）。其中Path_length（ni，nj）表示点ni到点nj的最短路径距离。
根据最短路径性质可知，对于任意给定的起点q和pi，如果Path（q，…，ni，…，nj，…， pi）是点q到点pi的最短路径，则在Path路径沿途上的任意两点间的最短路径也在Path路径上。
由此可知，对于给定的起点q和pi，如果Path（q，…，ni）是点q到点ni的最短路径，Path（nj，…，pi）是点nj到点pi的最短路径，则点q到点pi的最短路径不一定是Path（q，…，ni）与Path（nj，…，pi）的和。根据最短路径性质，可以得到剪枝方法4。
剪枝方法4：以查询点q为起点，候选集合C1中的数据点为终点，如果Path（q，…，ni，…，nj，…，C1）是点q到点pi的最短路径，则点q到这条路径上任意一点间的最短路径也在Path路径上，将这些数据点加入到候选最近邻集合中。
根据剪枝方法4可知，需要进一步求解点q到点pi的最短路径，本文使用改进的双向A*算法[19]求查询点到候选集合中的数据点的最短路径。
根据剪枝方法1、2、3、4，将大量数据点进行修剪，得到过滤算法NMNN_ FILTER（q）。具体步骤如下：（1）将候选最近邻集合C初始化为空，如果在欧氏空间上查询点q到数据对象pi的距离大于在路网下查询对象q到其最近邻的距离，则使用剪枝方法1进行剪枝。（2）如果欧氏空间下的最近邻点与查询点q在同一条路段上，则利用剪枝方法2进行剪枝。（3）如果欧氏空间下的最近邻点与查询点q不在同一条路段上，则利用剪枝方法3进行剪枝。（4）确定到以查询点q为起点到达路径上点的最短路径，利用剪枝方法4将这些路径上的数据点加入到候选最近邻集合中，最终得到候选最近邻集合C。
如图 1所示，查询点q的最近邻为点p8，在路网环境下查询对象q到数据对象pi（如p11、p6、p13等）的距离一定不小于在路网下查询对象q到点p8的距离，根据剪枝方法1，将这些数据对象进行剪枝。图 1中查询点q的最近邻点p8与查询点q不在同一条路段上，以查询点q为圆心，以查询点q到点p8的距离为半径构造圆，记为Circle（q，de（q，p8））；以查询点q为圆心，以路网环境下查询点q到点p8的距离为半径构造圆，记为Circle（q，dn（q，p8）），这两个圆组成的圆环如图中阴影部分所示，点p5、a2、p8在此圆环中，将这几个点加入到候选最近邻集合中，将与此圆环相交的网格中的数据点p2、b2也加入到候选最近邻集合中。根据剪枝方法4，以查询点q为起点，候选最近邻集合中的数据点p5为终点的最短路径为Path（q，n7，p8，n2，p1，n1，p5），由于点q到这条路径上任意一点间的最短路径也在Path路径上，数据点p1在此最短路径上，故将数据点p1也加入到候选最近邻集合中。
图 1 数据集约减过程
Figure 1. Process of Data Reduction
-
§1.2.2对数据集进行了初步的约减，下面对数据集进行进一步的精炼，最终查询到最近邻结果。如果Path（q，…，ni，…，nj，…， pi）是点q和点pi之间的最短路径，则点q到该路径中间任意一点pk间的最短路径长度一定小于该路径长度，即Path_length（q，pk）≤Path_length（q，pi）。由此对候选最近邻集合进行进一步的缩减，然后对缩减之后的数据集进行精炼，在精炼过程中需要对查询点到候选最近邻集合C中的点的最短距离进行计算。如果候选集合中的数据点ci与查询点q在同一条路段上并且方向可达，则最短距离为dn（q，ci）=de（q，ci）；如果候选集合中的数据点ci与查询点q不在同一条路段上，则调用双向A*算法找到最短路径，即可得到最短距离。由此进一步给出了精炼算法NMNN_Search（q），步骤如下：（1）调用NMNN_ FILTER（q）算法得到候选最近邻集合C。（2）如果C集合中某一点cj在q到集合C中的另一点ci的最短路径Path（q，…， ci）上，则将点ci剪去，更新集合C。（3）如果候选集合C中的数据点ci与查询点q在同一条路段上并且方向可达，则判定欧氏空间上的最短距离与路网上的最短距离相等；如果候选集合中的数据点ci与查询点q不在同一条路段上，则调用双向A*算法找到最短路径。（4）遍历所有节点得到所有节点的最短路径，通过比较得到最短距离，返回精确的最近邻结果。
-
使用3种对比算法与本文所提算法进行比较，分别测试数据对象的数量对中央处理器（central processing unit，CPU）运行时间的影响和对输入/输出（input/output，I/O）代价的影响，以及路网规模的大小对CPU运行时间的影响，最终得出比较结果。
由于本文的研究对象为点和线段混合的复杂数据，目前并没有直接解决这种复杂混合数据类型的最近邻查询方法，故选择的3种对比算法分别是在文献[3]、文献[20]和文献[14]算法基础上改进得出的。其中，NN_Search（q）是对文献[3]提出的k-NN_Search（q，k）算法改进得到的；QNN（quadtree nearest neighbor）算法是对文献[20]提出的QKNN（quadtree-based k-NN search）算法改进得到的；NN_Search（q，G）算法是文献[14]提出的路网k-NN查询算法。
本文实验使用的数据集包括真实数据和人工合成数据两部分，其中真实数据采用的是美国加州路网的数据，共包括1 957 027个节点，2 760 388条路段，其中交叉点和端点由节点表示，连接这些交叉点或道路端点的道路由无向边表示。为便于研究，对一些数据进行了适当调整。人工合成部分主要是通过人工将此真实数据集中加入方向，并且均匀地在路段上生成数据点。将生成的数据点部分两两连接，连接成一些线段，这些线段与路网路段有交点。其中所有的线段均互不相交，并且点不在线段上。数据点集通过随机生成数据点而得到，数据线段集通过随机生成数据线段而得到，之后将数据线段与路网的交点加入到数据点集中。
本文分析了数据对象的数量对CPU运行时间的影响，结果如图 2所示。由图 2可知，4种算法的CPU运行时间都是随着数据点数量的增加而逐渐增加的，其中NMNN_Search（q）算法的CPU运行时间最少。这是由于NMNN_Search（q）算法首先利用剪枝方法和最短路径定理对数据集进行了约减，减少了后续的计算量，然后对最近邻候选集进行了一次精炼，减少了查询时间。
图 2 数据点的数量对CPU运行时间的影响
Figure 2. Effect of the Number of Data Points on CPU Runtime
针对4种算法分析了数据对象的数量对I/O代价的影响，结果如图 3所示。由图 3可知，4种算法的访问数据量都是随着查询点的数量增加而逐渐增加的，但是NMNN_Search（q）算法的增长幅度偏小。这是因为3种对比算法中需要存储每个子图内的边界节点之间的距离信息，这些信息中存在大量冗余的距离信息，使得访问数据量增加。
图 3 数据点的数量对I/O代价的影响
Figure 3. Effect of the Number of Data Points on I/O Costs
进一步使用3个真实的数据集进行对比实验，分别是美国的圣华金市、旧金山和加州的路网数据，数据集如表 1所示。统计了路网规模的大小对CPU运行时间的影响，结果如图 4所示。
表 1 路网数据集
Table 1. Road network data set
数据集 地点 顶点/个 边/条 Road-TG 美国圣华金市 18 263 23 874 Road-SF 美国旧金山 174 966 223 001 Road-CA 美国加州 1 957 027 2 760 388 
图 4 路网规模的大小对CPU运行时间的影响
Figure 4. Effect of Road Network Size on CPU Runtime
由图 4可知，4种算法在不同规模路网下的CPU运行时间也不同，规模越大，CPU运行时间越长，其中NMNN_Search（q）算法的CPU运行时间最少。这是由于NMNN_Search（q）算法根据最短路径定理对查询点周围满足剪枝条件的数据点和路网数据都进行了剪枝，所以路网规模的增大对于算法的时间复杂度影响较小，故NMNN_Search（q）算法优于其他对比算法。
-
本文系统研究了路网环境下混合数据的最近邻查询方法，分为预处理、数据集约减和数据集精炼3个查询过程。根据Hilbert曲线、四叉树和R树的特性，设计了QHR树。对数据进行预先处理，利用剪枝方法和最短路径定理对数据集进行了有效约减，通过计算距离并比较得到最近邻结果。研究成果能较好地解决路网环境下混合数据的最近邻查询问题。未来的研究工作将主要集中于障碍环境下的点和线段混合数据的最近邻问题。
-
摘要: 路网环境下的k最近邻查询方法在地理信息系统、智慧城市、数据挖掘、医疗营救和物流配送等领域都有着较为重要的作用，已有路网环境下的最近邻查询方法无法直接解决查询对象为点而数据对象为点和线段混合的复杂数据的近邻查询问题，为了弥补已有方法的不足，提出了路网环境下混合复杂数据的最近邻查询算法。将查询过程分为预处理、数据集约减和数据集精炼3个部分，并与3种对比算法进行对比实验，研究了测试数据对象的数量、路网规模的大小对中央处理器运行时间以及输入/输出代价的影响。结果表明，所提算法能有效地处理路网环境下混合数据的最近邻查询问题。Abstract:
Objectives The k nearest neighbor query method under the road network environment plays an important role in geographic information system, point of interest discovery, smart city, data mining and material distribution. The existing methods mainly deal with the query problem that the query object and data object are single data type. However, in reality, the data object type of the target object set is often not single, and the query problem will become more complex. The existing nearest neighbor query methods in road network cannot directly solve the neighbor query problem in which the query object is a point and the data object includes the data mixed with points and line segments. In order to make up for the shortcomings of the existing methods, the nearest neighbor query algorithm of mixed complex data in the road network is proposed. Methods The query process is divided into three parts: Preprocessing, data set reduction and data set refining. Firstly, the data set is preprocessed, the line segments are transformed into points. A mapping relationship is formed between the intersection of line segments in the road network and line segments, and the corresponding line segments are found by querying the location of the points. The query points, data points and Hilbert values are stored using arrays. Secondly, the data object set is refined preliminarily by pruning method and shortest path theorem to reduce the number of data objects, and the data set filtering algorithm is given. Finally, the points in the data set are further pruned to calculate the shortest path network distance from the query point to the points in the candidate set. Compared with these distances, the shortest path distance can be determined, and then the nearest neighbor is accurately found. Results Experimental results show that the proposed algorithm effectively reduces the data set and the amount of calculation in the query process, further refines the nearest neighbor candidate set and reduces the query scope and the query time. There is no need to store the distance information between all boundary nodes in the road network, so a large amount of redundant distance information is eliminated.The data points and road network data that meet the pruning conditions around the query points are pruned. Therefore, the increase of road network scale has little impact on the time cost of the algorithm. Conclusions The proposed algorithm can directly deal with the nearest neighbor query of mixed data in the road network environment. When the number of data objects and the scale of the road network are large, the algorithm has obvious advantages in central processing unit running time and input/output cost. -
Key words:
- spatial database /
- road network /
- mixed data /
- nearest neighbor query /
- space filling curve
-
表 1 路网数据集
Table 1. Road network data set
数据集 地点 顶点/个 边/条 Road-TG 美国圣华金市 18 263 23 874 Road-SF 美国旧金山 174 966 223 001 Road-CA 美国加州 1 957 027 2 760 388 
下载: 导出CSV
-
[1] Roussopoulos N, Kelley S, Vincent F. Nearest Neighbor Queries[C]// The ACM SIGMOD International Conference on Management of Data, Austin, Texas, USA, 1995 [2] Hu L, Ku W S, Bakiras S, et al. Verifying Spatial Queries Using Voronoi Neighbors[C]//The 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, Beijing, China, 2010 [3] 章登义, 李想. 一种基于密度网格索引的k-最近邻查询算法[J]. 电子学报, 2017, 45(2): 376-383 doi: 10.3969/j.issn.0372-2112.2017.02.016 Zhang Dengyi, Li Xiang. A k-Nearest Neighbor Query Algorithm for Density Grid-Based Index[J]. Acta Electronica Sinica, 2017, 45(2): 376-383 doi: 10.3969/j.issn.0372-2112.2017.02.016 [4] Li S, Li B H, Yu J X, et al. Probabilistic Threshold K-ANN Query Method Based on Uncertain Voronoi Diagram in Internet of Vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(6): 3592-3602 doi: 10.1109/TITS.2020.3003902 [5] 赵龙飞, 赵学胜, 朱思坤, 等. 一种球面退化四叉树格网的多层次近搜索算法[J]. 武汉大学学报·信息科学版, 2018, 43(4): 529-535 doi: 10.13203/j.whugis20150611 Zhao Longfei, Zhao Xuesheng, Zhu Sikun, et al. A Multi-level Adjacent Searching Algorithm of Degenerate Quadtree Grid on Spherical Facet[J]. Geomatics and Information Science of Wuhan University, 2018, 43(4): 529-535 doi: 10.13203/j.whugis20150611 [6] 向隆刚, 高萌, 王德浩, 等. Geohash-Trees: 一种用于组织大规模轨迹的自适应索引[J]. 武汉大学学报·信息科学版, 2019, 44(3): 436-442 doi: 10.13203/j.whugis20160523 Xiang Longgang, Gao Meng, Wang Dehao, et al. Geohash-Trees: An Adaptive Index Which can Organize Large-Scale Trajectories[J]. Geomatics and Information Science of Wuhan University, 2019, 44(3): 436-442 doi: 10.13203/j.whugis20160523 [7] 龚俊, 谢潇. 基于R树索引的三维可视化查询方法[J]. 武汉大学学报·信息科学版, 2011, 36(10): 1140-1143 http://ch.whu.edu.cn/article/id/687 Gong Jun, Xie Xiao. Three-Dimension Visualization Query Method Based on R-Tree[J]. Geomatics and Information Science of Wuhan University, 2011, 36(10): 1140-1143 http://ch.whu.edu.cn/article/id/687 [8] 崔宁宁, 杨晓春, 王斌, 等. 移动k-支配最近邻查询验证研究[J]. 计算机学报, 2018, 41(8): 1780-1797 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201808006.htm Cui Ningning, Yang Xiaochun, Wang Bin, et al. Research on Authentication of Moving k-Dominant NN Queries[J]. Chinese Journal of Computers, 2018, 41(8): 1780-1797 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJX201808006.htm [9] Kim H I, Chang J W. k-Nearest Neighbor Query Processing Algorithms for a Query Region in Road Networks[J]. Journal of Computer Science and Technology, 2013, 28(4): 585-596 doi: 10.1007/s11390-013-1359-8 [10] Huang Y K, Lin L F. Processing Probabilistic kNearest Neighbor Query Using RLSD-Tree[C]// The 28th International Conference on Advanced Information Networking and Applications, Victoria, Canada, 2014 [11] 李松, 胡晏铭, 郝晓红, 等. 基于维度分组降维的高维数据近似k近邻查询[J]. 计算机研究与发展, 2021, 58(3): 609-623 https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ202103016.htm Li Song, Hu Yanming, Hao Xiaohong, et al. Approximate k-Nearest Neighbor Query of High Dimensional Data Based on Dimension Grouping and Reducing[J]. Journal of Computer Research and Development, 2021, 58(3): 609-623 https://www.cnki.com.cn/Article/CJFDTOTAL-JFYZ202103016.htm [12] Papadias D, Zhang J, Mamoulis N, et al. Query Processing in Spatial Network Databases[C]// 2003 VLDB Conference, Berlin, Germany, 2003 [13] Samet H, Sankaranarayanan J, Alborzi H. Scalable Network Distance Browsing in Spatial Databases[C]//The ACM SIGMOD International Conference on Management of Data, Vancouver, BC, Canada, 2008 [14] Zhong R C, Li G L, Tan K L, et al. G-Tree: An Efficient and Scalable Index for Spatial Search on Road Networks[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(8): 2175-2189 doi: 10.1109/TKDE.2015.2399306 [15] 鲍金玲, 王斌, 杨晓春, 等. 路网环境下的最近邻查询技术[J]. 软件学报, 2018, 29(3): 642-662 https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201803009.htm Bao Jinling, Wang Bin, Yang Xiaochun, et al. Nearest Neighbor Query in Road Networks[J]. Journal of Software, 2018, 29(3): 642-662 https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB201803009.htm [16] Miao X, Guo X, Wang H, et al. Continuous Nearest Neighbor Query with the Direction Constraint[C]// International Symposium on Web & Wireless Geographical Information Systems, Kyoto, Japan, 2019 [17] Zhang L P, Ren L L, Hao X H, et al. Query Method for Nearest Region of Spatial Line Segment Based on Hilbert Curve Grid[J]. International Journal of Innovative Computing Information and Control, 2019, 15(4): 1287-1307 [18] Kamel I. Hilbert R-tree: An Improved R-tree Using Fractals[C]// International Conference on Very Large Data Bases, Santiago, Chile, 1994 [19] 林娜, 李天啸. 基于双向A*算法的城市无人机航路规划[J]. 沈阳航空航天大学学报, 2016, 33(4): 55-60 https://www.cnki.com.cn/Article/CJFDTOTAL-HKGX201604010.htm Lin Na, Li Tianxiao. Urban UAV Route Planning Based on Bidirectional A* Algorithm[J]. Journal of Shenyang Aerospace University, 2016, 33(4): 55-60 https://www.cnki.com.cn/Article/CJFDTOTAL-HKGX201604010.htm [20] Wen Y R, Xiong H L. Quadtree-Based KNN Search on Road Networks[C]//The International Conference on Computer Technology, Electronics and Communication (ICCTEC), Dalian, China, 2017 -
点击查看大图
图(4) / 表(1)
计量
- 文章访问数: 254
- HTML全文浏览量: 61
- PDF下载量: 35
- 被引次数: 0
