浙大与阿里AZFT下一代数据库技术实验室合作成果入选VLDB 2019

导语：

在刚刚结束的VLDB 2019顶级国际会议上，浙江大学与阿里巴巴AZFT下一代数据库技术实验室联合发表的最新研究成果入选了VLDB 2019 Research Paper（研究类文章），入选论文的题目为“Real-time Distributed Co-Movement Pattern Detection on Streaming Trajectories”。

该研究成果是由浙江大学数据库与大数据分析实验室高云君教授团队和阿里巴巴AZFT实验室合作完成。VLDB是数据库领域的三大顶级国际会议之一，其在数据库领域具有很高的学术地位和国际影响力。此项研究成果也是“阿里巴巴—浙江大学下一代数据库技术实验室项目”在科研层面取得的新成果，其中团队负责人高云君教授，作为此项目的高校合作老师之一，将会在此之后继续通过阿里巴巴和高校合作的平台，与阿里研发团队持续滚动项目合作，通过高效的校企协作创造更多的学术与社会价值。

01 面向大轨迹流数据挖掘中的实际问题

随着移动传感技术和定位技术的快速发展，轨迹数据正以极快的速度增长。这些轨迹数据捕获了人类、车辆和动物的运动行为等信息，因而分析和挖掘这些数据是许多现实应用的基础。其中共同运动模式(Co-Movement Pattern)检测是一种重要的分析类型。共同运动模式检测可应用于移动物体的运动轨迹预测、轨迹压缩以及其他基于位置的服务等。现有的研究通常考虑的是历史数据的运动模式检测。然而，许多应用如轨迹预测需要对流式轨迹进行实时处理。因此，我们研究了流式轨迹数据上的分布式共同运动模式实时检测。在基于实时轨迹流的运动模式检测中，轨迹数据是不间断到达的无界数据，这使得轨迹流上的运动模式实时检测问题变得尤为困难。鉴于此，我们提出了一个基于Apache Flink的轨迹流共同运动模式实时检测框架。此项研究成果可以总结为以下几个方面：

• 1. 针对轨迹流共同运动模式实时检测，提出了基于Flink的轨迹流共同运动模式实时检测框架，其包含聚类和模式枚举两个阶段；
• 2. 针对聚类，提出了基于双层索引GR-index的范围连接来加速聚类过程，并对范围连接进行优化；
• 3. 针对模式枚举，提出了FBA和VBA两个算法，以加速和优化枚举过程。其采用位压缩（定长压缩与变长压缩）算法和基于候选集的枚举技术将存储与计算代价从指数级减少至线性。

对比现有算法，该框架第一次针对轨迹流进行共同运动模式实时挖掘，在效率和可扩展性方面取得了显著提升，并能有效地应用于实际的业务场景中。

论文现场poster展示图

02 技术点解析

对于此项研究中算法的实现细节，具体的框架图如下所示：

Indexed Clustering and Pattern Enumeration(ICPE)框架

01 Co-Movement运动模式实时检测问题定义

Co-Movement运动模式实时检测

a). Co-Movement 运动模式

轨迹的运动模式可以表示为CP , 当T满足以下5个条件时，CP就是一个Co-Movement运动模式CP(M, K, L, G)。（注：O表示运动物体集合，T表示时间片集合）

• 紧密性：用于定义“共同运动”，即O中所有物体在T中的任意时间片都属于同一个簇；
• 重要性：用于定义共同运动物体数量，即|O| ≥ M；
• 持续性：用于定义共同运动时间长度，即|T| ≥ K；
• 连续性：用于定义连续运动时间长度，即T满足L-连续条件；
• 连接性：用于定义不连续运动时间长度，即T属于G-连接条件。

其中L-连续指T中的各个时间片可以不连续且可以拆分为若干个子时间片段Ti（|Ti| ≥ L）；G-连接指∀(1 ≤ i ≤ |T| − 1), T[i + 1] − T[i] ≤ G，T[i]代表T中的第i个元素。例如，在图2中，O = {o4, o5, o6} 在时间序列T = <3, 4, 6, 7>时是在约束条件CP(3, 4, 2, 2)下的一个Co-Movement运动模式。

b). Co-Movement运动模式实时检测

Co-Movement运动模式实时检测旨在找到当前时间所有运动模式。

02 聚类

a).GR-Index

我们采用分布式两层索引GR-Index来加速聚类过程。GR-Index采用网格索引作为全局索引，并对每个网格中数据建立R树作为局部索引。其中，每个网格都可以代表Flink中的一个分区。给定一个位置o=，则它对应的分区键值为<⌊o.x/lg⌋,⌊o.y/lg⌋>。

b).基于GR-Index的范围连接

