基于MapReduce计算框架的浮动车数据与道路匹配的方法

摘要

本发明提供一种基于MapReduce计算框架的浮动车数据与道路匹配的方法，包括下述步骤：步骤一，将路网划分为网格；步骤二，利用MapReduce分布式计算框架将线段定位到网格上；步骤三，利用MapReduce分布式计算框架将浮动车数据定位到网格上；步骤四，在同一网格内，利用MapReduce分布式计算框架，将代表浮动车数据的点定位到线段上。本发明通过对分布式存储和计算架构的利用，并利用数据裁剪技术将系统中匹配算法的复杂度尽量降低，使得对数据的处理能力和处理规模都有极大的提升。

主权项

一种基于MapReduce计算框架的浮动车数据与道路匹配的方法，其特征在于，包括下述步骤：步骤一，将路网划分为网格；步骤二，利用MapReduce分布式计算框架将线段定位到网格上；步骤三，利用MapReduce分布式计算框架将代表浮动车数据的点定位到网格上；步骤四，在同一网格内，利用MapReduce分布式计算框架，将代表浮动车数据的点定位到线段上；所述步骤二中，具体的方法为：先进行步骤二的Map过程，算法如下：步骤2‑1，计算线段两端点各自所在的网格ID，如果两个网格ID相同则该线段属于该网格，直接创建Key/Value键值对，将网格ID作为Key，将线段作为Value；步骤2‑2，如果线段两端点所在的网格ID不同，首先利用线段两端点计算出其可能相交的网格矩阵，之后计算该线段向量与线段始端点和各个网格端点组成的向量的点乘积，如果点乘积大于零，则将该网格端点表示为1，如果点乘积小于0，则将该网格端点表示为0；步骤2‑3，在网格矩阵各个端点组成的矩阵中出现0、1变化的部分所属的网格，就是该线段向量与之相交的网格，该线段就属于相应的网格ID，将该些网格ID作为Key，而将该线段作为Value；之后启动步骤二的Reduce过程。