面向时空数据k近邻查询的分布式计算平台及查询方法

摘要

本发明公开了一种面向时空数据k近邻查询的分布式计算平台及查询方法，该平台包括全局索引数据管理模块，其与数据接入分发模块、时空数据索引模块和查询并行处理模块进行交互数据，用来支撑分布式动态两级索引结构；数据接入分发模块，其用于实时接入连续到达的时空数据和时空数据查询，根据分布式动态两级索引结构将时空数据和时空数据查询分别分发至时空数据索引模块和查询并行处理模块；时空数据索引模块，其对相应查询区域内的时空数据建立索引，实时更新时空数据的位置信息，并将更新的时空数据位置信息实时发送至查询并行处理模块；查询并行处理模块，其根据更新的时空数据位置信息，并行处理接收的时空数据查询，输出时空数据查询结果。

说明书

技术领域

本发明涉及时空数据查询技术，属于计算机应用领域，尤其涉及一种面向时空数据k近邻查询的分布式计算平台及查询方法。

背景技术

时空数据(Spatial-Temporal Data)是指具有空间和时间维度的一类数据，它通常用来描述某一对象的空间信息随时间的变化状态。近年来，随着各类移动设备(如手机、GPS设备)、无线传感器和电子监控设备的大规模应用以及移动互联网的迅猛发展，社会生活中许多基于位置服务的应用正在快速地产生大量的时空数据，而时空数据查询也在智能交通、电子商务、社交网络等领域产生越来越重要的影响。近年来，时空数据查询受到国内外学者的广泛关注，尤其是大数据背景下的海量时空数据查询成为一个新兴的研究热点。当前许多领域的时空数据规模呈“爆炸”式增长，传统的单机计算模式受到计算和存储能力的限制，已经难以应对大规模时空数据以及时空数据上的并发查询。

目前，国内外学者在时空数据查询领域已经做了很多工作，但是对于分布式环境下的海量时空数据k近邻查询的研究还处于起步阶段，该问题仍然面临巨大的挑战。具体表现如下：

(1)缺乏能够支持海量时空数据大规模并发k近邻查询的分布式计算平台。

(2)缺乏支持海量时空数据频繁更新和并行k近邻查询算法的分布式索引结构，导致对海量时空数据分布式存储和维护的支持性较差。

(3)现有的时空数据查询方法大多数都是基于单机计算环境的集中式处理方法，难以直接部署到分布式计算平台之上，缺乏有效的分布式k近邻查询方法。

发明内容

本发明的目的就是为了解决上述问题，提供一种面向时空数据k近邻查询的分布式计算平台及查询方法。本发明具有既能够对持续变化的海量时空数据进行实时存储和维护，又能够对大规模并发k近邻查询进行实时响应的优点。

为了实现上述目的，本发明采用如下技术方案：

一种面向时空数据k近邻查询的分布式计算平台，包括：

数据接入分发模块，其用于实时接入连续到达的时空数据和时空数据查询，根据分布式动态两级索引结构DTLI将时空数据和时空数据查询分别分发至数据缓存模块；

分布式动态两级索引结构DTLI包括第一级条状索引和基于条状索引的第二级网格索引， 所述第一级条状索引由对时空数据沿x轴方向进行划分而构成；所述第二级网格索引是对每一个条状索引的时空数据沿y轴进行划分而构成；

数据缓存模块，其用来缓存数据接入分发模块发送的时空数据和时空数据查询；

时空数据索引模块对各个条状索引区域内的时空数据分别建立索引，并对索引数据进行实时更新；所述时空数据索引模块还实时监听所述数据缓存模块到达的时空数据和时空数据查询，然后获取自身应处理的时空数据和查询；

全局索引数据管理模块，维护一份分布式动态两级索引结构的条状索引的边界信息作为全局索引数据，并与数据接入分发模块、时空数据索引模块和查询并行处理模块进行索引数据交互；

查询并行处理模块，对时空数据k近邻查询进行分布式处理。

所述数据接入分发模块，由若干个分布在不同物理计算节点上的数据接入算子组成，每个数据接入算子为一个逻辑计算单元。

所述时空数据索引模块，由若干个分布在不同物理计算节点上的数据索引算子组成，每个数据接入算子为一个逻辑计算单元。

所述查询并行处理模块，由若干个分布在不同物理计算节点上的数据查询算子组成，每个数据查询算子为一个逻辑计算单元。

所述各个算子之间通过发送和接收事件的形式来实现数据交互。

