一种基于学习索引的路网空间索引构建方法

1.本发明涉及计算机技术领域和数据处理技术，具体涉及构建路网索引技术，可应用于定位、导航、路线规划等基于位置的服务，尤其涉及一种基于学习索引的路网空间索引构建方法。


背景技术：

2.随着定位、导航、路线规划等基于位置的服务(location based services，lbs)广泛应用，其针对特定点搜索最近路段的基础操作成为服务性能的瓶颈。为了在大规模数据下能够快速响应，传统的解决方法是构建索引对空间进行划分。如r树(antonin guttman.r-trees:adynamic index structure for spatial searching.in proceedings of the 1984acm sigmod international conference on management of data,pages 47
–
57,1984.)将路网数据集划分为不同的子集，对其子集构建树结构。使用最小边界矩形(minimum bounding rectangle,mbr)逼近空间数据对象时，多个小的mbr组合在一起时，形成一个较大的mbr，不断重复该操作，直到出现一个最大的mbr。节点之间的父子关系由较大的mbr与较小的mbr之间的父子关系决定。基于空间分区的索引四叉树(raphael a finkel and jon louis bentley.quad trees adata structure for retrieval on composite keys.acta informatica,4(1):1
–
9,1974.)将道路网络空间划分为区域，对该区域构建索引。在四叉树(通常用于二维数据)中，每个内部节点都有四个象限作为子节点。然而，实验结果显示，使用r树索引对一个gps采样点进行路段搜索，搜索时间为0.91ms，四叉树则需1.47ms，难以满足高频操作下快速响应的要求。而近期出现的学习索引，搜索时间可缩短为0.76ms，若利用学习索引对路段构建索引，可提高路段搜索的时间效率。
3.学习索引利用机器学习技术学习数据分布和查询负载特征，基于数据分布拟合函数的直接式查找代替传统的间接式索引查找。学习索引背后的思想是学习一个将搜索键值映射到数据对象存储地址的函数。文献(tim kraska,alex beutel,ed h.chi,jeffrey dean,and neoklis polyzotis.2018.the case for learned index structures.in proceedings of the 2018international conference on management of data(sigmod'18).association for computing machinery,new york,ny,usa,489
–
504.)首先提出了学习索引的思想，提出了递归索引模型，以分层的方式学习数据分布。其本质上是通过神经网络学习累积分布函数(cumulative distribution function,cdf)来预测搜索键值的位置。文献(pengfei li,hua lu,qian zheng,long yang,and gang pan.lisa:a learned index structure for spatial data.in acm sigmod,2020.)对时空数据构建学习索引，为gps采样点构建索引可取得较好的效果。但在路段构建索引时，搜索路段返回的结果仅包含路段起始点与终点均在搜索范围内的路段，不能返回与搜索范围存在空间交叉的路段。


技术实现要素：

4.本发明的目的在于克服上述现有技术存在的问题，提供一种基于学习索引的路网
空间索引构建方法。
5.为实现上述技术目的，本发明采用如下方案：
6.一种基于学习索引的路网空间索引构建方法，包括：
7.利用六边形网格划分道路网络，以中心的六边形网格为原点，对六边形网格从中心向外围按顺序分配编号，将各六边形网格中心记为参考点；
8.将路段投影至六边形网格，根据分层网格结构和参考点推断路段所属六边形网格及方向块，所述方向块为六边形网格的边与中点围成的三角形，方向块按顺序编号；
9.对六边形网格编号、方向块编号、路段到所属六边形网格的垂直距离和/或常数进行数学变换计算，获取路段的键值；
10.将路段根据键值排序，使用神经网络递归模型索引构建路网的学习索引。
11.作为一种优选的实施方式，以中心的六边形网格为原点，按照由内向外的顺序对六边形网格按照顺时针方向螺旋编号，每层六边形中均以正北方向的六边形为编号的起始点。该编码方式可根据六边形编号即可获得六边形参考点的地理位置，也可根据参考点的位置信息获得六边形的编号，实现参考点oi与对应六边形网格hi的一一映射关系，即：oi＝f(hi),hi＝f-1
(oi)。
12.作为一种优选的实施方式，对六边形内经过的路段数目设置路段数阈值，当某一六边形内经过的路段数目超过所述路段数阈值时，将该六边形按照同样的划分和编号规则划分为7个子六边形。可解决六边形网格覆盖过多路段，影响查询效率的问题。
13.作为一种优选的实施方式，所述根据分层网格结构和参考点推断路段所属六边形网格的方式为：
14.获取路段到所述中心的六边形网格的参考点的垂直距离和角度；
15.对所述垂直距离与六边形网格计算比值并向下取整，确定路段所属六边形网格所在层数；
16.基于所述角度确定路段所属六边形网格所在方位；
17.根据所述层数及方位确定路段所属六边形网格。
18.作为一种优选的实施方式，如果一个路段起始点和终点不在同一个六边形网格的同一方向块内，则将路段分割为多条子路段，对位于同一六边形网格和方向块内的子路段计算统一键值。
19.作为一种优选的实施方式，对每条子路段，找到与其最近的参考点从而确定其所在的六边形网格，计算子路段和所述最近的参考点的方向角，确定方向块，对每个子路段得到子路段、子路段所属六边形网格编号、方向块信息组成的三元组；
20.对所有的三元组以相同的归属网格和方向块作为分组依据进行分组，对每个分组获取路段和参考点之间的垂直距离，采用相同的算法获得三元组的键值。
21.作为一种优选的实施方式，所述使用神经网络递归模型索引构建路网的学习索引包括：
22.设置阶段1模型f1对键值数据进行构建模型并存储；
23.设置阶段2模型对六边形网格的数据进行构建模型并存储。
24.设置阶段3模型对子六边形网格的数据进行构建模型并存储。
25.作为一种优选的实施方式，所述键值基于下式计算：
[0026][0027]
其中keye为键值，c1，c2和c3为常数，hi为路段所属六边形网格的编号；bj为方向块编号，为路段到所属六边形网格的垂直距离的向上取整值。优选的，c3固定为1；c2设置为六边形边长l的位数+1的最小值；c1设置为六边形的方向块bj数量的位数+1乘以c2，这一参数设置对于不同城市的道路网络均有效。
[0028]
本发明的又一目的在于提供基于上述路网空间索引模型进行路段查询的方法，包括：
[0029]
对于给定的gps样本和搜索范围，以gps样本为中心，搜索范围为半径建立搜索圆，获取与搜索圆重叠的六边形网格；
[0030]
确定gps样本所属六边形网格并获取搜索范围内的关联六边形网格，获取与搜索圆相交的六边形网格集合；
[0031]
计算每个六边形网格的参考点到其与搜索圆相交区域的最大距离和最小距离，之后根据键值计算方式得到相交区域的下限键值和上限键值，将下限键值或上限键值输入学习索引中，得到位置搜索边界，基于误差边界确定搜索范围，来检索相交区域内候选路段的键值，获取查询结果。
[0032]
本发明利用新兴的学习索引技术来构建路段索引，先将路段投影到道路网络上，将路段空间四维信息降维成一维键值；再按路段对应的编码值进行排序，对排序后的路段对象及其位置进行学习，建立针对路段对象的学习索引机制；最后在道路网络中对原始的经纬度坐标实现路段查询。既能提高路段搜索的时间效率又可返回相对准确的结果，为基于位置的服务应用做好前期路段索引的准备。
附图说明
[0033]
图1是六边形覆盖路网示意图。
[0034]
图2是六边形网格编号排序图。
[0035]
图3是路段键值设置示意图。
[0036]
图4是构建空间学习索引结构图。
[0037]
图5是训练空间学习索引伪代码。
[0038]
图6是使用空间学习索引查询路段示意图。
具体实施方式
[0039]
1、路段投影
[0040]
(1)确定参考点
[0041]
1)使用六边形覆盖路网的地理编码方法，对给定的道路网络g确定一组合适的参考点。以所框定的道路网络g的中心为圆心，用边长为l正且平的六边形以顺时针螺旋的方向覆盖道路网络g。将道路网络g划分为不同的网格，直到六边形能完全覆盖道路网络g，并将每个六边形的中心作为参考点。(见图1)
[0042]
2)为区分这些参考点，我们以道路网络g的中心六边形为原点，根据由内向外的层次结构对六边形进行顺时针螺旋编号，在每层六边形中，将正北方向的六边形为起始点，以顺时针方向对六边形确定编号规则，最终得到六边形编号hi，其中第i个六边形的中心记为
参考点oi。图2说明了我们如何用六边形划分道路网络图，并为这些六边形分配编号hi。
[0043]
3)为解决六边形hi覆盖过多路段，影响查询效率的问题，若六边形覆盖路段(六边形内经过的路段)数目超过256条，则将六边形hi进一步划分为7个边长为的子六边形。该子六边形根据hi分配子id，中央的子六边形被标记为hi，而其他子六边形从中央子六边形正上方开始，h
i.1
到h
i.6
顺时针分配子id，o
i.1
到o
i.6
为每个子六边形的参考点。(见图3左图)
[0044]
(2)几何投影
[0045]
考虑到路段的特征，将路段e∈ξ投影到六边形网格上，将路段信息映射成一维的键值。基于分层六边形结构和参考点，路段e∈ξ可以大致描述为三部分：六边形hi，hi的方向块bj(即所述方向块为六边形网格的边与中点围成的三角形)，路段e到hi质心oi的垂直距离dist(oi，e)(见图3)。
[0046]
1)计算路段e到参考点o0的垂直距离le＝dist(o0，e)和路段e到参考点o0的角度de＝degree(o0，e)，根据垂直距离和角度信息确定路段e所属的六边形hi＝f(le，de)。特别地，仅根据hi的编号信息，也可反推路段e的le和de的范围。即le，de＝f-1
(hi)。
[0047]
2)f(le，de)根据六边形分层的结构特性来计算六边形编号hi。先根据le先确定六边形hi所在的层数再根据de确定六边形hi的方位最后hi＝f(le，de)＝3*lh*(l
h-1)+dh+1。
[0048]
3)计算路段e到参考点oi的角度确定路段e所在hi的方向块bj∈[0，5]。计算路段e到hi质心oi的垂直距离dist(oi，e)。若该六边形hi包含子六边形，则需根据判断路段e位于第k个子六边形，并计算路段e到参考点o
i.k
的角度确定方向块和计算路段e到参考点o
i.k
的垂直距离。
[0049]
(3)分配值
[0050]
若路段的起始点和终点均在同一六边形的同一方向块内，则该键值为：若路段的起始点和终点均在同一六边形的同一方向块内，则该键值为：
[0051]
一个路段可能会经过一个以上的六边形，因此一个路段会有多个键值。为了计算路段e的所有可能的键值，我们完成如下键值分配：
[0052]
1)将路段e以25米为间距分割多条子路段，判断每条子路段的起点与终点是否均在同一个六边形同一方向块内，若是则保留，反则对子路段进行分割，最终组成一个路段集pe＝{pz|z＝1，2，
…
}。对于pe中的每条子路段pz，找到与pz最近的参考点o
iz
，确定其所在的六边形h
iz
。注意h
iz
可以是一个子六边形。以北为零度方向，用子路段pz和参考o
iz
计算一个方向从而确定块索引为b
jz
。因此，对于每条子路段pz都得到一个三元组《pz，h
iz
，b
jz
》。
[0053]
将所有的三元组进行分组，以相同的h
iz
和b
jz
作为分组依据。对于每组，我们找到这个三元组的pz和o
iz
之间的垂直距离，用dist(o
iz
，pz)表示。因此，我们可以计算出这个三元组的键值为：
[0054][0055]
其中c1，c2和c3主要用于生成伸缩性良好的无误的键值，将有误键值(即相距很远
的路段映射到同一个键值)生成为伸缩性良好的无误键值。在我们的实验中，默认设置c1＝10000，c2＝1000，c3＝1。其中，c3固定为1；c2设置为六边形边长l的位数+1的最小值(如现六边形边长l为500米，则c2设置为1000)；c1设置为六边形的方向块bj数量的位数+1乘以c2(如现定义六边形的方向块bj数量为6，则c1设置为10c2＝10000)，发现这些参数设置对于不同城市的道路网络均有效。
[0056]
2、构建空间学习索引
[0057]
获得所有路段的键值后，现将路段根据键值进行排序，可有效检索查询范围内的数据。给定一个有序的数据集，预测每个键值对应记录的位置模型近似于一个累积分布函数(cdf)，其中累积的是各个键值对应的存储位置概率分布(如键值排序后，键值a位于整体数据的位置)。因此需要对累积分布函数进行建模，给定一个键值keye，对应的位置可以表示为：
[0058]
p＝f(keye)
×n[0059]
其中p是记录所在的位置，f(keye)是数据的累积分布函数，用于计算一个键值x不大于keye的概率，n表示数据的总数。
[0060]
根据路网划分，使用神经网络递归模型索引(rmi)来构建路网的学习索引，这是一个三阶段模型。路段键值及其位置p的累积分布函数逼近由一个阶段1模型f1、若干阶段2模型和阶段3模型组成(见图4)。
[0061]
(1)利用阶段1模型预测输入键值属于哪个六边形hi。
[0062]
(2)利用每个阶段2模型来估计键值的cdf函数估计值。若该六边形已被划分为多个子六边形，rmi模型将进一步建立相应的阶段2模型来预测输入键值属于哪个子六边形，来指向阶段3模型
[0063]
(3)由于在训练模型时预测的位置具有一定的误差δ，因此我们在γ的误差范围[γ-δ，γ+δ]内搜索正确的位置。考虑到键值是升序排列的，采用二分查找来加快查找速度(见图5)。
[0064]
(4)设(x，y)∈d为数据集中(键值，位置)的集合，我们通过调整每个阶段模型中的参数，即来训练rmi模型，最小损失函数为：
[0065][0066]
(5)以自顶向下的方式训练rmi模型。首先训练第一阶段模型，并通过训练第二阶段模型对预测进行微调，然后在必要时对第三阶段模型进行训练。通过迭代训练每个阶段的模型来构建完整的rmi模型。
[0067]
(6)在发达城市中，路网相对静态，很少有新建或移除路段的情况，但rmi模型在因道路变化而增加或删除(键值，位置)时仍具有可扩展性。支持未来的快速插入，应定期在键值数组中创建额外的间隙来保持足够的存储空间。通常，插入或删除操作的时间复杂度为o(n+k)，其中n是数据集d的大小，k是要插入或删除的键的数量。
[0068]
3、路段查询
[0069]
(见图6)形式上，给定一个gps样本s和搜索范围γ，学习索引查询将返回一组路段键值，最后验证路段是否与s间的距离不超过范围γ。
[0070]
(1)以gps样本s为中心，半径γ，获得与搜索圆重叠的六边形(或子六边形)，所交叉的六边形的集合用hs表示。先估计gps样本s所属的六边形hi，其中计算gps样本s到参考点o0的两点距离ls＝dist(o0，s)和到参考点00的角度ds＝degree(o0，s)，根据距离和角度信息确定gps样本s所属的六边形hi。迭代检查每个与六边形hi临近γ范围的参考点oi和gps样本s之间的距离是否小于若是，关联的六边形(或子六边形)被添加到hs中。
[0071]
(2)对于hs中每个与搜索圆相交的六边形hi，进一步与搜索圆的重叠部分分解为更小的区域，每个区域与一个且只有一个六边形hi的块相交。对于每个相交区域，我们可以很容易地计算出六边形hi的参考点oi到该区域的最小距离d
min
和最大距离d
max
。根据键值计算公式，可以得到相交区域的下限键值和上限键值，分别用k
l
和ku表示。然后，将下限键k
l
(或上限键ku)输入到学习索引中，我们将得到位置搜索边界[y
l-δ
l
，y
l
+δ
l
](或ku的[y
u-δu，yu+δu])，其中δ
l
和δu分别是所涉及的两个阶段模型的误差边界。因此，我们可以扫描组合搜索绑定[y
l-δ
l
，yu+δu]来检索该相交区域内候选路段的键值。我们对所有交叉区域重复这些操作，并将其检索到的路段密钥聚合为ki。
[0072]
(3)对hs中所有相交的六边形重复步骤，并将派生的键集合并，形成最终查询结果ks，其中包含样本s的所有候选路段。
[0073]
附：方法中涉及的符号注释：
[0074]
[0075]

