基于退化四叉树的时空网格索引查询方法和系统

1.本发明涉及时空数据管理及查询技术领域，特别涉及一种基于退化四叉树的时空网格索引查询方法和系统。


背景技术：

2.地理时空数据是指具有地理位置和时间信息的数据，在自然、社会、经济、环境等方面都具有重要的应用价值。随着科技的不断进步和数据获取技术的发展，人们能够更加精准地记录和分析地球上各种现象的变化和演化，例如气候变化、城市扩张、人口流动等。地理时空数据的研究可以帮助人们更好地理解和预测这些变化，为决策制定提供支持，同时也为各种领域的应用提供了数据基础。因此，地理时空数据的研究和应用已经成为当今世界各个领域中备受关注和重视的课题之一。时空轨迹数据蕴含着丰富的时空信息，能动态反映城市的运行状态，可以从中挖掘出高附加值的信息，从而为城市的高效管理、社会流畅运行、社会服务效率的提升提供决策支持。
3.目前，传统以对象为中心数据索引组织方法在时空轨迹数据组织和管理中较为常见，在这类索引中，国内外学者提出了很多经典索引，这些索引大多在空间索引结构体上衍生出三维面向实体的索引，如rt树、3dr树、str树、mtsb树、ph树。这种传统的方法已很难适应高实时性时空轨迹点数据处理，难以实现实时或准实时的业务需求，数据建模方法难以满足大规模轨迹流数据的高效组织与管理需求。
4.目前，基于时空划分的索引方式成为当下地学领域的研究热点之一。基于时空划分的方式是在地球剖分格网上进行扩展的，地球剖分格网以地球的本质空间-球体(面)为空间划分对象，其可以无限细分，但又不改变形状，当细分到一定程度时，可以达到模拟地球的目的。地球剖分格网可作为时空统一数据组织框架，可以将不同来源数据组织到该框架中。同时，格网具有良好的层次性，适用于多分辨率数据的组织、管理与分析，也适用于动态连续的轨迹数据局部聚集特征的表达。
5.基于时空划分的索引方式的主要研究方向有两类，一类是单一索引即时空一体化网格，另一类是对时间和空间单独建立索引，两者分别查询。单一索引具体是针对单一字段建立的索引，该字段即包含空间信息又包含时间信息，通过地理网格编码与时间信息结合得到。单一索引不仅加大了数据存储空间和索引结构空间，还限制了索引的查询效率。基于时空划分的索引方式，程承旗(2019)将轨迹划分为子轨迹并建立四叉树空间索引，并对位于四叉树同一节点的子轨迹，依据其时间信息建立时间索引；实现了在具有较大时间跨度的空间区域上的高效查询，但限制了在时间维度的查询性能。
6.dqg格网是一种变经纬度格网，具有连续剖分层次性、父子单元嵌套性和网格编码连续性等特点。dqg与传统的经纬度geohash相比，不存在高纬度地区格网变形大缺陷，且格网索引效率高。同时dqg网格向高度维进行衍生，在高度维进行二分递归，基于退化八叉树剖分方式探讨dqg_3d格网，并使用编码将三维对象表达为一维格网，在继承二维dqg格网优点的同时，用于表达空中物体在网格空间中的位置。
7.综上所述，为了更好地组织高动态数据和高并发数据，基于时空划分的索引方法是更好的选择。且dqg格网编码的索引适用性更好，可对不同尺度的轨迹数据编码，建立轨迹点/轨迹线的时空索引。


技术实现要素：