所述事件是一个<key,value>数据对，每个算子将根据事件的名称和key值指定其所接受的事件。

一种基于分布式计算平台的时空数据分布式k近邻查询方法，包括以下步骤：

步骤(1)：构建上述海量时空数据k近邻查询的分布式计算平台；

步骤(2)：在分布式计算平台上部署分布式动态两级索引结构DTLI；

步骤(3)：基于分布式动态两级索引结构DTLI，对连续到达的海量时空数据进行处理；

步骤(4)：基于DTLI索引结构，将时空数据分布式k近邻查询算法，即PSK算法部署到分布式计算平台上，实现PSK算法的并行化，进而实现对海量时空数据k近邻查询的并行处理。

所述步骤(2)的具体过程，包括：

步骤(2.1)：数据接入分发模块中的每一个数据接入算子维护一份DTLI的条状索引的边界信息，全局索引数据管理模块也维护一份DTLI的条状索引的边界信息，但并不记录任何时空数据的位置信息；

步骤(2.2)：时空数据索引模块中的每个数据索引算子负责维护一个条状索引，并对该条状索引内的时空数据进行存储和更新；每个数据索引算子在自身维护的条状索引之上构建第二级网格索引，从而实现将分布式动态两级索引结构部署在分布式计算平台上。

在所述步骤(2.2)中，若出现时空数据索引模块中的数据索引算子负责维护的一个条状索引发生分裂或者合并，该数据索引算子实时地将发生变化的条状索引的边界信息写入到全局索引数据管理模块。

数据接入分发模块中的数据接入算子通过“监听”操作启动一个监听进程对全局索引数据管理模块的数据进行持续监听。当监听进程一旦发现全局索引数据管理模块的条状索引发生了变化，数据接入算子则实时地获取全局索引数据管理模块更新的条状索引来覆盖本地的条状索引对应的部分。

所述步骤(3)的具体过程，包括：

步骤(3.1):数据接入分发模块中的每一个数据接入算子并行地接入到达的时空数据，并根据DTLI的条状索引为时空数据分配相应的数据索引算子。

步骤(3.2):数据接入分发模块中的数据接入算子将时空数据发送至数据缓存模块，数据索引模块中的每个数据索引算子持续监听数据缓存模块中到达的时空数据，并从数据缓存模块中实时获取自身应处理的时空数据。

在所述步骤(4)中，采用PSK算法并行处理时空数据k近邻查询。

其中，本发明的时空数据是指二维平面空间内的移动对象(如人、车)，这些移动对象的位置连续变化，并频繁地向数据中心报告自己的位置坐标。

本发明的有益效果：

(1)本发明采用的面向海量时空数据k近邻查询的分布式计算平台具备全局索引数据管理模块和数据缓存模块，能够很好地支撑本发明所提出的分布式动态两级索引结构，满足时空数据k近邻查询对于全局索引数据的分布式访问需求，避免不同算子在处理时空数据k近邻查询时出现数据错发问题，为海量时空数据大规模并发k近邻查询提供了通用的分布式计算平台；

(2)本发明所提出的分布式动态两级索引结构能够对持续变化的海量时空数据进行实时存储和维护；此外，该索引结构具备良好的可扩展性，在分布式环境下，仅通过增加硬件资源就可以实现索引结构时空数据处理能力的线性增长；最后，该索引结构能够很好地支持PSK查询算法，在很大程度上加速了PSK查询算法的收敛；

(3)本发明利用PSK算法来实现对时空数据上的k近邻查询的实时处理，减少了分布 式环境下处理时空数据k近邻查询所产生的物理计算节点之间的通信代价，能够对大规模并发k近邻查询进行实时响应，查询效率显著提高。

附图说明

图1为海量时空数据分布式动态两级索引结构(DTLI)示意图；

图2为DTLI条状索引分裂示意图；

图3为海量时空数据查询的分布式计算平台架构图；

图4为PSK算法演示图；

图5为基于分布式动态两级索引结构处理时空数据O_i流程图；

图6为PSK算法并行化架构图。

具体实施方式

在本发明中，面向海量时空数据k近邻查询的分布式计算平台、分布式动态两级索引结构和支持海量时空数据分布式k近邻查询的PSK算法三者紧密联系。下面结合附图，详细阐述面向海量时空数据k近邻查询的分布式计算平台、分布式动态两级索引结构和PSK算法三者之间的关系。

如图3所示，为本发明的面向海量时空数据查询的分布式计算平台。其具体结构组成如下：

