CN116108120A - 用于轨迹数据的网格索引方法、轨迹数据搜索方法和装置 - Google Patents

Abstract

本说明书的实施例提供了一种用于轨迹数据的网格索引方法、轨迹数据搜索方法和装置。在该用于轨迹数据的网格索引方法中，获取目标轨迹点信息，其中，目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息；根据待索引区域的范围和初始网格分辨率对纬度信息和经度信息进行映射，得到目标轨迹点的映射位置信息，其中，映射位置信息包括映射后的纬度信息和映射后的经度信息；利用空间填充曲线根据映射位置信息进行映射，得到目标轨迹点对应的网格标识；以及根据目标轨迹点的标识，得到目标轨迹点对应的网格标识的第一倒排列表，其中，第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。

Description

用于轨迹数据的网格索引方法、轨迹数据搜索方法和装置

技术领域

本说明书实施例通常涉及计算机技术领域，尤其涉及用于轨迹数据的网格索引方法、轨迹数据搜索方法和装置。

背景技术

随着GIS(Geographic Information Systems，地理信息系统)技术的发展以及诸如全球定位系统(Global Positioning System，GPS)等多种定位技术、射频识别技术(Radio Frequency Identification，RFID)以及通讯网络技术等的应用，大量包含时间戳(timestamp)的位置数据正被广泛采集。而随着移动设备的普及与基于位置的服务(Location-Based Service,LBS)的使用，对行人、车辆等移动目标进行追踪所产生的移动轨迹数据也具有较大应用价值，如：交通预测、路径规划、出行模式挖掘等。

针对轨迹数据管理，现有技术往往采用在树形的空间索引结构(如R-tree)上进行拓展，例3DR-tree、TB-tree、MV3R-tree等方式。但由于树形索引结构需维护许多中间节点以构造从根结点到有数据记录的叶结点之间的查询路径，而这些中间节点在时空范围上往往相互重叠，因此一定程度上浪费了存储空间。此外，此类树形结构索引一般通过深度优先搜索(Depth-First Search，DFS)或广度优先搜索(Breath-First Search，BFS)的方式进行轨迹查询，过多无关中间节点的遍历也制约了查询性能。如何设计能够有效地降低空间占用、并提高查询性能的索引结构与查询算法成为轨迹数据管理面临的问题。

发明内容

鉴于上述，本说明书实施例提供了一种用于轨迹数据的网格索引方法、轨迹数据搜索方法和装置。利用该方法、装置，可以通过二维网格索引或立体网格索引实现对不包含时间维度的轨迹数据或包含时间维度的轨迹数据的高效索引。由于所建立的网格索引基于空间填充曲线而得到，因而可以通过线性表进行存取，从而避免了树型索引结构中的中间节点的空间占用与创建时间开销，有助于提高查询性能。上述网格索引可以应用于诸如基于大型数据库的GIS系统等。

根据本说明书的实施例的一个方面，提供一种用于轨迹数据的网格索引方法，包括：获取目标轨迹点信息，其中，所述目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息；根据待索引区域的范围和初始网格分辨率对所述纬度信息和经度信息进行映射，得到所述目标轨迹点的映射位置信息，其中，所述映射位置信息包括映射后的纬度信息和映射后的经度信息；利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识；以及根据所述目标轨迹点的标识，得到所述目标轨迹点对应的网格标识的第一倒排列表，其中，所述第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。

根据本说明书的实施例的另一个方面，提供一种基于网格索引的轨迹数据搜索方法，包括：获取待搜索轨迹点的信息，其中，所述待搜索轨迹点的信息包括待搜索轨迹点的标识；利用网格标识的倒排列表，确定与所述待搜索轨迹点对应的网格标识，其中，所述网格标识的倒排列表通过如上所述的用于轨迹数据的网格索引方法而得到。

根据本说明书的实施例的又一个方面，提供一种用于轨迹数据的网格索引装置，包括：轨迹点信息获取单元，被配置为获取目标轨迹点信息，其中，所述目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息；位置映射单元，被配置为根据待索引区域的范围和初始网格分辨率对所述纬度信息和经度信息进行映射，得到所述目标轨迹点的映射位置信息，其中，所述映射位置信息包括映射后的纬度信息和映射后的经度信息；曲线编码单元，被配置为利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识；以及第一索引建立单元，被配置为根据所述目标轨迹点的标识，得到所述目标轨迹点对应的网格标识的第一倒排列表，其中，所述第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。

根据本说明书的实施例的再一个方面，提供一种基于网格索引的轨迹数据搜索装置，包括：待搜索轨迹点信息获取单元，被配置为获取待搜索轨迹点的信息，其中，所述待搜索轨迹点的信息包括待搜索轨迹点的标识；搜索单元，被配置为利用网格标识的倒排列表，确定与所述待搜索轨迹点对应的网格标识，其中，所述网格标识的倒排列表通过如权利要求1到6中任一所述的用于轨迹数据的网格索引方法而得到。

根据本说明书的实施例的另一方面，提供一种用于轨迹数据的网格索引装置，包括：至少一个处理器，以及与所述至少一个处理器耦合的存储器，以及存储在所述存储器上的计算机程序，所述至少一个处理器执行所述计算机程序来实现如上所述的用于轨迹数据的网格索引方法。

根据本说明书的实施例的另一方面，提供一种基于网格索引的轨迹数据搜索装置，包括：至少一个处理器，以及与所述至少一个处理器耦合的存储器，以及存储在所述存储器上的计算机程序，所述至少一个处理器执行所述计算机程序来实现如上所述的基于网格索引的轨迹数据搜索方法。

根据本说明书的实施例的另一方面，提供一种计算机可读存储介质，其存储有计算机程序，所述计算机程序被处理器执行时实现如上所述的用于轨迹数据的网格索引方法和/或基于网格索引的轨迹数据搜索方法。

根据本说明书的实施例的另一方面，提供一种计算机程序产品，包括计算机程序，所述计算机程序被处理器执行来实现如上所述的用于轨迹数据的网格索引方法和/或基于网格索引的轨迹数据搜索方法。

附图说明

通过参照下面的附图，可以实现对于本说明书内容的本质和优点的进一步理解。在附图中，类似组件或特征可以具有相同的附图标记。

图1示出了根据本说明书的实施例的用于轨迹数据的网格索引方法和装置、基于网格索引的轨迹数据搜索方法和装置的示例性架构。

图2示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的一个示例的流程图。

图3示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的又一个示例的流程图。

图4示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的网格标识的第二倒排列表的生成过程的一个示例的流程图。

图5示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的再一个示例的流程图。

图6示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的另一个示例的流程图。

图7示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的立体网格标识的一个示例的示意图。

图8示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的网格索引的一个示例的示意图。

图9示出了根据本说明书的实施例的基于网格索引的轨迹数据搜索方法的一个示例的流程图。

图10示出了根据本说明书的实施例的用于轨迹数据的网格索引装置的一个示例的方框图。

图11示出了根据本说明书的实施例的用于轨迹数据的网格索引装置的又一个示例的方框图。

图12示出了根据本说明书的实施例的用于轨迹数据的网格索引装置的再一个示例的方框图。

