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

本文涉及的产品
云数据库 RDS MySQL,集群系列 2核4GB
推荐场景:
搭建个人博客
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
简介: 校企协作创造更多的学术与社会价值

导语:

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

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

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

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

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

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

头条封面图.jpg

论文现场poster展示图

2、技术点解析

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

01.jpg

Indexed Clustering and Pattern Enumeration(ICPE)框架

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

02.png

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是终止时间。非固定长度的字符串需要找到一个最长模式时间序列以满足(K, L, G)限制条件。非固定长度的为压缩算法利用最长模式时间序列技术,进一步提高了系统吞吐量,并降低了存储代价。然而,由于模式需要等待最长模式时间序列的发现才能被返回,因而系统响应时间增大。

3、实验结果

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

03.png

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

4.png

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

4、总结

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

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

相关实践学习
基于Hologres轻松玩转一站式实时仓库
本场景介绍如何利用阿里云MaxCompute、实时计算Flink和交互式分析服务Hologres开发离线、实时数据融合分析的数据大屏应用。
Linux入门到精通
本套课程是从入门开始的Linux学习课程,适合初学者阅读。由浅入深案例丰富,通俗易懂。主要涉及基础的系统操作以及工作中常用的各种服务软件的应用、部署和优化。即使是零基础的学员,只要能够坚持把所有章节都学完,也一定会受益匪浅。
目录
相关文章
|
12天前
|
存储 NoSQL 关系型数据库
非关系型数据库-MongoDB技术(二)
非关系型数据库-MongoDB技术(二)
|
12天前
|
NoSQL 关系型数据库 MongoDB
非关系型数据库-MongoDB技术(一)
非关系型数据库-MongoDB技术(一)
|
2月前
|
Java 关系型数据库 MySQL
"解锁Java Web传奇之旅:从JDK1.8到Tomcat,再到MariaDB,一场跨越数据库的冒险安装盛宴,挑战你的技术极限!"
【8月更文挑战第19天】在Linux上搭建Java Web应用环境,需安装JDK 1.8、Tomcat及MariaDB。本指南详述了使用apt-get安装OpenJDK 1.8的方法,并验证其版本。接着下载与解压Tomcat至`/usr/local/`目录,并启动服务。最后,通过apt-get安装MariaDB,设置基本安全配置。完成这些步骤后,即可验证各组件的状态,为部署Java Web应用打下基础。
42 1
|
2月前
|
SQL Java 关系型数据库
探索Java数据库连接的奥秘:JDBC技术全攻略
探索Java数据库连接的奥秘:JDBC技术全攻略
45 8
|
2月前
|
存储 缓存 负载均衡
【PolarDB-X 技术揭秘】Lizard B+tree:揭秘分布式数据库索引优化的终极奥秘!
【8月更文挑战第25天】PolarDB-X是阿里云的一款分布式数据库产品,其核心组件Lizard B+tree针对分布式环境优化,解决了传统B+tree面临的数据分片与跨节点查询等问题。Lizard B+tree通过一致性哈希实现数据分片,确保分布式一致性;智能分区实现了负载均衡;高效的搜索算法与缓存机制降低了查询延迟;副本机制确保了系统的高可用性。此外,PolarDB-X通过自适应分支因子、缓存优化、异步写入、数据压缩和智能分片等策略进一步提升了Lizard B+tree的性能,使其能够在分布式环境下提供高性能的索引服务。这些优化不仅提高了查询速度,还确保了系统的稳定性和可靠性。
62 5
|
2月前
|
Cloud Native 数据库 开发者
云原生数据库2.0问题之帮助阿里云数据库加速技术更新如何解决
云原生数据库2.0问题之帮助阿里云数据库加速技术更新如何解决
|
2月前
|
Cloud Native 关系型数据库 分布式数据库
云原生数据库2.0问题之PolarDB利用云计算技术红利如何解决
云原生数据库2.0问题之PolarDB利用云计算技术红利如何解决
|
2月前
|
关系型数据库 OLAP 分布式数据库
揭秘Polardb与OceanBase:从OLTP到OLAP,你的业务选对数据库了吗?热点技术对比,激发你的选择好奇心!
【8月更文挑战第22天】在数据库领域,阿里巴巴的Polardb与OceanBase各具特色。Polardb采用共享存储架构,分离计算与存储,适配高并发OLTP场景,如电商交易;OceanBase利用灵活的分布式架构,优化数据分布与处理,擅长OLAP分析及大规模数据管理。选择时需考量业务特性——Polardb适合事务密集型应用,而OceanBase则为数据分析提供强大支持。
211 2
|
24天前
|
存储 负载均衡 数据库
探索后端技术:从服务器架构到数据库优化的实践之旅
在当今数字化时代,后端技术作为支撑网站和应用运行的核心,扮演着至关重要的角色。本文将带领读者深入后端技术的两大关键领域——服务器架构和数据库优化,通过实践案例揭示其背后的原理与技巧。无论是对于初学者还是经验丰富的开发者,这篇文章都将提供宝贵的见解和实用的知识,帮助读者在后端开发的道路上更进一步。
下一篇
无影云桌面