本发明的面向时空数据k近邻查询的分布式计算平台，包括：

数据接入分发模块，其用于实时接入连续到达的时空数据和时空数据查询，根据分布式动态两级索引结构，将时空数据和时空数据查询分别分发至时空数据索引模块和查询并行处理模块；

时空数据索引模块，是对其所负责的相应查询区域内的时空数据建立索引，并实时维护更新时空数据的索引结构；

数据缓存模块，为数据接入分发模块和时空数据索引模块的数据交互提供数据缓存区，用于解决“数据接入算子”和“数据索引算子”之间数据异步更新所导致的数据错发问题；

全局索引数据管理模块，负责对全局索引数据的实时更新和维护，并其提供“读数据”和“写数据”两种数据操作方法，来分别与时空数据索引模块、查询并行处理模块以及查询计算模块之间进行索引数据交互；

所述查询计算模块，根据PSK查询算法处理时空数据k近邻查询请求；

具体地，数据接入分发模块是由多个分布在不同物理计算节点上的数据接入算子Entrance Actor组成的，每个数据接入算子为一个逻辑计算单元。该模块的主要任务是实时接 入连续到达的时空数据和用户查询，并根据分布式动态两级索引结构，为时空数据和查询分配相应的数据索引算子Index Actor。

具体地，时空数据索引模块，由若干个分布在不同物理计算节点上的数据索引算子IndexActor组成，每个数据索引算子为一个逻辑计算单元。每个Index Actor负责整个查询区域的一小部分区域。每个Index Actor的功能有两个：(1)对该部分区域内的时空数据建立索引，并对索引进行实时更新。(2)根据时空数据k近邻查询算法处理由Entrance Actor分发的时空数据k近邻查询。每个用户查询通常由多个Index Actor并行处理，每个Index Actor根据自身所维护的时空数据产生该查询的部分中间结果。

具体地，查询并行处理模块，由若干个分布在不同物理计算节点上的数据查询算子组成，每个数据查询算子为一个逻辑计算单元。

每个时空数据k近邻查询由唯一的一个数据查询算子Search Actor负责，一个Search Actor根据自身负载同时处理多个时空数据k近邻查询。每个Search Actor能够命令相应的IndexActor对其负责的查询进行处理。Search Actor通过发送和接收事件的形式实现与Index Actor之间的数据交互。

分布式环境下的时空数据索引结构是一种全局索引数据，既有若干计算单元从中读取数据，也有若干计算单元向其写入数据。因此，全局索引数据管理模块在该架构中有重要作用。该模块的主要任务是维护一份全局索引数据(即DTLI的条状索引)，并提供两种数据操作方法：put和get。不同物理节点的计算单元能够通过get和put操作对该模块的数据进行读写，从而保证全局索引数据在不同计算单元之间的及时更新。

进一步地，本发明的分布式计算平台还包括：数据缓存模块，用来缓存数据接入分发模块发送至所述时空数据索引模块的数据。引入数据缓存模块，主要用于解决Entrance Actor和Index Actor之间索引数据异步更新所导致的数据错发问题。实际应用中，Index Actor中条状索引的更新总是早于Entrance Actor中条状索引的更新，此时，同一条状索引在Index Actor和Entrance Actor中的版本可能不一致，这种情况下，Entrance Actor分发至Index Actor的数据和查询将出现错误。为此，该发明引入数据缓存模块，令每个Entrance Actor不再将时空数据和时空数据查询直接发送至Index Actor，而是发送至数据缓存模块，每个Index Actor对数据缓存模块中的数据和查询进行持续监听从而获得自身应处理的数据和查询。

本发明采用全局索引数据管理模块，其提供“读数据”和“写数据”两种数据操作方法，用于与数据接入分发模块、时空数据索引模块和查询并行处理模块进行索引数据交互，用来支撑分布式动态两级索引结构，最终构建出面向海量时空数据k近邻查询的分布式计算平台， 该分布式平台采用并行计算模式能够支持海量时空数据大规模k近邻查询。

本发明所应用的时空数据索引结构是针对海量时空数据分布式k近邻查询而设计的分布式动态两级索引结构(Distributed Two-Levels Index，DTLI)，如图1所示。

本发明的分布式动态两级索引结构(DTLI)包含两部分：(1)条状索引和网格索引的边界信息；(2)被索引的移动对象的位置信息。索引的边界信息相对较小，而移动对象的位置信息规模巨大。随着移动对象位置的频繁变化，两种信息都将频繁更新。