图13示出了根据本说明书的实施例的用于轨迹数据的网格索引装置的另一个示例的方框图。

图14示出了根据本说明书的实施例的基于网格索引的轨迹数据搜索装置的一个示例的方框图。

图15示出了根据本说明书的实施例的用于轨迹数据的网格索引装置的一个示例的方框图。

图16示出了根据本说明书的实施例的基于网格索引的轨迹数据搜索装置的一个示例的方框图。

具体实施方式

以下将参考示例实施方式讨论本文描述的主题。应该理解，讨论这些实施方式只是为了使得本领域技术人员能够更好地理解从而实现本文描述的主题，并非是对权利要求书中所阐述的保护范围、适用性或者示例的限制。可以在不脱离本说明书实施例内容的保护范围的情况下，对所讨论的元素的功能和排列进行改变。各个示例可以根据需要，省略、替代或者添加各种过程或组件。另外，相对一些示例所描述的特征在其它例子中也可以进行组合。

如本文中使用的，术语“包括”及其变型表示开放的术语，含义是“包括但不限于”。术语“基于”表示“至少部分地基于”。术语“一个实施例”和“一实施例”表示“至少一个实施例”。术语“另一个实施例”表示“至少一个其他实施例”。术语“第一”、“第二”等可以指代不同的或相同的对象。下面可以包括其他的定义，无论是明确的还是隐含的。除非上下文中明确地指明，否则一个术语的定义在整个说明书中是一致的。

在本说明书中，术语“网格索引”可以指在逻辑上将一定范围的地理空间G＝(lat_min,lon_min,lat_max,lon_max)划分为大小相等的矩形网格，通过每个网格来索引位于其中的轨迹点。其中，lat_min,lat_max可以用来表示上述地理空间的纬度边界，lon_min,lon_max可以用来表示上述地理空间的经度边界。

在本说明书中，术语“空间填充曲线”可以包括Z曲线、希尔伯特曲线等，其目的是在空间网格的基础上降低空间维度。例如，对于二维或三维空间，将其划分为等大小的网格或立方体，并按照曲线的延伸顺序对空间中的网格或立方体进行排序，从而将网格或立方体的表示空间映射至一维。

下面将结合附图来详细描述根据本说明书实施例的用于轨迹数据的网格索引方法和装置、基于网格索引的轨迹数据搜索方法和装置。

图1示出了根据本说明书实施例的用于轨迹数据的网格索引方法和装置、基于网格索引的轨迹数据搜索方法和装置的示例性架构100。

在图1中，网络110可以被应用于在终端设备120和服务器130之间进行互连。

网络110可以是能够对网络实体进行互连的任何类型的网络。网络110可以是单个网络或各种网络的组合。在覆盖范围方面，网络110可以是局域网(LAN)、广域网(WAN)等。在承载介质方面，网络110可以是有线网络、无线网络等。在数据交换技术方面，网络110可以是电路交换网络、分组交换网络等。

终端设备120可以是能够连接到网络110、访问网络110上的服务器或网站、处理数据或信号等的任何类型的电子计算设备。例如，终端设备120可以是台式计算机、笔记本电脑、平板电脑、智能电话等。尽管在图1中仅示出了一个终端设备，但是应当理解，可以有不同数量的终端设备连接到网络110。

在一种实施方式中，终端设备120可以由用户使用。终端设备120可以包括可为用户提供各种服务的应用客户端(例如客户端121)。在一些情况下，客户端121可以与服务器130进行交互。例如，客户端121可以将用户输入的消息传送到服务器130，并且从服务器130接收与上述消息相关联的响应。在本文中，“消息”可以指任何输入信息，例如来自用户输入的轨迹点信息等。

服务器130可以通过网络110连接到数据库140。数据库140可以用于支持服务器130建立轨迹数据的网格索引或基于网格索引进行轨迹数据搜索。

应当理解，图1中所示的所有网络实体都是示例性的，根据具体的应用需求，架构100中可以涉及任何其它网络实体。

图2示出了根据本说明书的实施例的用于轨迹数据的网格索引方法200的流程图。

如图2所示，在210，获取目标轨迹点信息。

在本实施例中，可以获取目标轨迹点信息。在一个示例中，可以对通过定位设备发送的实时位置进行采样，得到多个轨迹点信息。可以通过各种方式从所得到的轨迹点信息中选取目标轨迹点信息。其中，上述目标轨迹点信息可以包括目标轨迹点的标识、纬度信息和经度信息。在一个示例中，针对目标轨迹点p，其目标轨迹点信息可以是(pid,lat,lon)。pid,lat,lon可以分别用于指示目标轨迹点p的标识、所在维度和所在经度。

在本实施例的一些可选的实现方式中，上述目标轨迹点信息还可以包括目标轨迹点所属轨迹的标识。在一个示例中，一条轨迹可以是由轨迹点组成的有序序列，用以描述某物体在一定时间范围内的位置变化。例如，轨迹可以用T＝<p₁,p₂,…,p_n>来表示。p₁,p₂,…,p_n可以分别用于表示不同的轨迹点。从而，针对目标轨迹点p₁，其目标轨迹点信息可以是(p₁,lat,lon,tid)。tid可以用于表示目标轨迹点p₁所属轨迹的标识。

在本实施例的一些可选的实现方式中，上述目标轨迹点可以包括目标历史轨迹点。上述目标轨迹点信息还可以包括目标轨迹点信息的采集时间信息。在一个示例中，针对目标轨迹点p₁，其目标轨迹点信息可以是(p₁,lat,lon,time,tid)。time可以用于表示p₁对应的目标轨迹点信息的采集时间。在一个示例中，采集时间信息可以是时间戳(例如1668049697)。在一个示例中，采集时间可以是采集时的北京时间(例如2022-11-1011:08:17)。

在220，根据待索引区域的范围和初始网格分辨率对纬度信息和经度信息进行映射，得到目标轨迹点的映射位置信息。

在本实施例中，待索引区域的范围可以指待划分网格的地理空间的范围。例如，针对N市建立轨迹数据的网格索引，则待索引区域的范围可以是N市的行政区划，也可以是N市的行政区划的最小外接矩形。上述初始网格分辨率可以用于指示映射比例。在一个示例中，针对N市，当设置初始网格分辨率为6时，所划分的单个网格的大小约为750*750m²；当设置初始网格分辨率为7时，所划分的单个网格大小约为375*375m²。可以通过各种方式对目标轨迹点信息中的纬度信息和经度信息进行映射，以将目标轨迹点信息所指示的轨迹点映射至所划分的网格中。映射位置信息可以包括映射后的纬度信息和映射后的经度信息。

在一个示例中，针对轨迹点p＝(lat,lon)，可以通过以下公式得到映射后的纬度信息i和映射后的经度信息j。其中，μ可以用来表示初始网格分辨率。lat,lon,lat_min,lon_min,lat_max,lon_max的含义可以参考前面相关描述。

在230，利用空间填充曲线根据映射位置信息进行映射，得到目标轨迹点对应的网格标识。