技术特征：
1.一种基于学习索引的路网空间索引构建方法，其特征在于，包括：利用六边形网格划分道路网络，以中心的六边形网格为原点，对六边形网格从中心向外围按顺序分配编号，将各六边形网格中心记为参考点；将路段投影至六边形网格，根据分层网格结构和参考点推断路段所属六边形网格及方向块，所述方向块为六边形网格的边与中点围成的三角形，方向块按顺序编号；对六边形网格编号、方向块编号、路段到所属六边形网格的垂直距离和/或常数进行数学变换计算，获取路段的键值；将路段根据键值排序，使用神经网络递归模型索引构建路网的学习索引。2.根据权利要求1所述的方法，其特征在于，以中心的六边形网格为原点，按照由内向外的顺序对六边形网格按照顺时针方向螺旋编号，每层六边形中均以正北方向的六边形为编号的起始点。3.根据权利要求1或2所述的方法，其特征在于，对六边形内经过的路段数目设置路段数阈值，当某一六边形内经过的路段数目超过所述路段数阈值时，将该六边形按照同样的划分和编号规则划分为7个子六边形。4.根据权利要求1所述的方法，其特征在于，所述根据分层网格结构和参考点推断路段所属六边形网格的方式为：获取路段到所述中心的六边形网格的参考点的垂直距离和角度；对所述垂直距离与六边形网格计算比值并向下取整，确定路段所属六边形网格所在层数；基于所述角度确定路段所属六边形网格所在方位；根据所述层数及方位确定路段所属六边形网格。5.根据权利要求1所述的方法，其特征在于，如果一个路段起始点和终点不在同一个六边形网格的同一方向块内，则将路段分割为多条子路段，对位于同一六边形网格和方向块内的子路段计算统一键值。6.根据权利要求5所述的方法，其特征在于，对每条子路段，找到与其最近的参考点从而确定其所在的六边形网格，计算子路段和所述最近的参考点的方向角，确定方向块，对每个子路段得到子路段、子路段所属六边形网格编号、方向块信息组成的三元组；对所有的三元组以相同的归属网格和方向块作为分组依据进行分组，对每个分组获取路段和参考点之间的垂直距离，采用相同的算法获得三元组的键值。7.根据权利要求3所述的方法，其特征在于，所述使用神经网络递归模型索引构建路网的学习索引包括：设置阶段1模型f1对键值数据进行构建模型并存储；设置阶段2模型对六边形网格的数据进行构建模型并存储；设置阶段3模型对子六边形网格的数据进行构建模型并存储。8.根据权利要求1所述的方法，其特征在于，所述键值基于下式计算：其中key
e
为键值，c1，c2和c3为常数，h
i
为路段所属六边形网格的编号；b
j
为方向块编号，为路段到所属六边形网格的垂直距离的向上取整值。
9.根据权利要求8所述的方法，其特征在于，c3＝1；c2取值为六边形边长的位数+1的最小值；c1取值为六边形网格的方向块b
j
数量的位数+1乘以c2。10.利用权利要求1～9任一项所述方法构建的路网空间索引模型进行路段查询的方法，其特征在于，包括：对于给定的gps样本和搜索范围，以gps样本为中心，搜索范围为半径建立搜索圆，获取与搜索圆重叠的六边形网格；确定gps样本所属六边形网格并获取搜索范围内的关联六边形网格，获取与搜索圆相交的六边形网格集合；计算每个六边形网格的参考点到其与搜索圆相交区域的最大距离和最小距离，之后根据键值计算方式得到相交区域的下限键值和上限键值，将下限键值或上限键值输入学习索引中，得到位置搜索边界，基于误差边界确定搜索范围，来检索相交区域内候选路段的键值，获取查询结果。

技术总结
本发明公开了一种基于学习索引的路网空间索引构建方法。基于学习索引技术利用神经网络学习累积分布函数CDF来预测搜索键值的位置，构建由路段起始点与终点所连接的边的路网空间索引。该索引主要分成路段投影，构建空间学习索引和路段查询三部分。先将路段投影到道路网络上，将路段空间四维信息降维成一维键值；再按路段对应的编码值进行排序，对排序后的路段对象及其位置进行学习，建立针对路段对象的学习索引机制；最后在道路网络中对原始的经纬度坐标实现路段查询。本发明既能提高路段搜索的时间效率又可以返回相对准确的结果，为基于位置的服务应用做好前期路段索引路段查询的准备。询的准备。询的准备。


技术研发人员：刘志丹 周荧倩 伍楷舜
受保护的技术使用者：香港科技大学（广州）
技术研发日：2023.03.29
技术公布日：2023/7/22