该索引结构首先对全局时空数据沿x轴方向进行划分，构建第一级条状索引，条状索引与y轴方向平行。对于任意一个条状索引s_i，通过上界和下界确定自身负责的区域。条状索引s_i根据移动对象的位置坐标为自身区域内的移动对象建立索引。

每一个条状索引具有以下特性：

(1)每个条状索中引移动对象的数目总是在一定的范围之内。假设一个条状索引内移动对象的数量为m，那么l＜m＜h，其中，l和h分别表示单个条状索引内移动对象数量的下限和上限。

(2)如果一个条状索引的移动对象数量大于h，那么该条状索引会沿y轴方向分裂成两个小的条状索引，使每个条状索引的移动对象数量小于h，图2是一个条状索引分裂操作的示意图；

(3)如果一个条状索引的移动对象数量小于l，那么该条状索引就会与相邻的条状索引合并，使合并之后的条状索引的移动对象数量大于l。

DTLI第二级索引是基于条状索引的网格索引。网格索引是对每一个条状索引的移动对象沿y轴进行划分，这样每个条状索就被划分成多个网格，每个网格对自身区域内的移动对象建立索引。图1中，条状索引s_i被划分成多个网格索引(g₁，g₂,…，g_n)。

网格索引和条状索引具有相似的特性：

(1)每个网格索引的移动对象的数量总是在一个范围之内；

(2)每个网格可以在条状索引范围之内与相邻的网格进行分裂或者合并来满足第一个特性。

本发明的分布式计算平台部署了分布式动态两级索引结构DTLI，结合图1和图3，部署的具体过程如下：

步骤(1)：将DTLI部署到本发明所述的分布式计算平台上时，每一个Entrance Actor保存一份DTLI第一级条状索引的边界信息，但并不记录任何移动对象的位置信息。EntranceActor的任务是为到达的移动对象分配Index Actor并将其发送至数据缓存模块。具体来说， 对于一个新到达的移动对象o_i(x_i，y_i)，Entrance>j{lb^j，ub^j}，然后以四元组<o_i,(x_i，y_i),s_j,{lb^j，ub^j}>的形式发送至数据缓存模块。由于条状索引边界的数据量很小，这样能够保证每一个Entrance>

步骤(2)：每个Index Actor负责维护一个DTLI的条状索引，对该条状索引的移动对象的位置进行存储和更新。此外，每个Index Actor在自身维护的条状索引之上建立二级网格索引。根据DTLI动态调整的特性，DTLI的条状索引会发生分裂或者合并，对应的Index Actor也会分裂或者合并。

步骤(3)：本发明所述的全局索引数据管理模块，其维护一份DTLI的条状索引的边界信息。如果某个Index Actor发生分裂或者合并，该Index Actor实时地将发生变化的条状索引的边界信息写入到全局索引数据管理模块。每一个Entrance Actor能够通过“监听”操作启动一个监听进程对全局索引数据管理模块的数据进行持续监听。当监听进程一旦发现全局索引数据管理模块的条状索引发生了变化，Entrance Actor则实时地调用get方法获取全局索引数据管理模块更新的条状索引来覆盖本地的条状索引对应的部分。在处理k近邻查询时，一些SearchActor也需要用到全局的条状索引信息，届时也将访问全局索引数据管理模块获取条状索引。该方案实现了Index Actor与其他处理单元之间全局索引数据的同步。

步骤(4)：本发明所述的数据缓存模块用来维护Entrance Actor发送至Index Actor的数据。数据缓存模块为每个Index Actor分配一个队列，每个Index Actor会持续监听数据缓存模块队列中到达的时空数据。令负责维护条状索引s_j的Index>j，所对应的队列为Q_j。对于新到达队列Q_j的时空数据o_i，IA_j监听到<o_i,(x_i，y_i)，s_j,{lb^j，ub^j}>后，判断o_i是否属于自身维护的条状索引。如果属于，则IA_j将从数据缓存模块中读取该对象并将该对象从数据缓存模块删除。如果IA_j发现o_i不属于自身维护的条状索引，则将元组<o_i,(x_i，y_i),s_j,{lb^j，ub^j}>中的s_j设置为Suspend，表示该移动对象为待处理状态。数据缓存模块采用广播方式，将待处理状态的移动对象发送至其他所有Index>

以上是DTLI索引结构在分布式计算平台上的整个部署方案，该方案描述了一个能够支持 海量时空数据实时存储和维护的可扩展的分布式动态索引结构。图6描述了该分布式索引架构处理移动对象的流程图。