在本实施例中，可以利用各种空间填充曲线(例如Z曲线、希尔伯特曲线等)根据映射位置信息进行映射，得到目标轨迹点对应的网格标识。在一个示例中，可以将上述映射位置信息包括的映射后的纬度信息(例如上述i)和映射后的经度信息(例如上述j)分别转换为二进制，再交错位(例如偶数位存放映射后的纬度信息的二进制表示的位，奇数位存放映射后的经度信息的二进制表示的位)，以产生上述目标轨迹点所在网格按照Z顺序(曲线)排列的编码作为目标轨迹点对应的网格标识(例如网格标识g₁)。

在240，根据目标轨迹点的标识，得到目标轨迹点对应的网格标识的第一倒排列表。

在本实施例中，可以根据上述目标轨迹点的标识与所得到的对应的网格标识之间的关系，得到目标轨迹点对应的网格标识的第一倒排列表。上述第一倒排列表用于表示网格标识与网格标识所指示的网格所包含的轨迹点的标识之间的关系。从而可以利用网格标识来索引位于该网格中的轨迹点。

下面参考图3，图3示出了根据本说明书的实施例的用于轨迹数据的网格索引方法300的又一个示例的流程图。

如图3所示，在310，获取目标轨迹点信息。

在本实施例中，上述目标轨迹点信息可以包括目标轨迹点的标识、纬度信息、经度信息和目标轨迹点所属轨迹的标识。可以参考前述图2实施例中步骤210中可选的实现方式中的相应描述。

在320，根据待索引区域的范围和初始网格分辨率对纬度信息和经度信息进行映射，得到目标轨迹点的映射位置信息。

在330，利用空间填充曲线根据映射位置信息进行映射，得到目标轨迹点对应的网格标识。

在340，根据目标轨迹点的标识，得到目标轨迹点对应的网格标识的第一倒排列表。

需要说明的是，上述步骤320至340可以参考前述图2实施例中步骤220至240的相应描述，此处不再赘述。

在350，根据目标轨迹点所属轨迹的标识，得到目标轨迹点对应的网格标识的第二倒排列表。

在本实施例中，可以根据上述目标轨迹点所属轨迹的标识与所得到的对应的网格标识之间的关系，得到目标轨迹点对应的网格标识的第二倒排列表。上述第二倒排列表用于表示网格标识与网格标识所指示的网格所包含的轨迹点所属轨迹的标识之间的关系。从而可以利用网格标识来索引位于该网格中的轨迹点所属的轨迹。

可选地，进一步参考图4，图4示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的网格标识的第二倒排列表的生成过程400的一个示例的流程图。

如图4所示，上述目标轨迹点包括实时轨迹点。在一个示例中，目标轨迹点可以是所获取的采集时间距离当前最近的轨迹点。

在410，判断目标轨迹点对应的网格标识的当前第二倒排列表中是否包含目标轨迹点的所属轨迹的标识。

在本实施例中，网格标识的第二倒排列表可以根据网格标识与轨迹点的所属轨迹的标识之间的关系变化进行更新，而无需每次重新创建新的网格标识的第二倒排列表。可以判断实时轨迹点对应的网格标识的当前第二倒排列表中是否包含该实时轨迹点的所属轨迹的标识。在一个示例中，若网格标识g₁的当前第二倒排列表中包含{轨迹t₁,轨迹t₂}，实时轨迹点p₅属于轨迹t₃。则可以判断网格标识g₁的当前第二倒排列表中不包含目标轨迹点的所属轨迹的标识。在一个示例中，若网格标识g₁的当前第二倒排列表中包含{轨迹t₁,轨迹t₃}，实时轨迹点p₅属于轨迹t₃。则可以判断网格标识g₁的当前第二倒排列表中包含目标轨迹点的所属轨迹的标识。

在410判断为否后，在420，将目标轨迹点的所属轨迹的标识插入目标轨迹点对应的网格标识的当前第二倒排列表。

在一个示例中，若网格标识g₁的当前第二倒排列表中包含{轨迹t₁,轨迹t₂}，可以将实时轨迹点p₅所属的轨迹的标识t₃插入目标轨迹点对应的网格标识g₁的当前第二倒排列表，从而更新后的网格标识g₁的当前第二倒排列表中包含{轨迹t₁,轨迹t₂,轨迹t₃}。

在430，从在目标轨迹点对应的网格标识所指示的网格附近的其他网格的网格标识的当前第二倒排列表中删除目标轨迹点的所属轨迹的标识。

在一个示例中，“网格附近”的范围可以根据上述实时轨迹点的采样率而确定，从而既可以避免因属于同一轨迹的轨迹点漂移太远而遗漏，又通过仅判断局部的当前第二倒排列表来减少计算量。若采样率较高，则“网格附近”的范围可以相应较小，例如仅将相邻网格确定为“网格附近”。若采样率较低，则“网格附近”的范围可以相应较大，例如将距离不超过5个网格确定为“网格附近”。在一个示例中，若网格标识g₂的当前第二倒排列表中包含{轨迹t₁,轨迹t₃}，则在将实时轨迹点p₅所属的轨迹的标识t₃插入目标轨迹点对应的网格标识g₁的当前第二倒排列表后，可以从网格标识g₂的当前第二倒排列表中删除“轨迹t₃”，从而更新后的网格标识g₂的当前第二倒排列表中包含{轨迹t₁}。

基于此，可以尽可能地保证在任意时刻对于实时轨迹点的实时索引中每个轨迹只被记录在一个网格标识的当前第二倒排列表内，避免记录冲突。

可选地，在410判断为是后，可以无需更新上述目标轨迹点对应的网格标识的第二倒排列表。

下面参考图5，图5示出了根据本说明书的实施例的用于轨迹数据的网格索引方法500的再一个示例的流程图。

如图5所示，在510，获取目标历史轨迹点信息。

在本实施例中，目标历史轨迹点信息包括目标历史轨迹点的标识、纬度信息、经度信息和目标历史轨迹点的位置信息的采集时间信息。在一个示例中，可以获取多个历史轨迹点的标识、位置信息和采集时间信息。其中，位置信息可以包括纬度信息和经度信息。可以通过各种方式从所获取到多个历史轨迹点信息中选取目标历史轨迹点信息。

在520，根据待索引区域的范围和初始网格分辨率对纬度信息和经度信息进行映射，得到目标历史轨迹点的映射位置信息。

在530，根据采集时间信息和预先划分的时间区段，得到目标历史轨迹点对应的时间区段编码。

在本实施例中，可以根据预先划分的时间区段对目标历史轨迹点对应的采集时间信息进行编码，得到时间区段编码。在一个示例中，目标历史轨迹点对应的采集时间信息可以是2022-11-10 11:08:17，预先划分的时间区段可以是一日(24小时)，时间区段编码可以用于表示采集时间信息所指示的日期相对于1970-01-01的偏移天数。则上述目标历史轨迹点对应的时间区段编码可以是19306。可选地，也可以直接将采集时间信息所指示的日期作为时间区段编码，例如可以是2022-11-10。可以理解，预先划分的时间区段也可以是一周、一小时等，相应地，时间区段编码可以用于表示采集时间信息所指示的日期相对于1970-01-01 0时的偏移周数或偏移小时数。

在540，根据预先划分的时间区段和初始网格分辨率对附加时间信息进行映射，得到映射时间信息。