8.本发明针对现有技术难以对轨迹数据高效组织和管理，搜索效率慢的问题，提供了一种基于退化四叉树的时空网格索引查询方法和系统。在dqg多尺度的编码结构上，针对时间编码建立时间分区，去除非必要的时间节点，并在时间和空间尺度上采取融合的方法建立时空编码，使用键值存储的方式存储时间编码，从而提出了一种三维时空格网编码结构，并实现了与时空数据快速转换。在数据库postgresql中建立时空分区表，并使用基于退化四叉树的时空格网st_dqg(spatiotemporal degenerate quadtree grids,st_dqg)与b+树索引结合的建立时空索引，使用dqg多尺度节点范围查询进行时空数据检索。st_dqg编码可以实现与时空数据快速转换，且具有多尺度的特性，从而提高了时空轨迹点数据搜索效率。
9.为了实现以上发明目的，本发明采取的技术方案如下：
10.一种基于退化四叉树的时空网格索引查询方法，包括：时空网格编码转换、时空数据网格化和时空轨迹点时空查询。
11.所述时空网格编码转换包括：
12.利用dqg多尺度空间格网结构，将网格单元进行编码。不同尺度的网格单元均通过时空网格编码结构来表示，每个时空编码对应一个网格单元，从而实现了时间和空间的整合。
13.在时空一体的网格结构中采用填充曲线z-ordering算法，按照一定的连接顺序将三维时空格网连接成一条连续的曲线。通过该算法，可以将三维空间转换为一维编码模式，可以通过二分查找即可快速实现地理数据的快速访问。
14.根据生成的时空网格编码和实际时空位置信息，设计出时空网格编码转换算法。该算法根据编码规则将时空位置信息转换为对应的时空网格编码，同时也可以将时空网格编码转换为对应的时空位置信息。在进行时空点数据的查询检索时，可以通过时空网格编码转换算法在数据库中快速地检索出轨迹点数据。
15.所述时空数据网格化包括：
16.空间尺度的格网化：将查询区域在空间上按照一定的空间分辨率划分为一系列网格单元，采用行列号坐标+八分码形式的结构体作为网格单元的标识。网格单元的大小取决于空间分辨率的精度，越小的空间分辨率会划分出越小的网格单元。
17.时间尺度的格网化：将查询区域按照一定的时间分辨率划分为一系列时间段，采用32位无符号整型作为时间尺度的标识。时间尺度的划分可以根据实际数据的特点来确定，比如，一分、一个小时、一天等。
18.时空网格编码集合：将空间尺度和时间尺度的网格划分进行结合，采用时空坐标进行标识，得到完整的时空网格编码集合，并通过z-ordering曲线合并减少时空编码集合数量。在进行时空数据查询时，可以通过该时空网格编码集合进行高效的检索查询，提高查询效率。
19.所述时空轨迹点时空查询包括：
20.将输入的pointm类型转换为时空编码并存储于合适的数据库表，然后对时空轨迹点数据进行等值或时空区域查询，按照时空查询区域网格化方法确定查询范围并查找相应时空表，最后通过数据库范围查询方式检索出满足条件的轨迹点数据。
21.进一步地，所述时空网格编码转换中时空索引结构采用时空信息联合编码，时间编码采用分区键和排序键的设计，具体指分为时空分区键和时空一体化编码，时空分区键由八分体码和时间编码分区键联合确定；时空一体化编码采用morton码，由空间行列号和时间排序键交叉取位得到，并采用标记位的方式将其转换为多尺度编码。时间粒度根据数据大小、采样频率、数据库约束等因素进行计算得出，空间层级根据航线要素分布、存储代价、查询时间等因素确定。空间纬度不仅可以是二维还可以是三维空间，时间编码则采用扩展二分法。
22.进一步地，所述将时空位置信息转换为对应的时空网格编码，包括以下步骤：
23.s11：给定经纬度高度坐标时间信息(l,b,h,t)，根据经纬度与八分码的关系，确定时空单元所对应的八分码octant。
24.s12：根据给定的空间剖分等级level，计算纬度差δb，从而得到行号i。
25.s13：计算给定的空间剖分等级level下i行格元的经度差δl。
26.s14：根据经度差δl和经度l计算列号j。
27.s15：根据空间剖分层级，计算高度差δh并得到层号h。
28.s16：将时间t转换为时间结构体pg_tm tm，并按照时间扩展二分法将其转换为时间编码tcode。
29.s17：根据时间粒度t，将时间编码tcode分为分区键ftcode和排序键ptcode，并将时间分区键和八分体编码结合为时空分区键fst_code，对时间排序键进行变换。
30.s18：将行号i、列号j、层号h、时间排序键ptcode进行交叉取位，得到二进制的时空编码stcode，加入空间剖分层级形成多尺度编码，组合fst_code，时空编码stcode，时间粒度t和时间层级tlevel，从而生成时空结构体stcode_fp64。
31.进一步地，所述将时空网格编码转换为对应的时空位置信息，包括以下步骤：
32.s21：由时空结构体stcode_fp64，得到时间粒度t，时间剖分层级tlevel，并得到空间剖分层级level；
33.s22：根据时空分区键，取出uint32_t类型中最高位为前三位的八分码octant，根据时间粒度t，根据时间编码得到时间分区键ft；
34.s23：将时空编码stcode根据morton码根据查找表的方式解算，求出行号i，列号j，层号h，时间排序键t。根据tlevel和t得到pt；
35.s24：根据空间剖分层级level计算纬差δb，计算中心点纬度b；
36.s25：计算经差δl，计算中心点经度l；
37.s26：计算经差δh，计算中心点经度h；
38.s27：根据八分体码计算实际的经纬度坐标l,b,h；
39.s28：根据t，t和pt，计算时间编码，转成pg_tm,计算时间信息t。
40.进一步地，时空查询区域网格化的具体步骤如下：
41.s31：在空间维度上使用dqg扫描线填充算法进行网格化，将时空查询区域用网格
的形式表示出来，得到时空查询空间区域上的行列号坐标集合(i,j)，实现在限定层级n的单尺度网格化。
42.s32：在时间维度上进行网格化，将时间维度上的时间范围time
min
和time
max
，转换为第tlevel层级上的二进制时间编码tmin和tmax，将时空区域划分为m＝tmax-tmin+1个相同空间区域，即在时间维度上进行等间隔网格化，保证相同时间粒度的数据可以被包含在同一个时空格网中。
43.s33：将查询区域的行列号坐标集合(i,j)和m个时间编码转换为时空格网编码集合(i,j,t)，得到时空查询区域在网格化环境下对应的时空编码，以便于后续的处理。
44.s34：对时空格网编码进行z-ordering曲线聚合，实现在限定层级n0下的合并。将四个格网和四个虚拟格网合并为一个格网，同时剔除掉合并后存在的虚拟格网。将时空格网编码中的高位按照z-ordering曲线排序，直到合并的层级达到n层级为止，得到以n层级为基础的时空查询区域多尺度网格化结果，其中每个格网对应一个固定的层级，其层级范围为[n0,n]。尺度网格用来快速查询时空数据，并对查询结果进行评估和分析。
[0045]
进一步地，所述时空点数据查询检索的具体步骤如下：
[0046]
s41：首先将输入的pointm类型转换为时空编码stcode_fp。然后根据时空编码stcode_fp常量选取合适的数据库表。
[0047]
s42：按照类似于查找点数据的方式进行等值查询，输出查询到的轨迹时空点数据。
[0048]
s43：进行时空区域查询轨迹点数据。例如，查询与时空面状数据包含的轨迹点状数据时，实际上是时间段查询与面状数据的查询。
[0049]
s44：对时空查询区域进行时空网格化，并确定包含待查询时间段的时间粒度t、时间剖分层级tlevel。
[0050]
s45：查找待查询时间段所在年月的父节点，并检索对应的时空表。
[0051]
s46：通过数据库范围查询方式进行时空查询，检索出满足查询条件的轨迹点数据。
[0052]
一种基于退化四叉树的时空网格索引查询系统，该系统能够用于实施上述的一种基于退化四叉树的时空网格索引查询方法，具体的包括：时空网格编码转换模块、时空数据网格化模块和时空轨迹点时空查询模块。
[0053]
时空网格编码转换模块：该模块实现了dqg空间格网结构下的多尺度编码和空间填充曲线z-ordering算法，并利用出时空网格编码转换算法，在时空点数据查询检索时快速确定点数据在时空网格索引中的位置。
[0054]
时空数据网格化模块：该模块实现了空间尺度和时间尺度的格网化方法，并将二者结合得到完整的时空网格编码集合。在时空数据的查询检索中，通过该模块进行高效的检索查询，提高查询效率。
[0055]
时空轨迹点时空查询模块：该模块首先将输入的轨迹点数据转换为时空编码并选取合适的数据库表，然后进行等值或时空区域查询，并通过时空查询区域网格化方法确定查询范围并查找相应的时空表。最终，通过数据库范围查询方式检索出满足条件的轨迹点数据。
[0056]
本发明还公开了一种计算机设备，包括存储器、处理器及存储在存储器上并可在
处理器上运行的计算机程序，所述处理器执行所述程序时实现上述一种基于退化四叉树的时空网格索引查询方法。
[0057]
本发明还公开了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述一种基于退化四叉树的时空网格索引查询方法。
[0058]
与现有技术相比，本发明的优点在于：
[0059]
1.高效性：时空网格索引的采用，可以快速地确定查询范围，避免对整个数据集进行扫描。并且，在时间和空间层面的网格化方法，进一步提高了查询的效率。
[0060]
2.灵活性：在时间和空间网格化时可以根据数据的特点和查询的需求进行设置，灵活度高。使用该方法可以解决一些传统查询方法无法解决的问题，例如，跨越不同时间段和空间范围的的数据查询等。
[0061]
3.数据可视化：时空网格索引提供了一种以网格单元为基础的数据表示方式，也提供了一种数据可视化的方案。可以通过空间网格化分析来实现对数据空间分布和时间特征的可视化。
[0062]
4.兼容性：该方法可以适用于各种类型的时空数据索引化，包括点数据、线数据、面数据及轨迹数据等。
[0063]
5.扩展性：时空网格索引具有良好的可扩展性，可以适应不断变化的数据规模和查询需求。同时，多尺度时空编码优化了数据分配和处理的效率，可以更好地适应大数据量的场景。
[0064]
6.可实现时空数据与时空网格编码的高效转换。可以减少在postgresql数据库中时空信息检索时间。
附图说明
[0065]
图1是本发明实施例时空网格索引查询方法技术路线图；
[0066]
图2是本发明实施例时空网格编码代码结构示意图；
[0067]
图3是本发明实施例格网编码转经纬度高度时间流程图；
[0068]
图4是本发明实施例是时空查询区域划分为多个时间段区域示意图；
[0069]
图5是本发明实施例轨迹点查询流程图。
具体实施方式
[0070]
为使本发明的目的、技术方案及优点更加清楚明白，以下根据附图并列举实施例，对本发明做进一步详细说明。
[0071]
本发明的一种基于退化四叉树的时空网格索引查询方法(st_dqg时空网格索引查询)包括时空格网编码结构和编码解码算法、时空查询区域格网化方式、时空轨迹点时空查询三个部分。时空格网编码是基于dqg空间格网多尺度编码结构，发展出一种基于空间填充曲线z-ordering的时空一体化格网组织方法，并在此基础上设计了时空数据与时空格网的快速转换算法。时空查询区域的网格化是进行数据时空查询的基础，将时空查询区域分为空间尺度的格网化和时间尺度的格网化，并最终合并转换为时空网格编码集合，从而利用时空编码计算与查询方法，以提高时空查询的效率。时空轨迹点时空查询则是介绍了在模拟出来的北京时空人流轨迹点数据上，通过建立时空分区表，初次实现对不同时空轨迹点
数据分类，然后采取跨层级退化四叉树索引和b+树对时空编码构建索引，并采取多尺度化方式，以此来验证本发明方法的高效性。图1描述了基于st_dqg时空格网索引查询技术路线。
[0072]
时空网格编码转换
[0073]
时空索引结构采用时空信息联合编码，在mls3索引的基础之上进行一系列更改：时间编码按照如表1所示进行分割，分为分区键和排序键。最优时空层级时间粒度的确定将根据采样频率和数据大小，以及数据库的约束计算而得。最优空间层级确定顾及航线要素的分布，存储代价和查询时间。
[0074]
其中，通过mls3索引[58]扩展而成，时间编码采用扩展二分法，并按照如表3.3所示进行分割，分为时间分区键和时间排序键，空间码采用dqg_3d格网编码或者二维dqg格网编码。时空格网索引包括时空分区键，时空一体化编码两个部分。时空分区键由八分体码和时间编码分区键联合确定；时空一体化编码stcode由时间编码和空间信息在空间层级level上的编码组成。整体的时空编码数据结构如图2所示。
[0075]
表1时间信息编码
[0076][0077]
图2中，stcode表示3d或者4d的时空编码，level表示时间剖分层级，tlevel表示时间粒度，ftimecode表示时间编码的分区键+八分码。在相同场景中，变化的是时空编码和时间分区键。
[0078]
经纬度高度时间转格网编码算法
[0079]
对于给定时空格网单元的经纬度时间其转换为时空网格编码的基本原理：
[0080]
步骤1:给定经纬度高度坐标时间信息(l,b,h,t),根据经纬度坐标信息，根据经纬度与八分码的关系，确定时空单元所对应的八分码octant；
[0081]
步骤2:根据给定的空间剖分等级level，由公式1计算纬差δb，则行号i计算方法；
[0082][0083]
式中，为向上取整运算
[0084]
步骤3:计算给定的空间剖分等级level下i行格元的经差δl：
[0085]
δl＝log2(i+1)+1
ꢀꢀꢀꢀ
(2)
[0086]
式中，log2()为以2为底的对数
[0087]
步骤4:根据经差δl和经度l计算列号j；
[0088][0089]
步骤5:根据空间剖分层级，计算高差δh并计算层号h；
[0090][0091]
步骤6:时间t(double类型)转成时间结构体pg_tm tm,按照时间扩展二分法，转成时间编码tcode
[0092]
tcode＝y＜＜26+m＜＜22+d＜＜17+h＜＜12+m＜＜6+ss
ꢀꢀꢀꢀ
(5)
[0093]
式中，y表示年，m表示月，d表示日，h表示时，m表示分，s表示秒。
[0094]
步骤7:根据时间粒度t，按照表1将时间编码tcode分为分区键ftcode和排序键ptcode，其中时间分区键和八分体编码结合为时空分区键fst_code，时间排序键进行变换。
[0095]
ptcode＝ptcode＞＞(32-tlevel))
ꢀꢀꢀꢀ
(6)
[0096]
步骤8:将行号i，列号j，层号h，时间排序键ptcode，进行交叉取位，得到二进制的时空编码stcode，按照公式7加入空间剖分层级形成多尺度编码，组合fst_code，时空编码stcode,时间粒度t和时间层级tlevel，生成时空结构体stcode_fp64。
[0097]
stcode＝stcode＜＜(63-2
×
level)+1ull＜＜(63-2
×
level))
ꢀꢀꢀꢀ
(7)
[0098]
格网编码转经纬度高度时间算法
[0099]
对于给定一个时空编码其转换为时空信息的流程图如图3所示，具体步骤如下：
[0100]
步骤1:由时空结构体stcode_fp64，得到时间粒度t，时间剖分层级tlevel，按照表1算法的方式得到空间剖分层级level；
[0101]
步骤2:根据时空分区键，取出uint32_t类型中最高位为前三位的八分码octant，根据时间粒度t，按照表1得到时间分区键ft；
[0102]
步骤3:将时空编码stcode根据morton码根据查找表的方式解算，求出行号i，列号j，层号h，时间排序键t。根据tlevel和t得到pt；
[0103]
步骤4：根据空间剖分层级level按照公式1计算纬差δb，并按照公式9计算中心点纬度b；
[0104]
b＝(j+0.5)
×
δb
ꢀꢀꢀꢀ
(9)
[0105]
步骤5:根据公式8计算经差δl，计算中心点经度l；
[0106]
l＝(i+0.5)
×
δl
ꢀꢀꢀꢀ
(8)
[0107]
步骤6:根据公式10计算经差δh，计算中心点经度h；
[0108]
h＝(h+0.5)
×
δh
ꢀꢀꢀꢀ
(10)
[0109]
步骤7:根据八分体码按照公式计算实际的经纬度坐标l,b,h；
[0110]
步骤8:根据t，t和pt，计算时间编码，转成pg_tm,计算时间信息t(double类型)。
[0111]
时空查询区域网格化
[0112]
本节提出一种基于退化四叉树的时空查询区域网格化的方法，旨在提高时空区域查询的效率。该方法的主要思路是：
[0113]
步骤1:在空间维度对时空查询区域使用dqg扫描线填充算法网格化，得到时空查
询空间区域上的行列号坐标集合(i,j)，实现area的在限定层级n的单尺度网格化。
[0114]
步骤2:时间维度上网格化具体是将时间维度上的时间范围time
min
和time
max
，转换为第tlevel层级上的二进制时间编码tmin和tmax，将时空区域划分为其中，m＝tmax-tmin+1个相同空间区域area。
[0115]
步骤3:最后将查询区域的行列号坐标集合(i,j)和m个时间编码转换为时空格网编码集合(i,j,t)。
[0116]
步骤4:时空格网化后实现在限定层级n0下(n0《n)z-ordering曲线聚合。在z曲线合并中主要工作为将八个格网合并为4个格网，4个格网和4个虚拟格网合并为1个格网，并剔除掉合并后存在的虚拟格网，得到以n层级为基础的时空查询区域多尺度网格化结果，其层级范围为[n0,n]。
[0117]
如图4所示，通过以上的时空格网化方法，实现了用更少的时空格网表达时空查询区域，从而减少编码查询次数，提高了数据的时空查询效率。
[0118]
时空点数据查询检索
[0119]
postgis的点类型支持多维的类型有pointz、pointm和pointzm。本发明中选取postgis的pointm作为三维时空数据的存储数据结构。时空轨迹点数据的时空索引建立只需将数据表中geometry字段，通过扩展插件函数将经纬度时间转成时空格网编码，将stcode_fp64结构体中的stcode建立b+树等一维索引，即可建立一维时空编码索引。如果轨迹点数据的时空编码stcode_fp64的其他变量一致，结构体其他变量作为表中的常量存储，否则按照结构体中常量对数据采取分表方式(注:前提数据量足够大)，并进行表映射，stcode_fp64其他变量存储与config表中。config系统表中类型如下：
[0120][0121]
其中，fqcode表示时间分区键和八分体码结合码，tlevel表示时间剖分层级，t表示时间粒度。
[0122]
时空轨迹点数据查询流程如下：
[0123]
步骤1:首先将输入的pointm类型转换为时空编码stcode_fp。然后根据的时空编码stcode_fp常量选取合适的数据库表，
[0124]
步骤2:然后按照类似于查找点数据的方式进行等值查询，输出查询到的轨迹时空点数据。
[0125]
步骤3:时空区域查询轨迹点数据，如查询与时空面状数据包含的轨迹点状数据时实际上是时间段查询与面状数据的查询，
[0126]
步骤3:首先按照上节进行时空查询区域网格化方法，确定包含待查询时间段的时
间粒度t，时间剖分层级tlevel，
[0127]
步骤4:查找待查询时间段年月的父节点，然后再查找对应的时空表，
[0128]
步骤5:通过数据库范围查询方式进行时空查询。
[0129]
实验中轨迹点数据的时空编码结构体的其他变量都是一致的。该索引将高维的时空索引转换为一维编码索引，有利于实现空间不同尺度与时间尺度对应，有利于实现基于st_dqg时空格网的轨迹点数据的高效时空查询。
[0130]
时空轨迹点数据查询流程图如图5所示；
[0131]
实验数据：以北京市作为研究范围，以北京市2020年6月以前的poi点为模拟点位，数据从开源的百度地图api接口获取，模拟出人流轨迹点数据，存储轨迹点数据表结构的参考模式如表3所示。其中表中_id为一条轨迹点记录的标识，poi_id为关联表北京市poi点的标识，关联表表结构包括存储空间数据geometry、lon经度、lat纬度，time为表示为到达的poi轨迹地点时间，数据表达类型是timestamp，attributes表示的该条记录里面的属性信息。设计两种查询：时空点位查询和时空查询区域，时空点位查询快速查询在某一时间特定点位人员_id，时空区域查询快速查询在某一时间段内特定区域内人员_id。
[0132]
表3时空轨迹点数据结构表
[0133][0134][0135]
为验证查询时空网格轨迹点的时空索引与查询方法的有效性，设计北京市轨迹点的时空查询效率对比实验，其具体步骤如下：
[0136]
步骤1:以搭建的postgre平台为基础，按照表3的格式建立用于st_dqg，独立查询方法的2个轨迹点数据表，表名分别为tddta、tddtb。
[0137]
步骤2：将模拟的实验数据(5449989个轨迹点)分别导入表名为tddta、tddtb中，并计算表中tddta中每个点的时空编码存储于字段stcode，该过程中，poi空间数据网格基础层级取值为21，时间编码基础层级取22，该层级的时空格网的空间分辨率约为5m
×
5m，时间分辨率为1小时。能够较好满足poi时空轨迹点时空编码索引的数据查询应用需求；
[0138]
步骤3：参照时空索引建立方法，以此为基础，建立st_dqg时空格网索引；
[0139]
步骤4:基于两种时空编码索引，利用两组时空轨迹点数据，分别进行轨迹点的时空点位查询实验，并统计st_dqg、独立查询方法的对于每组不同数据量的平均查询耗时，其对比结果如表4所示。
[0140]
步骤5:基于本发明提出的时空格网索引，实验中通过两组时空查询方式，分别进行轨迹点的时空查询实验，轨迹点的时空区域查询实验，然后统计st_dqg格网和独立查询方法的对于每组多边形时空查询区域的平均查询耗时，其对比结果如表5所示。
[0141]
表4时空轨迹点查询对比表
[0142][0143]
表5时空区域查询效率对比表
[0144][0145]
本发明的时空轨迹点查询策略效率高于单独查询策略。为验证本发明的时空格网的有效性，共设计两组实验。该实验场景中轨迹点的时空查询实验表明与单独查询相比，本发明的查询效率平均提升约三倍。该实验中轨迹点的时空区域查询实验，其结果表明：与单独索引相比，本发明方法的时空区域查询效率平均提升约三倍。
[0146]
本发明再一个实施例中，提供了一种基于退化四叉树的时空网格索引查询系统，该系统能够用于实施上述的一种基于退化四叉树的时空网格索引查询方法，具体的包括：时空网格编码转换模块、时空数据网格化模块和时空轨迹点时空查询模块。
[0147]
时空网格编码转换模块：该模块实现了dqg空间格网结构下的多尺度编码和空间填充曲线z-ordering算法，并利用出时空网格编码转换算法，在时空点数据查询检索时快速确定点数据在时空网格索引中的位置。
[0148]
时空数据网格化模块：该模块实现了空间尺度和时间尺度的格网化方法，并将二者结合得到完整的时空网格编码集合。在时空数据的查询检索中，通过该模块进行高效的检索查询，提高查询效率。
[0149]
时空轨迹点时空查询模块：该模块将输入的点数据转换为时空编码并选取合适的数据库表，然后进行等值或时空区域查询，并通过时空查询区域网格化方法确定查询范围并查找相应的时空表。最终，通过数据库范围查询方式检索出满足条件的轨迹点数据。
[0150]
本发明再一个实施例中，提供了一种终端设备，该终端设备包括处理器以及存储器，所述存储器用于存储计算机程序，所述计算机程序包括程序指令，所述处理器用于执行所述计算机存储介质存储的程序指令。处理器可能是中央处理单元(central processing unit，cpu)，还可以是其他通用处理器、数字信号处理器(digital signal processor、dsp)、专用集成电路(application specific integrated circuit，asic)、现成可编程门阵列(field-programmable gatearray，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等，其是终端的计算核心以及控制核心，其适于实现一条或一条以上指令，具体适于加载并执行一条或一条以上指令从而实现相应方法流程或相应功能；本发明实施例所述的处理器可以用于一种基于退化四叉树的时空网格索引查询方法的操作。
[0151]
本发明再一个实施例中，本发明还提供了一种存储介质，具体为计算机可读存储介质(memory)，所述计算机可读存储介质是终端设备中的记忆设备，用于存放程序和数据。可以理解的是，此处的计算机可读存储介质既可以包括终端设备中的内置存储介质，当然也可以包括终端设备所支持的扩展存储介质。计算机可读存储介质提供存储空间，该存储空间存储了终端的操作系统。并且，在该存储空间中还存放了适于被处理器加载并执行的
一条或一条以上的指令，这些指令可以是一个或一个以上的计算机程序(包括程序代码)。需要说明的是，此处的计算机可读存储介质可以是高速ram存储器，也可以是非不稳定的存储器(non-volatile memory)，例如至少一个磁盘存储器。
[0152]
可由处理器加载并执行计算机可读存储介质中存放的一条或一条以上指令，以实现上述实施例中有关一种基于退化四叉树的时空网格索引查询方法的相应步骤。
[0153]
本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、cd-rom、光学存储器等)上实施的计算机程序产品的形式。
[0154]
本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0155]
这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0156]
这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0157]
本领域的普通技术人员将会意识到，这里所述的实施例是为了帮助读者理解本发明的实施方法，应被理解为本发明的保护范围并不局限于这样的特别陈述和实施例。本领域的普通技术人员可以根据本发明公开的这些技术启示做出各种不脱离本发明实质的其它各种具体变形和组合，这些变形和组合仍然在本发明的保护范围内。