基于GR-Index的范围连接过程可以分为三步：GridAllocate，GridQuery和GridSync。GridAllocate负责建立全局网格索引，其将每个时间片的数据分配至不同的网格，并将每个移动物体位置转换成数据对象（位于某个特定网格）或查询对象（范围区域与该网格相交）。GridQuery针对每个网格里的数据对象建立局部索引R树，并对查询对象进行范围查询。此外，我们利用单数据集上范围连接结果的对称性，提出了两个引理以加速查询。最后，GridSync收集且合并所有网格中的查询结果。

c).基于GR-Index的实时聚类

使用DBSCAN聚类方法对范围连接后的结果进行聚类，利用范围连接可以很容易地得到中心点和密度可达点。此外，我们通过单独对每个时间片进行聚类来实现聚类过程的并行性，从而加速聚类过程。

03 模式枚举

a).基准算法(BA)

我们采用了基于轨迹Id的分区技术，以克服现存算法不适用于轨迹流共同运动模式实时检测的不足。基于轨迹Id的分区为每条轨迹o分配一个子任务，每个子任务不同时刻的分区包含该时刻与o在同一簇的轨迹对象（这些轨迹的id大于o.id）。接着，对于每一个分区，先枚举所有可能模式，并对每个模式验证其正确性。在验证过程中，我们使用η=(⌈K/L⌉-1)×(G-1)+K+L-1个时间片信息进行验证，从而保证没有被遗漏正确结果。由于基线算法需要枚举以及存储所有可能模式，因而基线算法的计算和存储代价都是指数级。

b). 固定长度的位压缩算法(FBA)

为了减少基线算法中指数级别的存储成本和时间复杂度，我们提出了固定长度的位压缩算法。对于分区里的每个轨迹oi，采用固定长度的位字符串B[oi]来表示oi，其中|B[oi]|=η，位1表示o和oi属于同一个簇，位0则不是。为了枚举可能模式，我们利用AND位操作运算，以获得模式的位字符串。此外，为了加速枚举，我们提出了一个基于候选集的模式枚举算法。该算法首选过滤掉不符合要求的模式，并在符合要求的模式上进行增量式枚举。固定长度的位压缩算法采用位表示和基于候选集的模式技术，从而将枚举时间和存储代价从指数降低为线性。

c). 非固定长度的位压缩算法(VBA)

固定长度的位压缩算法可能造成某些时间片的重复验证。为此，我们提出了非固定长度的位压缩算法来确保每个时间片只被验证一次。我们采用非固定长度的位字符串来表示分区中的轨迹oi。符号为<sti,eti,B[oi]>，其中sti是起始时间，eti是终止时间。非固定长度的字符串需要找到一个最长模式时间序列以满足(K, L, G)限制条件。非固定长度的为压缩算法利用最长模式时间序列技术，进一步提高了系统吞吐量，并降低了存储代价。然而，由于模式需要等待最长模式时间序列的发现才能被返回，因而系统响应时间增大。

03 实验结果

为了评估此项研究中提出的算法，我们采用了两个真实数据集和一个合成数据集来评估聚类和模式检测的性能。我们将提出算法与现有最优算法进行了有效性和扩展性比较。性能评价指标包括延迟时间和吞吐量。针对聚类，我们对比研究所提出算法RJC和现有聚类算法SRJ与GDC在不同距离阈值ϵ和不同网格宽度lg条件下进行对比，其中一部分实验结果如下：

从上图可以观察出，我们提出的基于范围连接的聚类算法比其他算法具有更低的延迟和更高的吞吐量，从而验证了聚类算法的高效性。针对模式检测，我们基于四个参数（即轨迹数量Or，网格宽度lg，距离阈值ϵ和分布式机器数量N），评估了三个算法BA、FBA和VBA的性能。部分实验结果如下所示：

从上图中我们可以看出基准算法BA在一些条件下（譬如数据量变大）就不再适用。此外，FBA具有更低的延迟，而VBA具有更高的吞吐量。通过这部分实验验证了我们的算法和框架在轨迹流运动模式检测中的优势以及可扩展性。

04 总结

综上，本项目探讨了轨迹流数据上的Co-Movement运动模式实时挖掘，并首次提出了面向轨迹流数据的分布式共同运动模式实时检测框架ICPE，以克服以往共同模式挖掘只能针对历史轨迹数据进行检测的缺陷。此外，我们对聚类和枚举过程进行加速，从而有效地提高了ICPE的性能和扩展性。该框架可以被广泛地应用于未来模式预测、轨迹压缩以及基于位置的服务等。

回顾此研究项目初期，双方通过“下一代数据库技术”开启合作，先是基于阿里巴巴的AZFT实验室提供的大轨迹流数据，提出了基于Flink的两阶段轨迹流数据的共同运动模式实时检测框架ICPE，包括实时聚类和模式枚举；而后在此基础上，双方进一步考虑将本论文的轨迹共同运动模式挖掘算法和框架扩展至其他领域，如物流配送模式挖掘和社交属性挖掘等，进而将这些研究成果逐步应用于阿里的实际业务场景中。

文章来源: https://www.toutiao.com/group/6732693063778435588/