在本实施例中，上述附加时间信息可以用于指示采集时间信息中除时间区段外的其他部分。在一个示例中，继续参考上例，预先划分的时间区段可以是一日，对应的时间区段编码可以是19306，则附加时间信息可以是11:08:17(北京时间，对应格林威治时间3:08:17)。而后，可以将附加时间信息转换为与时间戳对应的秒数，即3×3600+8×60+17＝11297秒。再通过以下公式根据所对应的秒数s和初始网格分辨率μ对附加时间信息进行映射，得到映射时间信息k。

在另一个示例中，采集时间信息可以是时间戳timestamp(例如1668049697)，预先划分的时间区段可以是一日，对应的时间区段编码D可以是19306，也可以通过以下公式根据时间戳timestamp和初始网格分辨率μ得到时间映射信息k。

可以理解，预先划分的时间区段也可以是一周、一小时等，相应地，时间区段编码可以用于表示采集时间信息所指示的日期相对于1970-01-01 0时的偏移周数或偏移小时数。从而附加时间信息可以用于指示采集时间信息中除上述偏移周数或偏移小时数外的其他部分，可以按照类似的方式将附加时间信息转换为与时间戳对应的秒数，再得到映射时间信息，此处不再赘述。

在550，利用空间填充曲线根据映射位置信息和映射时间信息进行映射，得到排序曲线编码。

在本实施例中，对于由包括映射后的纬度信息和映射后的经度信息的映射位置信息以及映射时间信息所形成的三维空间，可以利用空间填充曲线(例如Z排序曲线)的延伸顺序对空间中所划分的立体网格(例如立方体)进行排序，得到排序曲线编码，从而可以将立方网格(例如立方体)的表示空间映射至一维。

在560，根据时间区段编码和排序曲线编码，得到目标历史轨迹点对应的立体网格标识。

在本实施例中，可以通过各种方式将所得到的时间区段编码和排序曲线编码进行组合，得到目标历史轨迹点对应的立体网格标识c例如，可以将所得到的时间区段编码和排序曲线编码进行组合，中间用分隔符(例如空格，逗号，@等)相隔。再例如，还可以对所得到的时间区段编码和排序曲线编码进一步编码，以进一步建立索引，此处不作限定。

在570，根据目标历史轨迹点的标识，得到目标历史轨迹点对应的网格标识的第一倒排列表。

需要说明的是，上述步骤510、520和570可以参考前述图2实施例中步骤210、220和240的相关描述，此处不再赘述。

基于此，可以结合目标轨迹点的采集时间信息建立时空立方体索引。在时空立方体索引中，可以使用二维坐标来表示地理空间上的某个位置，并通过一维的时间轴来表示该地理空间上的平面位置随时间的变化。可见，时空立方体索引可以实现在空间和时间两个维度上索引轨迹点。

下面参考图6，图6示出了根据本说明书的实施例的用于轨迹数据的网格索引方法600的另一个示例的流程图。

如图6所示，在610，获取目标历史轨迹点信息。

在620，根据待索引区域的范围和初始网格分辨率对纬度信息和经度信息进行映射，得到目标历史轨迹点的映射位置信息。

在630，根据采集时间信息和预先划分的时间区段，得到目标历史轨迹点对应的时间区段编码。

在640，根据预先划分的时间区段和初始网格分辨率对附加时间信息进行映射，得到映射时间信息。

在650，利用空间填充曲线根据映射位置信息和映射时间信息进行映射，得到排序曲线编码。

在660，根据待索引区域的范围内的历史轨迹点在根据初始网格分辨率而划分的各个立体网格中的分布，对历史轨迹点分布稀疏的立体网格进行合并，得到合并后立体网格。

在本实施例中，可以通过预设的阈值判断根据初始网格分辨率而划分的各个立体网格内所包含的历史轨迹点的个数的多少，并可以对包含较少历史轨迹点的、邻近的多个(例如8个)立体网格进行合并，得到合并后的立体网格。

在670，根据合并后立体网格的合并次数确定合并后立体网格的层级编码。

在本实施例中，例如，可以将合并后立体网格的合并次数确定为合并后立体网格的层级编码。在一个示例中，对于合并1次后所得到的合并后的立体网格，其层级编码可以为1。在一个示例中，未经过合并的立体网格(即根据初始网格分辨率而划分的立体网格)的层级编码可以为0。

基于此，可以有效应对真实的轨迹点分布的不均匀性，例如对于非高峰时段及非热点地区，其轨迹点数量一般较少，因而单独维护索引项使得存储空间的利用率不高。通过对轨迹点分布稀疏的立体网格进行合并以及为不同大小的时空立方体赋予相应的层级编码L，既可以区分不同大小的时空立方体，又可以适应历史数据的分布，有效提升存储空间的利用率。

在680，根据网格合并后分辨率，确定合并后立体网格对应的排序曲线编码。

在本实施例中，网格合并后分辨率包括对初始网格分辨率进行与合并后立体网格的合并次数相匹配的缩减处理后的分辨率。在一个示例中，初始网格分辨率可以为μ。执行n次合并后所得到的合并后立体网格的网格合并后分辨率可以为μ-n，相应地，合并后立体网格的层级编码可以为n。其中，n≤μ。根据上述网格合并后分辨率，可以按照类似前述步骤620至步骤650的方法，得到上述合并后立体网格对应的排序曲线编码。可选地，合并后立体网格所对应的初始的各个立体网格可以共用上述合并后立体网格对应的排序曲线编码。

在690，根据时间区段编码、对应的排序曲线编码和目标历史轨迹点对应的层级编码，得到目标历史轨迹点对应的合并后立体网格的网格标识作为立体网格标识。

在本实施例中，可以首先确定目标历史轨迹点对应的层级编码。在一个示例中，若上述目标历史轨迹点所在的立体网格未经过合并，则对应的层级编码可以为0。在一个示例中，若上述目标历史轨迹点所在的立体网格经过n次合并，则对应的层级编码可以为n。之后，可以通过各种方式将所得到的时间区段编码、步骤680所确定的对应的排序曲线编码和上述层级编码进行组合，得到目标历史轨迹点对应的立体网格标识。例如，可以将所得到的时间区段编码、对应的排序曲线编码和层级编码进行组合，中间用分隔符(例如空格，逗号，@等)相隔。再例如，还可以对所得到的时间区段编码、对应的排序曲线编码和层级编码进一步编码，以进一步建立索引，此处不作限定。

在一个示例中，立体网格标识可以为(19306@15@0)。其中，19306、15、0可以分别为该目标历史轨迹点所在立体网格的时间区段编码、排序曲线编码和层级编码。其意味着上述立体网格为根据初始网格分辨率而划分的立体网格。在一个示例中，立体网格标识可以为(19306@5@1)。其中，19306、5、1可以分别为该目标历史轨迹点所在立体网格的时间区段编码、排序曲线编码和层级编码。其意味着上述立体网格为根据初始网格分辨率而划分的立体网格经过一次合并后而得到的合并后网格。

继续参考图7，图7示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的立体网格标识的一个示例的示意图。