本发明所述海量时空数据分布式k近邻查询方法(PSK算法)的具体步骤如下：

输入：k近邻查询q_j(x_j，y_j)；当前所有移动对象的位置信息；

输出：与查询点q_j的距离最近的k个移动对象；

步骤(1)：对于接收的k近邻查询q_j(x_j，y_j)，首先根据DTLI的条状索引查找包含q_j以及距离q_j最近的(k-1)个条状索引，生成候选条状索引集合V。对于任意一个条状索引s_i，它与查询q_j的距离定义为

步骤(2)：从集合V的每个候选条状索引中选择距离查询点q_j最近的h个移动对象，其中h＝min{k，θ}。

步骤(3)：从h*k个移动对象中选择距离查询q_j最近的k个对象，并对k个对象根据与q_j的距离进行排序，然后计算得到一个以q_j为圆心，以q_j和第k个对象距离为半径的圆C_k。圆C_k包含了q_j的k个近邻。

步骤(4)：计算得到与圆C_k相交的条状索引集合U，令集合W＝U-V。集合W的条状索引是指可能含有查询q_j的k近邻但是不属于集合V的条状索引。

步骤(5)：负责集合W中的每个条状索查找自身区域内属于圆C_k并且与q_j距离最近的k个对象。如果符合条件的移动对象的数目小于k，则选择所有符合条件的对象。

步骤(6)：将从集合W中的条状索引获取的对象与之前确定圆C_k的k个对象进行比较，得到与q_j最近的k个移动对象，即为q_j的k近邻。

PSK算法示例：在图4(a)中，给定一个查询q_j(3-NN)，PSK算法首先确定候选条状索引集合V＝{s_i，s_i+1，s_i+2}；在图4(b)中，PSK算法根据候选条状索引内移动对象(o₁,o₃,o₆)的位置，进一步确定圆C_k。根据PSK算法步骤4可知，条状索引集合W包含条状索引s_i+3。然后，PSK算法基于s_i+3的网格索引，找到自身区域内被圆C_k覆盖的移动对象o₇。最后，PSK算法从移动对象集合{o₁,o₃,o₆,o₇}中找到q_j的3个近邻为{o₁,o₆,o₇}。

将PSK算法部署到本发明的分布式计算平台后，整个分布式计算平台并行处理时空数据 k近邻查询的过程如下：

步骤(1)：“数据接入算子”首先根据PSK查询算法的步骤1计算得到候选条状索引集合{s₁，s₂，…，s_k}，然后将q_j及其候选条状索引的标识(<q_j，s_e>，1≤e≤k)发送至数据缓存模块。

步骤(2)：负责候选条状索引s_e的“数据索引算子”监听到查询q_j后，首先判断当前本地条状索引中s_e的边界与接收到s_e的边界是否一致。如果一致则进行下一步；否则，将<q_j，s_e>发送至其他所有“数据索引算子”，每个“数据索引算子”通过比较条状索引s_e的边界从而判断自己是否应处理查询q_j。

步骤(3)：负责处理查询q_j的“数据索引算子”根据DTLI的网格索引，快速得到距离查询q_j最近的h个移动对象，h值的确定见PSK算法步骤2。

步骤(4)：负责处理查询q_j的各个“数据索引算子”将距离q_j最近的h个移动对象发送至同一个“数据查询算子”SA_j。SA_j根据PSK算法的步骤3，基于接收到的由“数据索引算子”发送的移动对象计算得到圆C_k。

步骤(5)：SA_j从全局索引数据管理模块获取当前DTLI的条状索引的边界信息，然后计算得到所有与圆C_k相交的条状索引，从而得到PSK算法步骤4中的条状索引集合W。

步骤(6)：SA_j将查询q_j以及圆C_k发送至集合W中条状索引所对应的“数据索引算子”，每个“数据索引算子”找到自身区域内被圆C_k覆盖且距离查询q_j最近的k个移动对象。并将这些对象发送至SA_j。如果符合条件的移动对象数量小于k，则将所有符合条件的移动对象发送至SA_j。

步骤(7)：SA_j将新收到的移动对象与之前确定圆C_k的k个对象进行比较，从而得到查询q_j的k近邻。

本发明所提出的面向海量时空数据k近邻查询的分布式解决方案，减少了分布式环境下处理时空数据k近邻查询所需的物理计算节点之间的通信代价，能够对大规模并发k近邻查询进行实时响应，显著提高了查询效率。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限 制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。