CN114116925B 一种时空数据的查询方法及相关装置 （华为技术有限公司）

本申请实施例提供一种时空数据的查询方的索引所指向的数据和内部网格的索引所指向空数据查询进行区分，提高了查询结果的精准2将所述边界网格的索引所指向的数据和所述内部网格的索引所指向的数据作为查询根据所述边界网格，生成边界网格范围字典，所述边界网将第一边界坐标点所在的网格确定为第一边界网格，将第二边界对所述第一边界坐标点和所述第二边界坐标点之间的所述边界坐标点所在的网格填若目标斜率的绝对值大于0且不大于1，将与所述第一边界网格在所述第一边界网格所在行中，将所述第一边界网格所在列若所述目标斜率的绝对值大于1，将与所述第一边界网格的列号相邻的列号确定为所在所述第一边界网格所在列中，将所述第一边界网格所在行3在所述边界网格的第一行号不为所述第一边界坐标点所在的行号且不为所述第二边所述第一行号对应的网格列号确定为所述边界网格范围字典中的键或，在所述边界网格的第一列号不为所述第一边界坐标点边界坐标点所在的列号的情况下，将所述第一列号确定为所述边界网格范围字典中的键，将所述第一列号对应的网格行号确定为所述边界网格范围字典中的键在所述第一行号为所述第一边界坐标点所在的行号且/或为所述第二边界坐标点所在或，在所述第一列号为所述第一边界坐标点所在的列号且/或为所述第二边界坐标点述第一列号对应的网格行中的相邻两行的行号确定为所述边界网格范围字典中的键对应在所述第一行号为所述第一边界坐标点所在的行号且/或为所述第二边界坐标点所在或，在所述第一列号为所述第一边界坐标点所在的列号且/或为所述第二边界坐标点对所述候选网格填充树缺失的叶子节点和中间节点填充，得到候选内选内部网格为所述候选网格填充树缺失的叶子节点和4若所述候选内部网格的行号和列号包含于所述边界网格范围字典在所述边界网格范围字典中的键为所述候选内部网格的行号的若所述候选内部网格的行号和/或列号不包含于所述边界网格范围字典中的键值，不将所述边界网格和所述内部网格转换为目标网格，所述目标网格的对所述目标网格的索引排序，得到索引区间，所述索引区间包含述内部网格为不包含所述边界坐标点的网格；所述边界网格的编码层级和/或所述内部网查询单元，用于将所述边界网格的索引所指向的数据和填充单元，用于根据所述边界网格范围字典对所述空间区域的非边界部分填点所在的网格确定为第一边界网格，将第二边界坐标点所在的网格确定为第二边界网格，所述第一边界坐标点和所述第二边界坐标点为位于所述空间区域边界的两个不同的坐标所述填充单元，还用于对所述第一边界坐标点和所述第5对值大于0且不大于1，将与所述第一边界网格的行号相邻的行号确定为边界交点的行号，标斜率为所述第一边界坐标点和所述第二边界坐标点所在的目标所述确定单元，还用于根据所述边界交点的行号和所述目标直线所述填充单元，具体用于在所述第一边界网格所在行中，将所述第一边界网格所所述确定单元，还用于根据所述边界交点的列号和所述目标直线所述填充单元，具体还用于在所述第一边界网格所在列中，将所述第一边界的第一行号不为所述第一边界坐标点所在的行号且不为所述第二边界坐标点所在的行号或，还用于在所述边界网格的第一列号不为所述第一边第一行号对应的网格列中的临近两列之间的任意网格的中心坐标点位于所述空间区域内，临近两列的列号确定为所述边界网格范围字典中的或，还用于在所述第一列号为所述第一边界坐标点所所述第一列号对应的网格行中的相邻两行的行号确定为所述边界网格范围字典中的键对第一行号对应的网格列中的临近两列之间的任意网格的中心坐标点不位于所述空间区域6或，还用于在所述第一列号为所述第一边界坐标点所所述填充单元，还用于对所述候选网格填充树缺失的叶子节点和中间节点填所述确定单元，还用于根据所述边界网格范围字典筛选所述候选内部网格的行号和/或列号不包含于所述边界网格范围字典中的键值，不将所述候选内部转换单元，用于将所述边界网格和所述内部网格转换为目标网格，所述7空数据的空间区域查询指的是针对用户输入的空间区域(通常是由多个经纬度坐标点构成查询方法从数据库包含的海量的时空数据中查询落入上述特定的空间区域的时空数据显不包含所述边界坐标点的网格；所述边界网格的编码层级和/或所述内部网格的编码层级[0008]将所述边界网格的索引所指向的数据和所述内部网格的索引所指向的数据作为8[0017]对所述第一边界坐标点和所述第二边界坐标点之间的所述边界坐标点所在的网为边界网格，该第一边界坐标点和第二边界坐标点为空间区域的两个不同的边界坐标点。间的边界区域进行网格填充，可以得到一个包含了若干个彼此相邻的边界网格的网格序9界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方式。[0025]若所述目标斜率的绝对值大于1，将与所述第一边界网格的列号相邻的列号确定界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方式。边界交点，该边界交点与网格线相交且为第一边界坐标点和第二边界坐标点之间的坐标界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方式。[0033]在所述边界网格的第一行号不为所述第一边界坐标点所在的行号且不为所述第二边界坐标点所在的行号的情况下，将所述第一行号确定为所述边界网格范围字典中的[0037]在所述第一行号为所述第一边界坐标点所在的行号且/或为所述第二边界坐标点述第一行号对应的网格列中的临近两列的列号确定为所述边界网格范围字典中的键对应[0038]或，在所述第一列号为所述第一边界坐标点所在的列号且/或为所述第二边界坐中心坐标点位于所述空间区域内，将所述第一列号确定为所述边界网格范围字典中的键，将所述第一列号对应的网格行中的相邻两行的行号确定为所述边界网格范围字典中的键上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号的情况下，若第号且/或为上述第二边界坐标点所在的列号的情况下，若该第一列号对应的网格行中的临[0041]在所述第一行号为所述第一边界坐标点所在的行号且/或为所述第二边界坐标点[0042]或，在所述第一列号为所述第一边界坐标点所在的列号且/或为所述第二边界坐一行号为上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号的情况列号为上述第一边界坐标点所在的列号且/或为上述第二边界坐标点所在的列号的情况列号对应的网格行的不同情况而定，若第一列号对应的网格行中除了上述临近两行之外，述候选内部网格为所述候选网格填充树缺失的叶子节点准；且相对于基于四叉树网格索引自顶而下的逐级递归四分空间区域的常规网格化方法，的结果更为精准，从而使内部网格的索引所指向的数据作为最后的查询结果也更为精准，[0057]若所述候选内部网格的行号和/或列号不包含于所述边界网格范围字典中的键体为根据上述候选内部网格的行号和列号判断候选内部网格是否包含于边界网格范围字该候选内部网格排除在内部网格的集合之外。上述筛选候选内部网格得到内部网格的方网格的编码层级为候选网格填充树的最高索引层级；目标网格的索引可以形成索引区间边界网格为包含边界坐标点的网格，所述边界坐标点为位于所述空间区域的边界的坐标[0073]填充单元，用于根据所述边界网格范围字典对所述空间点所在的网格确定为第一边界网格，将第二边界坐标点所在的网格确定为第二边界网格，所述第一边界坐标点和所述第二边界坐标点为位于所述空间区域边界的两个不同的坐标为边界网格，该第一边界坐标点和第二边界坐标点为空间区域的两个不同的边界坐标点。间的边界区域进行网格填充，可以得到一个包含了若干个彼此相邻的边界网格的网格序对值大于0且不大于1，将与所述第一边界网格的行号相邻的行号确定为边界交点的行号，标斜率为所述第一边界坐标点和所述第二边界坐标点所在的目标界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方式。界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方式。边界交点，该边界交点与网格线相交且为第一边界坐标点和第二边界坐标点之间的坐标界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方式。的第一行号不为所述第一边界坐标点所在的行号且不为所述第二边界坐标点所在的行号第一行号对应的网格列中的临近两列之间的任意网格的中心坐标点位于所述空间区域内，临近两列的列号确定为所述边界网格范围字典中的上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号的情况下，若第号且/或为上述第二边界坐标点所在的列号的情况下，若该第一列号对应的网格行中的临第一行号对应的网格列中的临近两列之间的任意网格的中心坐标点不位于所述空间区域一行号为上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号的情况列号为上述第一边界坐标点所在的列号且/或为上述第二边界坐标点所在的列号的情况列号对应的网格行的不同情况而定，若第一列号对应的网格行中除了上述临近两行之外，[0100]所述填充单元，还用于对所述候选网格填充树缺失的叶得到候选内部网格，所述候选内部网格为所述候选网格填充树缺失的叶子节点和中间节准；且相对于基于四叉树网格索引自顶而下的逐级递归四分空间区域的常规网格化方法，的结果更为精准，从而使内部网格的索引所指向的数据作为最后的查询结果也更为精准，内部网格的行号和/或列号不包含于所述边界网格范围字典中的键值，不将所述候选内部体为根据上述候选内部网格的行号和列号判断候选内部网格是否包含于边界网格范围字该候选内部网格排除在内部网格的集合之外。上述筛选候选内部网格得到内部网格的方网格的编码层级为候选网格填充树的最高索引层级；目标网格的索引可以形成索引区间[0141]本申请实施例提供了一种时空数据的查询方法，为了更清楚地描述本申请的方多种基于R树或四叉树的时空索引技术，这样建立索引是为了减少建立索引占据的空间及[0146]另一方面，对于用户发起的空间区域查询请求(该空间区域通常是由经纬度坐标分布式集群规模等。而步骤(1)的性能更多体现在查询过程中所运用的算法层面的性能和索引构建方法为基于空间分割的索引结构。其基本原理是将空间分割为多尺度层级的网待查询的空间区域的外包网格，该外包网格在满足可完全包含待查询的空间区域的前提新生成的网格与待查询的空间区域的拓扑关系，如果与待查询空间区域相交则进一步剖服务器获取待查询的空间区域(1)。然后确定完全包含待查询的空间区域(1)的外包网格分，即基于四叉树网格索引，自顶而下逐级递归四分外包网格(2)，可得到新的网格(3)、查询的空间区域(1)进行拓扑关系判断，可知网格(8)为完全不在待查询的空间区域(1)内格(7)和网格(10)均为部分在待查询的空间区域(1)内部，故还需对网格(7)和网格(10)继[0150]上述图1c中的网格与待查询的空间区域的拓扑关系基于经纬度单点与空间区域别对应于低层级网格和高层级网格)在不同层级存在冗余计算情况(即父网格与子网格相可以有效满足对空间区域精准查询的需求。在对该新的时空数据查询方法进行说明之前，首先对该新的时空数据查询方法所应用的系统架构进行[0152]请参阅图2a，图2a为本申请实施例提供的一种时空数据查询系统的架构示意网络连接的服务器获得待查询的空间区域的信息后，将根据该待查询的空间区域[0159]首先，服务器将待查询的空间区域的边界包含的经纬度标点所在的行号且不为上述第二边界坐标点所在的行号且不为上述第N边界坐标点所在的列号不为上述第一边界坐标点所在的列号且不为上述第二边界坐标点所在的列号且不为第一列号为键所对应的值是经过祛冗余后的行上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号且/或为上述第N意网格的中心坐标点位于空间区域内，则将该第一行号确定为边界网格范围字典中的键，并将该第一行号对应的网格列中的临近两列的列号确定为上述边界网格范围字典中的键号且/或为上述第二边界坐标点所在的列号且/或为上述第N边界坐标点所在的列号的情况上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号且/或为上述第N一边界坐标点所在的列号且/或为上述第二边界坐标点所在的列号且/或为上述第N边界坐[0173]步骤303：将上述边界网格的索引所指向的数据和上述内部网格的索引所指向的[0174]由上述步骤202可得到空间区域的边界网格和内部网格，再将上述边界网格的索引所指向的数据和上述内部网格的索引所指向的数据作为空间区域的时空数据的查询结[0176]请参阅图4a，图4a为本申请实施例提供的另一种时空数据查询方法的流程示意[0178]服务器接收到用户发起的空间区域查询请求后，会获得待查询的空间区域的信BCDDEE洁，本实施例可将经纬度坐标点A和经纬度坐标点B分别作为第一边界坐标点A和第二边界库中构建的全球离散四叉树网格的索引层级为L，则本实施例中得到的边界网格的网格层格编码，网格编码转换方式根据时空数据库采用的索引网格系统原理的不同而有所差异。ROW=llata/180x2"」和列号col=llona/360x2N],其中，符号表示向下取整。再将叉运算，可得到第一边界坐标点A对应的2L位的二进制网格编码(GS)2。例如，(Row)2=[0181]步骤402：按序依次将上述第一边界坐标点和上述第二边界坐标点之间的边界部[0190]由上述步骤401中的边界网格化方法可得到第一边界网格和第二边界网格，由上述步骤402中通过对第一边界坐标点和第二边界坐标点之间的边界部分进行网格填充的方[0192]可选的，上述步骤402中对所有相邻边界坐标点之间的边界部分进行网格填充的[0193]请参阅图5a，图5a为本申请实施例提供的又一种时空数据查询方法的流程示意[0199]由上述步骤501可得到边界网格集中的边界网格的行列编号，在本步骤中将根据范围字典中的键，将该第一列号对应的网格行号确定为边界网格范围字典中的键对应的一列号对应的网格行中的临近两行之间的任意网格的中心坐标点与上述多边形(空间区的网格行中的临近两行的行号确定为上述边界网格范围字典中的键对一行号对应的网格列中的临近两列的列号排除在上述边界网格范围字典中的键对应的值第一行号不为多边形的边界顶点所在的网格行号，故直接将该第一行号(行号1)加入边界网格范围字典中的键，并将该第一行号(行号1)对应的列号[0,10,11,12]确间[1,10]之间的任意网格的中心坐标点均位于多边形内，列区间[10,12]之间的任意网格将该第一行号(行号2)对应的列号[1,10]确定为上述边界网格范围字典中的键对应的值，多边形的边界顶点所在的网格行号，故直接将该第一行号(行号3)加入边界网格范围字典界网格范围字典中的键，并将该第一行号(行号4)对应的列号[1,5]和[5,9]确定为上述边不为多边形的边界顶点所在的网格行号，故直接将该第一行号(行号5)加入边界网格范围不为多边形的边界顶点所在的网格行号，故直接将该第一行号(行号6)加入边界网格范围的列集中的临近两列之间的任意网格的中心坐标点与上述多边形(空间区域)的拓扑关系。[2,8]排除在上述边界网格范围字典中的键对应的值之外。在边界网格范围字典中可以表[0212]由上述步骤502可得到祛冗余后的边界网格的行列编号，并将祛冗余后的边界网[0213]请参阅图6a，图6a为本申请实施例提供的又一种时空数据查询方法的流程示意分得到的新网格的网格层级与上述空间区域的边界网格的网格层级一致，停止往下剖分。[0225]步骤603：对候选网格填充树缺失的叶子节点和中间节点填充，得到候选内部网[0229]由上述步骤603可得到候选内部网格，该候选内部网格并不是最终所求的空间区部网格的行号和/或列号不包含于边界网格范围字典中的键值，则表示该候选内部网格不格的行号和列号是否包含于边界网格范围字典中的键值，本实施例提供了一种确定方式。[0232]例如在电信领域网规网优场景中，需要在线分析某个空[0238]查询单元703，用于将所述边界网格的索引所指向的数据和所述内部网格的索引[0242]填充单元705，用于根据所述边界网格范围字典对所述空间区域的非边界部分填界坐标点和所述第二边界坐标点为位于所述空间区域边界的两个[0245]所述填充单元705，还用于对所述第一边界坐标点和所述第二边界坐标点之间的定为边界网格，该第一边界坐标点和第二边界坐标点为空间区域的两个不同的边界坐标以有效满足对空间区域的边界部分有针对性的精准述第一边界坐标点和所述第二边界坐标点所在的目标边界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方边界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方边界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方第一边界网格所在行中，将第一边界网格所在列和第二边界网格所在列之间的网格填充，第一边界坐标点和第二边界坐标点之间的边界坐标点所在的网格填充得到第三边界网格，可以使空间区域的边界网格化得到的边界网格构成的集合完全覆盖空间区域的边界部分，为上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号的情况下，若列号且/或为上述第二边界坐标点所在的列号的情况下，若该第一列号对应的网格行中的第一行号对应的网格列中的临近两列的列号确定为所述边界网格范围字典中的键对应的中的临近两行的行号确定为所述边界网格范围字典中的键第一行号为上述第一边界坐标点所在的行号且/或为上述第二边界坐标点所在的行号的情行号对应的网格列的不同情况而定，若第一行号对应的网格列中除了上述临近两列之外，一列号为上述第一边界坐标点所在的列号且/或为上述第二边界坐标点所在的列号的情况列号对应的网格行的不同情况而定，若第一列号对应的网格行中除了上述临近两行之外，[0266]在一种可能的实施方式中，所述时空数据查询装置70还可以包括计算单元706和[0269]所述填充单元705，还用于对所述候选网格填充树缺失的叶子节点和中间节点填精准；且相对于基于四叉树网格索引自顶而下的逐级递归四分空间区域的常规网格化方格的结果更为精准，从而使内部网格的索引所指向的数据作为最后的查询结果也更为精所述边界网格范围字典中的键值；所述列号区间为所述边界网格范围字典中的键对应的行号和/或列号不包含于所述边界网格范围字典中的键值，不将所述候选内部网格确定为[0277]在本申请实施例中，提供了利用边界网格范围字典对候具体为根据上述候选内部网格的行号和列号判断候选内部网格是否包含于边界网格范围[0278]在一种可能的实施方式中，所述时空数据查询装置70还可以包括转换单元708和的数据作为最后的查询结果。首先将边界网格和内部网格中的所有网格转换为目标网格，访问记录；应用于边界网格范围字典可以加快数据的查询速度以及表中数据的增删速度，[0285]根据本申请实施例，图7所示的装置中的各个单元可以分别或全部合并为一个或[0287]在图7所描述的时空数据查询装置中，通过改进空间区域的剖分策略及网格拓扑[0290]处理器802是进行算术运算和逻辑运算的模块，可以是中央处理器(centralprocessingunit，CPU)、显卡处理器(graphicsprocessingunit，GPU)或微处理器不包含所述边界坐标点的网格；所述边界网格的编码层级和/或所述内部网格的编码层级[0294]将所述边界网格的索引所指向的数据和所述内部网格的索引所指向的数据作为[0303]对所述第一边界坐标点和所述第二边界坐标点之间的所述边界坐标点所在的网定为边界网格，该第一边界坐标点和第二边界坐标点为空间区域的两个不同的边界坐标边界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方[0311]若所述目标斜率的绝对值大于1，将与所述第一边界网格的列号相邻的列号确定边界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方边界区域进行网格填充，形成彼此相邻的边界网格序列提供了进一步更为详细的实施方第一边界网格所在行中，将第一边界网格所在列和第二边界网格所在列之间的网格填充，第一边界坐标点和第二边界坐标点之间的边界坐标点所在的网格填充得到第三边界网格，可以使空间区域的边界网格化得到的边界网格构成的集合完全覆盖空间区域的边界部分，[0319]在所述边界网格的第一行号不为所述第一边界坐标点所在的行号且不为所述第二边界坐标点所在的行号的情况下，将所述第一行号确定为所述边界网格范围字典中的[0323]在所述第一行号为所述第一边界坐标点所在的行号且/或为所述第二边界坐标点述第一行号对应的网格列中的临近两列的列号确定为所述边界网格范围字典中的键对应[0324]或，在所述第一列号为所述第一边界坐标点所在的列号且/或为所述第二边界坐中心坐标点位于所述空间区域内，将所述第一列号确定为所述边界网格范围字典中的键，将所述第一列号对应的网格行中的相邻两行的行号确定为所述边界网格范围字典中的键为上述第一边界坐标