如图7所示，初始网格分辨率μ例如可以是2。初始网格710对应的映射纬度信息i、映射经度信息j和映射时间信息k可以表示为(0,0,1)。初始网格710的排序曲线编码Z可以为1，层级编码L可以为0。而初始网格721、722对应的初始的映射纬度信息i、映射经度信息j和映射时间信息k可以分别表示为(0,0,2)、(1,0,2)。而对于经过一次合并的合并后网格720，其层级编码L为1，网格合并后分辨率μ为1，初始网格721、722对应的更新的映射纬度信息i、映射经度信息j和映射时间信息k可以为合并后网格720对应的映射纬度信息i、映射经度信息j和映射时间信息k，即(0,0,1)。此时，初始网格721、722对应的层级编码L为1。从而，即使在映射纬度信息i、映射经度信息j和映射时间信息k相同的情况下，也可以通过层级编码L来区分不同的立体网格

可以理解，由于时间区段编码D不涉及根据网格分辨率进行映射，因而合并后网格的时间区段编码D可以保持不变。例如，初始网格710和合并后网格720的时间区段编码D均可以为19163。

回到图6，在6100，根据目标历史轨迹点的标识，得到目标历史轨迹点对应的网格标识的第一倒排列表。

在本实施例中，可以参考前述实施例中步骤570的相关描述。

在一个示例中，可以将目标历史轨迹点的标识插入目标历史轨迹点对应的立体网格标识的第一倒排列表。若目标历史轨迹点的标识(pid＝89)，则可以向该目标历史轨迹点所在的立体网格的网格标识的第一倒排列表(立体网格-轨迹点)L_CP中插入记录<“19306@15@0”,89>。

可选地，在一个示例中，可以将目标历史轨迹点所属轨迹的标识插入目标历史轨迹点对应的立体网格标识的第二倒排列表。若目标历史轨迹点(pid＝89)属于轨迹(tid＝20)，还可以向该目标历史轨迹点所在的立体网格的网格标识的第二倒排列表(立体网格-轨迹)L_CT中插入记录<“19306@15@0”,20>。

需要说明的是，上述步骤610至步骤650可以参考前述图5实施例中步骤510至步骤550的相关描述，此处不再赘述。

继续参考图8，图8示出了根据本说明书的实施例的用于轨迹数据的网格索引方法的网格索引800的一个示例的示意图。

如图8所示，网格索引800可以包括网格标识的第一倒排列表L_GP，其可以用于表示网格标识与轨迹点标识之间的关系。根据轨迹点与所属轨迹之间的关系列表L_TP，以及当前轨迹点与所属轨迹之间的关系列表L_TlP，网格索引800还可以包括网格标识的第二倒排列表L_GT，其可以用于表示网格标识与轨迹标识之间的关系。上述网格可以包括如图中810所示的二维网格。

可选地，上述网格可以包括如图中820所示的立体网格。立体网格标识的第一倒排列表L_CP，其可以用于表示立体网格标识与轨迹点标识之间的关系。根据轨迹点与所属轨迹之间的关系列表L_TP，立体网格标识的第二倒排列表L_CT，其可以用于表示立体网格标识与轨迹标识之间的关系。

可选地，还可以建立立体网格标识的正排列表L_TC，其可以用于表示轨迹标识与立体网格标识之间的关系。

利用图1-图8中公开的用于轨迹数据的网格索引方法，可以通过二维网格索引或立体网格索引实现对不包含时间维度的轨迹数据或包含时间维度的轨迹数据的高效索引。由于所建立的网格索引基于轨迹点信息映射后的结果以及空间填充曲线而得到，因而可以通过线性表进行存取，从而避免了树型索引结构中的中间节点的空间占用与创建时间开销，有助于提高查询性能。上述网格索引可以应用于诸如基于大型数据库的GIS系统等。

下面参考图9，图9示出了根据本说明书的实施例的基于网格索引的轨迹数据搜索方法900的一个示例的流程图。

如图9所示，在910，获取待搜索轨迹点的信息。

在本实施例中，上述待搜索轨迹点的信息可以包括待搜索轨迹点的标识。

可选地，待搜索轨迹点的信息还可以包括对应的采集时间信息。

在920，利用网格标识的倒排列表，确定与待搜索轨迹点对应的网格标识。

在本实施例中，上述网格标识的倒排列表可以通过如前述图1-图8所描述的用于轨迹数据的网格索引方法而得到。在一个示例中，上述倒排列表可以包括第一倒排列表。在一个示例中，上述倒排列表还可以包括第二倒排列表。

利用图9中公开的基于网格索引的轨迹数据搜索方法，可以通过二维的网格标识和/或立体网格标识的倒排列表所提供的接口来索引实时轨迹数据和历史轨迹数据，从而可以提高轨迹数据的查询效率。

图10示出了根据本说明书的实施例的用于轨迹数据的网格索引装置1000的一个示例的方框图。该装置实施例可以与图2-图8所示的方法实施例相对应，该装置具体可以应用于各种电子设备中。

如图10所示，用于轨迹数据的网格索引装置1000可以包括轨迹点信息获取单元1010、位置映射单元1020、曲线编码单元1030和第一索引建立单元1040。

轨迹点信息获取单元1010，被配置为获取目标轨迹点信息，其中，所述目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息。轨迹点信息获取单元1010的操作可以参考上面图2描述的210的操作。

位置映射单元1020，被配置为根据待索引区域的范围和初始网格分辨率对所述纬度信息和经度信息进行映射，得到所述目标轨迹点的映射位置信息，其中，所述映射位置信息包括映射后的纬度信息和映射后的经度信息。位置映射单元1020的操作可以参考上面图2描述的220的操作。

曲线编码单元1030，被配置为利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识。曲线编码单元1030的操作可以参考上面图2描述的230的操作。

第一索引建立单元1040，被配置为根据所述目标轨迹点的标识，得到所述目标轨迹点对应的网格标识的第一倒排列表。其中，所述第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。第一索引建立单元1040的操作可以参考上面图2描述的240的操作。

进一步参考图11，图11示出了根据本说明书的实施例的用于轨迹数据的网格索引装置1100的又一个示例的方框图。

如图11所示，用于轨迹数据的网格索引装置1100可以包括轨迹点信息获取单元1110、位置映射单元1120、曲线编码单元1130、第一索引建立单元1140和第二索引建立单元1150。

在本实施例中，上述目标轨迹点信息还可以包括目标轨迹点所属轨迹的标识。

上述轨迹点信息获取单元1110、位置映射单元1120、曲线编码单元1130和第一索引建立单元1140的操作可以参考上面图3描述的步骤310至340的操作。

第二索引建立单元1150，被配置为根据所述目标轨迹点所属轨迹的标识，得到所述目标轨迹点对应的网格标识的第二倒排列表。其中，所述第二倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点所属轨迹的标识之间的关系。第二索引建立单元1150的操作可以参考上面图3描述的350的操作。

在一个示例中，上述目标轨迹点包括实时轨迹点。上述第二索引建立单元1150，被配置为：响应于所述目标轨迹点对应的网格标识的当前第二倒排列表中不包含所述目标轨迹点的所属轨迹的标识，将所述目标轨迹点的所属轨迹的标识插入所述目标轨迹点对应的网格标识的当前第二倒排列表，以及从在所述目标轨迹点对应的网格标识所指示的网格附近的其他网格的网格标识的当前第二倒排列表中删除所述目标轨迹点的所属轨迹的标识。上述内容可以参考上面图4实施例中的相应描述。