技术特征：
1.一种基于退化四叉树的时空网格索引查询方法，其特征在于，包括：时空网格编码转换、时空数据网格化和时空轨迹点时空查询；所述时空网格编码转换包括：利用dqg空间格网结构，将网格单元按多尺度进行编码；利用dqg多尺度空间格网结构，将网格单元进行编码；不同尺度的网格单元均通过时空网格编码结构来表示，每个时空网格编码对应一个网格单元，从而实现了时间和空间的整合；在时空一体的网格结构中采用填充曲线z-ordering算法，按照一定的连接顺序将三维时空格网连接成一条连续的曲线；通过填充曲线z-ordering算法将三维空间转换为一维编码模式；根据生成的时空网格编码和实际时空位置信息，设计出时空网格编码转换算法；时空网格编码转换算法根据编码规则将时空位置信息转换为对应的时空网格编码，或者将时空网格编码转换为对应的时空位置信息；所述时空数据网格化包括：空间尺度的格网化：将查询区域在空间上按照一定的空间分辨率划分为一系列网格单元，采用行列号坐标+八分码形式的结构体作为网格单元的标识；时间尺度的格网化：将查询区域按照一定的时间分辨率划分为一系列时间段，采用32位无符号整型作为时间尺度的标识；时空网格编码集合：将空间尺度和时间尺度的网格划分进行结合，采用时空坐标进行标识，得到完整的时空网格编码集合，并通过z-ordering曲线合并减少时空编码集合数量；所述时空轨迹点时空查询包括：将输入的pointm类型转换为时空编码并选取合适数据库表，然后对时空点数据进行等值或时空区域查询，按照时空查询区域网格化方法确定查询范围并查找相应时空表，最后通过数据库范围查询方式检索出满足条件的轨迹点数据。2.根据权利要求1所述的一种基于退化四叉树的时空网格索引查询方法，其特征在于：所述时空网格编码转换中时空索引结构采用时空信息联合编码，时间编码采用分区键和排序键的设计，具体指分为时空分区键和时空一体化编码，时空分区键由八分体码和时间编码分区键联合确定；时空一体化编码采用morton码，由空间行列号和时间排序键交叉取位得到，并采用标记位的方式将其转换为多尺度编码；时间粒度根据数据大小、采样频率、数据库约束等因素进行计算得出，空间层级根据航线要素分布、存储代价、查询时间等因素确定；空间纬度不仅可以是二维还可以是三维空间，时间编码则采用扩展二分法。3.根据权利要求1所述的一种基于退化四叉树的时空网格索引查询方法，其特征在于：所述将时空位置信息转换为对应的时空网格编码，包括以下步骤：s11：给定经纬度高度坐标时间信息(l,b,h,t)，根据经纬度与八分码的关系，确定时空单元所对应的八分码octant；s12：根据给定的空间剖分等级level，计算纬度差δb，从而得到行号i；s13：计算给定的空间剖分等级level下i行格元的经度差δl；s14：根据经度差δl和经度l计算列号j；s15：根据空间剖分层级，计算高度差δh并得到层号h；s16：将时间t转换为时间结构体pg_tm tm，并按照时间扩展二分法将其转换为时间编码tcode；
s17：根据时间粒度t，将时间编码tcode分为分区键ftcode和排序键ptcode，并将时间分区键和八分体编码结合为时空分区键fst_code，对时间排序键进行变换；s18：将行号i、列号j、层号h、时间排序键ptcode进行交叉取位，得到二进制的时空编码stcode，加入空间剖分层级形成多尺度编码，组合fst_code，时空编码stcode，时间粒度t和时间层级tlevel，从而生成时空结构体stcode_fp64。4.根据权利要求1所述的一种基于退化四叉树的时空网格索引查询方法，其特征在于：所述将时空网格编码转换为对应的时空位置信息，包括以下步骤：s21：由时空结构体stcode_fp64，得到时间粒度t，时间剖分层级tlevel，并得到空间剖分层级level；s22：根据时空分区键，取出uint32_t类型中最高位为前三位的八分码octant，根据时间粒度t，根据时间编码得到时间分区键ft；s23：将时空编码stcode根据morton码根据查找表的方式解算，求出行号i，列号j，层号h，时间排序键t；根据tlevel和t得到pt；s24：根据空间剖分层级level计算纬差δb，计算中心点纬度b；s25：计算经差δl，计算中心点经度l；s26：计算经差δh，计算中心点经度h；s27：根据八分体码计算实际的经纬度坐标l,b,h；s28：根据t，t和pt，计算时间编码，转成pg_tm,计算时间信息t。5.根据权利要求1所述的一种基于退化四叉树的时空网格索引查询方法，其特征在于：时空查询区域网格化的具体步骤如下：s31：在空间维度上使用dqg扫描线填充算法进行网格化，将时空查询区域用网格的形式表示出来，得到时空查询空间区域上的行列号坐标集合(i,j)，实现在限定层级n的单尺度网格化；s32：在时间维度上进行网格化，将时间维度上的时间范围time
min
和time
max
，转换为第tlevel层级上的二进制时间编码tmin和tmax，将时空区域划分为m＝tmax-tmin+1个相同空间区域，即在时间维度上进行等间隔网格化，保证相同时间粒度的数据可以被包含在同一个时空格网中；s33：将查询区域的行列号坐标集合(i,j)和m个时间编码转换为时空格网编码集合(i,j,t)，得到时空查询区域在网格化环境下对应的时空编码；s34：对时空格网编码进行z-ordering曲线聚合，实现在限定层级n0下的合并；将四个格网和四个虚拟格网合并为一个格网，同时剔除掉合并后存在的虚拟格网；将时空格网编码中的高位按照z-ordering曲线排序，直到合并的层级达到n层级为止，得到以n层级为基础的时空查询区域多尺度网格化结果，其中每个格网对应一个固定的层级，其层级范围为[n0,n]。6.根据权利要求1所述的一种基于退化四叉树的时空网格索引查询方法，其特征在于：所述时空点数据查询检索的具体步骤如下：s41：首先将输入的pointm类型转换为时空编码stcode_fp；然后根据时空编码stcode_fp常量选取合适的数据库表；s42：按照类似于查找点数据的方式进行等值查询，输出查询到的轨迹时空点数据；
s43：进行时空区域查询轨迹点数据；s44：对时空查询区域进行时空网格化，确定包含待查询时间段的时间粒度t、时间剖分层级tlevel；s45：查找待查询时间段所在年月的父节点，并检索对应的时空表；s46：通过数据库范围查询方式进行时空查询，检索出满足查询条件的轨迹点数据。7.一种基于退化四叉树的时空网格索引查询系统，其特征在于：该系统能够用于实施上述的一种基于退化四叉树的时空网格索引查询方法，具体的包括：时空网格编码转换模块、时空数据网格化模块和时空轨迹点时空查询模块；时空网格编码转换模块：该模块实现了基于退化四叉树的时空格网结构下的多尺度编码和填充曲线z-ordering算法，并利用出时空网格编码转换算法，在时空点数据查询检索时快速确定点数据在时空网格索引中的位置；时空数据网格化模块：该模块实现了空间尺度和时间尺度的格网化方法，并将二者结合得到完整的时空网格编码集合；在时空数据的查询检索中，通过该模块进行高效的检索查询，提高查询效率；时空轨迹点时空查询模块：该模块将输入的点数据转换为时空编码并选取合适的数据库表，然后进行等值或时空区域查询，并通过时空查询区域网格化方法确定查询范围并查找相应的时空表；最终，通过数据库范围查询方式检索出满足条件的轨迹点数据。8.一种计算机设备，其特征在于：包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述一种基于退化四叉树的时空网格索引查询方法。9.一种计算机可读存储介质，其特征在于：其上存储有计算机程序，该程序被处理器执行时实现上述一种基于退化四叉树的时空网格索引查询方法。

技术总结
本发明公开了一种基于退化四叉树的时空网格索引查询方法和系统，包括：通过时空网格编码转换将时空位置信息转换为对应的时空网格编码，并通过空间尺度和时间尺度的格网化方法对两个尺度分别格网化然后合并得到完整的时空网格编码集合。在进行时空轨迹点查询时，利用时空查询区域网格化方法确定时空查询范围，查找相应的时空表，并通过数据库范围查询方式检索出满足条件的轨迹点数据。本发明的优点是：具有高效性、灵活性、数据可视化、兼容性和扩展性等优点，可实现时空数据与时空网格编码的高效转换，可减少在postgresql数据库中时空信息检索时间。空信息检索时间。空信息检索时间。


技术研发人员：赵学胜 黄晓刚 李靖 吕子川
受保护的技术使用者：中国矿业大学（北京）
技术研发日：2023.07.13
技术公布日：2023/9/20