下面参考图12，图12示出了根据本说明书的实施例的用于轨迹数据的网格索引装置1200的再一个示例的方框图。

如图12所示，用于轨迹数据的网格索引装置1200可以包括轨迹点信息获取单元1210、位置映射单元1220、时间编码单元1230、附加时间映射单元1240、曲线编码单元1250和第一索引建立单元1260。

时间编码单元1230，被配置为根据所述采集时间信息和预先划分的时间区段，得到所述目标历史轨迹点对应的时间区段编码。时间编码单元1230的操作可以参考上面图5描述的530的操作。

附加时间映射单元1240，被配置为根据所述预先划分的时间区段和所述初始网格分辨率对附加时间信息进行映射，得到映射时间信息，其中，所述附加时间信息用于指示所述采集时间信息中除时间区段外的其他部分。附加时间映射单元1240的操作可以参考上面图5描述的540的操作。

曲线编码单元1250包括：曲线编码模块1251，被配置为利用空间填充曲线根据所述映射位置信息和所述映射时间信息进行映射，得到排序曲线编码。网格标识确定模块1252，被配置为根据所述时间区段编码和所述排序曲线编码，得到所述目标历史轨迹点对应的立体网格标识。曲线编码模块1251、网格标识确定模块1252的操作可以参考上面图5描述的550、560的操作。

轨迹点信息获取单元1210、位置映射单元1220和第一索引建立单元1260的操作可以参考上面图5描述的510、520、570的操作。

在一个示例中，用于轨迹数据的网格索引装置1200还可以包括第二索引建立单元1270。第二索引建立单元1270的具体操作可以参考上面图11实施例中第二索引建立单元1150的相关描述。

继续参考图13，图13示出了根据本说明书的实施例的用于轨迹数据的网格索引装置1300的另一个示例的方框图。

如图13所示，用于轨迹数据的网格索引装置1300可以轨迹点信息获取单元1310、位置映射单元1320、时间编码单元1330、附加时间映射单元1340、曲线编码单元1350、网格合并单元1360、层级编码单元1370、合并曲线编码单元1380和第一索引建立单元1390。

网格合并单元1360，被配置为根据所述待索引区域的范围内的历史轨迹点在根据所述初始网格分辨率而划分的各个立体网格中的分布，对历史轨迹点分布稀疏的立体网格进行合并，得到合并后立体网格。网格合并单元1360的操作可以参考上面图6描述的660的操作。

层级编码单元1370，被配置为根据所述合并后立体网格的合并次数确定所述合并后立体网格的层级编码。层级编码单元1370的操作可以参考上面图6描述的670的操作。

合并曲线编码单元1380，被配置为根据网格合并后分辨率，确定所述合并后立体网格对应的排序曲线编码。其中，所述网格合并后分辨率包括对初始网格分辨率进行与所述合并后立体网格的合并次数相匹配的缩减处理后的分辨率。合并曲线编码单元1380的操作可以参考上面图6描述的680的操作。

曲线编码单元1350包括：曲线编码模块1351和网格标识确定模块1352。网格标识确定模块1352，被进一步配置为：根据所述时间区段编码、对应的排序曲线编码和所述目标历史轨迹点对应的层级编码，得到所述目标历史轨迹点对应的合并后立体网格的网格标识作为立体网格标识。网格标识确定模块1352的操作可以参考上面图6描述的690的操作。

轨迹点信息获取单元1310、位置映射单元1320、时间编码单元1330、附加时间映射单元1340、曲线编码模块1351和第一索引建立单元1390的操作可以参考上面图6描述的610、620、630、640、650、6100的操作。

在一个示例中，第一索引建立单元1390被进一步配置为：将所述目标历史轨迹点的标识插入所述目标历史轨迹点对应的立体网格标识的第一倒排列表。第一索引建立单元1390的操作可以参考上面图6描述的6100中描述的相应示例中的操作。

在一个示例中，用于轨迹数据的网格索引装置1300还可以包括第二索引建立单元13100。第二索引建立单元13100的具体操作可以参考上面图11实施例中第二索引建立单元1150的相关描述。

在一个示例中，第二索引建立单元13100被进一步配置为：将所述目标历史轨迹点所属轨迹的标识插入所述目标历史轨迹点对应的立体网格标识的第二倒排列表。第二索引建立单元13100的操作可以参考上面图6描述的6100中描述的相应示例中的操作。

图14示出了根据本说明书的实施例的基于网格索引的轨迹数据搜索装置1400的一个示例的方框图。该装置实施例可以与图9所示的方法实施例相对应，该装置具体可以应用于各种电子设备中。

如图14所示，用于轨迹数据的网格索引装置1400可以包括待搜索轨迹点信息获取单元1410和搜索单元1420。

待搜索轨迹点信息获取单元1410，被配置为获取待搜索轨迹点的信息。其中，所述待搜索轨迹点的信息包括待搜索轨迹点的标识。待搜索轨迹点信息获取单元1410的操作可以参考上面图9描述的910的操作。

搜索单元1420，被配置为利用网格标识的倒排列表，确定与所述待搜索轨迹点对应的网格标识。其中，所述网格标识的倒排列表通过如上述图1-图8实施例描述的用于轨迹数据的网格索引方法而得到。搜索单元1420的操作可以参考上面图9描述的920的操作。

以上参照图1到图14，对根据本说明书实施例的用于轨迹数据的网格索引方法和装置、以及基于网格索引的轨迹数据搜索方法和装置的实施例进行了描述。

本说明书实施例的用于轨迹数据的网格索引装置和基于网格索引的轨迹数据搜索装置可以采用硬件实现，也可以采用软件或者硬件和软件的组合来实现。以软件实现为例，作为一个逻辑意义上的装置，是通过其所在设备的处理器将存储器中对应的计算机程序指令读取到内存中运行形成的。在本说明书实施例中，用于轨迹数据的网格索引装置和基于网格索引的轨迹数据搜索装置例如可以利用电子设备实现。

图15示出了本说明书的实施例的用于轨迹数据的网格索引装置1500的示意图。

如图15所示，用于轨迹数据的网格索引装置1500可以包括至少一个处理器1510、存储器(例如，非易失性存储器)1520、内存1530和通信接口1540，并且至少一个处理器1510、存储器1520、内存1530和通信接口1540经由总线1550连接在一起。至少一个处理器1510执行在存储器中存储或编码的至少一个计算机可读指令(即，上述以软件形式实现的元素)。

在一个实施例中，在存储器中存储计算机可执行指令，其当执行时使得至少一个处理器1510：获取目标轨迹点信息，其中，所述目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息；根据待索引区域的范围和初始网格分辨率对所述纬度信息和经度信息进行映射，得到所述目标轨迹点的映射位置信息，其中，所述映射位置信息包括映射后的纬度信息和映射后的经度信息；利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识；以及根据所述目标轨迹点的标识，得到所述目标轨迹点对应的网格标识的第一倒排列表，其中，所述第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。

应该理解，在存储器中存储的计算机可执行指令当执行时使得至少一个处理器1510进行本说明书的各个实施例中以上结合图1-8描述的各种操作和功能。

图16示出了本说明书的实施例的基于网格索引的轨迹数据搜索装置1600的示意图。

如图16所示，基于网格索引的轨迹数据搜索装置1600可以包括至少一个处理器1610、存储器(例如，非易失性存储器)1620、内存1630和通信接口1640，并且至少一个处理器1610、存储器1620、内存1630和通信接口1640经由总线1650连接在一起。至少一个处理器1610执行在存储器中存储或编码的至少一个计算机可读指令(即，上述以软件形式实现的元素)。

在一个实施例中，在存储器中存储计算机可执行指令，其当执行时使得至少一个处理器1610：获取待搜索轨迹点的信息，其中，所述待搜索轨迹点的信息包括待搜索轨迹点的标识；利用网格标识的倒排列表，确定与所述待搜索轨迹点对应的网格标识，其中，所述网格标识的倒排列表通过如上述的用于轨迹数据的网格索引方法而得到。

应该理解，在存储器中存储的计算机可执行指令当执行时使得至少一个处理器1610进行本说明书的各个实施例中以上结合图9描述的各种操作和功能。

根据一个实施例，提供了一种例如计算机可读介质的程序产品。计算机可读介质可以具有指令(即，上述以软件形式实现的元素)，该指令当被计算机执行时，使得计算机执行本说明书的各个实施例中以上结合图1-9描述的各种操作和功能。

具体地，可以提供配有可读存储介质的系统或者装置，在该可读存储介质上存储着实现上述实施例中任一实施例的功能的软件程序代码，且使该系统或者装置的计算机或处理器读出并执行存储在该可读存储介质中的指令。

在这种情况下，从可读介质读取的程序代码本身可实现上述实施例中任何一项实施例的功能，因此机器可读代码和存储机器可读代码的可读存储介质构成了本发明的一部分。

本说明书各部分操作所需的计算机程序代码可以用任意一种或多种程序语言编写，包括面向对象编程语言，如Java、Scala、Smalltalk、Eiffel、JADE、Emerald、C++、C#、VB、NET以及Python等，常规程序化编程语言如C语言、Visual Basic 2003、Perl、COBOL2002、PHP以及ABAP，动态编程语言如Python、Ruby和Groovy，或者其他编程语言等。该程序编码可以在用户计算机上运行，或者作为独立的软件包在用户计算机上运行，或者部分在用户计算机上运行另一部分在远程计算机运行，或者全部在远程计算机或服务器上运行。在后一种情况下，远程计算机可以通过任何网络形式与用户计算机连接，比如局域网(LAN)或广域网(WAN)，或连接至外部计算机(例如通过因特网)，或者在云计算环境中，或者作为服务使用，比如软件即服务(SaaS)。

可读存储介质的实施例包括软盘、硬盘、磁光盘、光盘(如CD-ROM、CD-R、CD-RW、DVD-ROM、DVD-RAM、DVD-RW、DVD-RW)、磁带、非易失性存储卡和ROM。可选择地，可以由通信网络从服务器计算机上或云上下载程序代码。

上述对本说明书特定实施例进行了描述。其它实施例在所附权利要求书的范围内。在一些情况下，在权利要求书中记载的动作或步骤可以按照不同于实施例中的顺序来执行并且仍然可以实现期望的结果。另外，在附图中描绘的过程不一定要求示出的特定顺序或者连续顺序才能实现期望的结果。在某些实施方式中，多任务处理和并行处理也是可以的或者可能是有利的。

上述各流程和各系统结构图中不是所有的步骤和单元都是必须的，可以根据实际的需要忽略某些步骤或单元。各步骤的执行顺序不是固定的，可以根据需要进行确定。上述各实施例中描述的装置结构可以是物理结构，也可以是逻辑结构，即，有些单元可能由同一物理实体实现，或者，有些单元可能分由多个物理实体实现，或者，可以由多个独立设备中的某些部件共同实现。

在整个本说明书中使用的术语“示例性”意味着“用作示例、实例或例示”，并不意味着比其它实施例“优选”或“具有优势”。出于提供对所描述技术的理解的目的，具体实施方式包括具体细节。然而，可以在没有这些具体细节的情况下实施这些技术。在一些实例中，为了避免对所描述的实施例的概念造成难以理解，公知的结构和装置以框图形式示出。

以上结合附图详细描述了本说明书的实施例的可选实施方式，但是，本说明书的实施例并不限于上述实施方式中的具体细节，在本说明书的实施例的技术构思范围内，可以对本说明书的实施例的技术方案进行多种简单变型，这些简单变型均属于本说明书的实施例的保护范围。

本说明书内容的上述描述被提供来使得本领域任何普通技术人员能够实现或者使用本说明书内容。对于本领域普通技术人员来说，对本说明书内容进行的各种修改是显而易见的，并且，也可以在不脱离本说明书内容的保护范围的情况下，将本文所定义的一般性原理应用于其它变型。因此，本说明书内容并不限于本文所描述的示例和设计，而是与符合本文公开的原理和新颖性特征的最广范围相一致。

Claims (16)

1.一种用于轨迹数据的网格索引方法，包括：

获取目标轨迹点信息，其中，所述目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息；

根据待索引区域的范围和初始网格分辨率对所述纬度信息和经度信息进行映射，得到所述目标轨迹点的映射位置信息，其中，所述映射位置信息包括映射后的纬度信息和映射后的经度信息；

利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识；以及

根据所述目标轨迹点的标识，得到所述目标轨迹点对应的网格标识的第一倒排列表，其中，所述第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。

2.如权利要求1所述的网格索引方法，其中，所述目标轨迹点信息还包括目标轨迹点所属轨迹的标识，

所述方法还包括：

根据所述目标轨迹点所属轨迹的标识，得到所述目标轨迹点对应的网格标识的第二倒排列表，其中，所述第二倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点所属轨迹的标识之间的关系。

3.如权利要求2所述的网格索引方法，其中，所述目标轨迹点包括实时轨迹点，

所述根据所述目标轨迹点所属轨迹的标识，得到所述目标轨迹点对应的网格标识的第二倒排列表包括：

响应于所述目标轨迹点对应的网格标识的当前第二倒排列表中不包含所述目标轨迹点的所属轨迹的标识，

将所述目标轨迹点的所属轨迹的标识插入所述目标轨迹点对应的网格标识的当前第二倒排列表，以及

从在所述目标轨迹点对应的网格标识所指示的网格附近的其他网格的网格标识的当前第二倒排列表中删除所述目标轨迹点的所属轨迹的标识。

4.如权利要求2所述的网格索引方法，其中，所述目标轨迹点包括目标历史轨迹点，所述目标轨迹点信息还包括所述目标历史轨迹点的位置信息的采集时间信息，所述网格标识包括立体网格标识，

在所述利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识之前，所述方法还包括：

根据所述采集时间信息和预先划分的时间区段，得到所述目标历史轨迹点对应的时间区段编码；

根据所述预先划分的时间区段和所述初始网格分辨率对附加时间信息进行映射，得到映射时间信息，其中，所述附加时间信息用于指示所述采集时间信息中除时间区段外的其他部分，

所述利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识包括：

利用空间填充曲线根据所述映射位置信息和所述映射时间信息进行映射，得到排序曲线编码；

根据所述时间区段编码和所述排序曲线编码，得到所述目标历史轨迹点对应的立体网格标识。

5.如权利要求4所述的网格索引方法，其中，在所述根据所述时间区段编码和所述排序曲线编码，得到立体网格标识之前，所述方法还包括：

根据所述待索引区域的范围内的历史轨迹点在根据所述初始网格分辨率而划分的各个立体网格中的分布，对历史轨迹点分布稀疏的立体网格进行合并，得到合并后立体网格；

根据所述合并后立体网格的合并次数确定所述合并后立体网格的层级编码；

根据网格合并后分辨率，确定所述合并后立体网格对应的排序曲线编码，其中，所述网格合并后分辨率包括对初始网格分辨率进行与所述合并后立体网格的合并次数相匹配的缩减处理后的分辨率，

所述根据所述时间区段编码和所述排序曲线编码，得到所述目标历史轨迹点对应的立体网格标识包括：

根据所述时间区段编码、对应的排序曲线编码和所述目标历史轨迹点对应的层级编码，得到所述目标历史轨迹点对应的合并后立体网格的网格标识作为立体网格标识。

6.如权利要求4或5所述的网格索引方法，其中，所述根据所述目标轨迹点的标识，得到所述网格标识的第一倒排列表包括：

将所述目标历史轨迹点的标识插入所述立体网格标识的第一倒排列表，

所述根据所述目标轨迹点所属轨迹的标识，得到所述网格标识的第二倒排列表包括：

将所述目标历史轨迹点所属轨迹的标识插入所述立体网格标识的第二倒排列表。

7.一种基于网格索引的轨迹数据搜索方法，包括：

获取待搜索轨迹点的信息，其中，所述待搜索轨迹点的信息包括待搜索轨迹点的标识；

利用网格标识的倒排列表，确定与所述待搜索轨迹点对应的网格标识，其中，所述网格标识的倒排列表通过如权利要求1到6中任一所述的用于轨迹数据的网格索引方法而得到。

8.一种用于轨迹数据的网格索引装置，包括：

轨迹点信息获取单元，被配置为获取目标轨迹点信息，其中，所述目标轨迹点信息包括目标轨迹点的标识、纬度信息和经度信息；

位置映射单元，被配置为根据待索引区域的范围和初始网格分辨率对所述纬度信息和经度信息进行映射，得到所述目标轨迹点的映射位置信息，其中，所述映射位置信息包括映射后的纬度信息和映射后的经度信息；

曲线编码单元，被配置为利用空间填充曲线根据所述映射位置信息进行映射，得到所述目标轨迹点对应的网格标识；以及

第一索引建立单元，被配置为根据所述目标轨迹点的标识，得到所述目标轨迹点对应的网格标识的第一倒排列表，其中，所述第一倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点的标识之间的关系。

9.如权利要求8所述的网格索引装置，其中，所述目标轨迹点信息还包括目标轨迹点所属轨迹的标识，

所述装置还包括：

第二索引建立单元，被配置为根据所述目标轨迹点所属轨迹的标识，得到所述目标轨迹点对应的网格标识的第二倒排列表，其中，所述第二倒排列表用于表示网格标识与所述网格标识所指示的网格所包含的轨迹点所属轨迹的标识之间的关系。

10.如权利要求9所述的网格索引装置，其中，所述目标轨迹点包括实时轨迹点，

所述第二索引建立单元，被配置为：

响应于所述目标轨迹点对应的网格标识的当前第二倒排列表中不包含所述目标轨迹点的所属轨迹的标识，

将所述目标轨迹点的所属轨迹的标识插入所述目标轨迹点对应的网格标识的当前第二倒排列表，以及

从在所述目标轨迹点对应的网格标识所指示的网格附近的其他网格的网格标识的当前第二倒排列表中删除所述目标轨迹点的所属轨迹的标识。

11.如权利要求9所述的网格索引装置，其中，所述目标轨迹点包括目标历史轨迹点，所述目标轨迹点信息还包括所述目标历史轨迹点的位置信息的采集时间信息，所述网格标识包括立体网格标识，

所述装置还包括：

时间编码单元，被配置为根据所述采集时间信息和预先划分的时间区段，得到所述目标历史轨迹点对应的时间区段编码；

附加时间映射单元，被配置为根据所述预先划分的时间区段和所述初始网格分辨率对附加时间信息进行映射，得到映射时间信息，其中，所述附加时间信息用于指示所述采集时间信息中除时间区段外的其他部分，

所述曲线编码单元包括：

曲线编码模块，被配置为利用空间填充曲线根据所述映射位置信息和所述映射时间信息进行映射，得到排序曲线编码；

网格标识确定模块，被配置为根据所述时间区段编码和所述排序曲线编码，得到所述目标历史轨迹点对应的立体网格标识。

12.如权利要求11所述的网格索引装置，其中，所述装置还包括：

网格合并单元，被配置为根据所述待索引区域的范围内的历史轨迹点在根据所述初始网格分辨率而划分的各个立体网格中的分布，对历史轨迹点分布稀疏的立体网格进行合并，得到合并后立体网格；

层级编码单元，被配置为根据所述合并后立体网格的合并次数确定所述合并后立体网格的层级编码；

合并曲线编码单元，被配置为根据网格合并后分辨率，确定所述合并后立体网格对应的排序曲线编码，其中，所述网格合并后分辨率包括对初始网格分辨率进行与所述合并后立体网格的合并次数相匹配的缩减处理后的分辨率；

所述网格标识确定模块，被进一步配置为：

根据所述时间区段编码、对应的排序曲线编码和所述目标历史轨迹点对应的层级编码，得到所述目标历史轨迹点对应的合并后立体网格的网格标识作为立体网格标识。

13.如权利要求11或12所述的网格索引装置，其中，所述第一索引建立单元被进一步配置为：

将所述目标历史轨迹点的标识插入所述立体网格标识的第一倒排列表，

所述第二索引建立单元被进一步配置为：

将所述目标历史轨迹点所属轨迹的标识插入所述立体网格标识的第二倒排列表。

14.一种基于网格索引的轨迹数据搜索装置，包括：

待搜索轨迹点信息获取单元，被配置为获取待搜索轨迹点的信息，其中，所述待搜索轨迹点的信息包括待搜索轨迹点的标识；

搜索单元，被配置为利用网格标识的倒排列表，确定与所述待搜索轨迹点对应的网格标识，其中，所述网格标识的倒排列表通过如权利要求1到6中任一所述的用于轨迹数据的网格索引方法而得到。

15.一种计算机可读存储介质，其存储有计算机程序，所述计算机程序被执行时使得处理器执行如权利要求1到6中任一所述的用于轨迹数据的网格索引方法或如权利要求7所述的基于网格索引的轨迹数据搜索方法。

16.一种计算机程序产品，包含计算机程序，所述计算机程序被执行时使得处理器执行如权利要求1到6中任一所述的用于轨迹数据的网格索引方法或如权利要求7所述的基于网格索引的轨迹数据搜索方法。

Images