暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / SIGMOD 2023 | Ghost: 分布式轨迹流高性能在线相似性查询通用框架

SIGMOD 2023 | Ghost: 分布式轨迹流高性能在线相似性查询通用框架

时空实验室 2023-09-25
106
轨迹相似性查询在各种移动定位程序中一直发挥着重要的作用，并且随着流式轨迹数据的不断增加，流式轨迹相似性查询逐渐成为一个热点问题。然而，现有的大多数研究都集中于解决离线数据集中的轨迹相似性查询，在线查询中的几个主要挑战仍未得到解决。本次为大家带来数据库与数据挖掘领域的顶级会议SIGMOD 2023的《Ghost: A General Framework for High-Performance Online Similarity Queries over Distributed Trajectory Streams》。

1. 背景
流式轨迹数据的相似性查询是流式轨迹数据挖掘的一个热点问题。轨迹数据的相似性查询依赖于轨迹相似性计算，但是轨迹相似性计算算法往往具有非常高的时间复杂度，所以为了优化算法时间复杂度，现有的流式轨迹数据相似性查询研究大部分聚焦于轨迹完整、轨迹间距离是静态的离线数据集。然而，现实世界的轨迹数据多数是实时生成的，为了更好地支持对数据新鲜度要求较高的应用，需要一个针对在线数据集的流式轨迹数据相似性查询方法。而在线查询目前主要面对三个挑战：1）如何在一个通用分析框架中支持多种常见的轨迹相似性衡量指标？2）如何实现在无边界且高速产生的轨迹流上的高效在线相似性查询？3）如何提高流处理的可拓展性？
基于以上分析，文章提出了一个分布式轨迹流在线相似性查询通用框架Ghost，Ghost很好的解决了上述挑战，支持：1）大量轨迹距离度量标准；2）快速在线相似性分析；3）分布式处理。
2. 问题定义
定义2.1 轨迹流
一个移动物体的轨迹流是以时间为序的GPS点序列。
定义2.2 轨迹相似关系
假设有轨迹流TR和TS，距离衡量标准D(·, ·)，距离阈值θ以及最近时间窗口L，如果DL(TR, TS) | = θ，那么则称TR和TS具有相似关系。
“｜=”的含义随距离衡量标准的不同而改变，例如：如果D(·, ·)代表的是DTW距离度量，那么“｜=”的含义为“≤”；如果D(·, ·)代表的是LCSS距离度量，那么“｜=”的含义为“≥”。
定义2.3 在线相似性搜索（OSS）
给定一个轨迹流数据集ST = {T1, T2, …, T|T|}，一个查询轨迹流TQ，距离函数D(·)，距离阈值θ和最近时间窗口L，OSS返回ST中所有在每个时刻t都满足DL(TQ, T) | = θ的轨迹流。
定义2.4 在线相似性连接（OSJ）
给定轨迹流数据集SP = {T1(P), …, T|P|(P)}以及SQ = {T1(Q), …, T|Q|(Q)}，距离函数D(·)，距离阈值θ和最近时间窗口L，OSJ返回SP × SQ中所有在每个时刻t都满足DL(TQ, T) | = θ的轨迹流对 (TP, TQ) 。
3. 方法概述
3.1 增量相似性计算
增量相似性计算的核心在于维护一个距离矩阵和一个相似性矩阵，每当接收到一个新的GPS点时，更新以上两个矩阵。
假设在当前时刻t有轨迹流TR = <a1, …, am> 和 TS = <b1, …, bn>，那么我们有：
其中，d(·, ·)代表点到点的距离（L2范式）。
假设在时间窗口L内T1有m个点，T2有n个点，那么距离矩阵为WTm1, Tn2, wi, j (1 ≤ i ≤ m, 1 ≤ j ≤ n)代表pi∈T1 和 pj ∈ T2­ 之间的距离；同样地，相似性矩阵的定义为V Tm1, Tn2，v­t,j = DTW(Ti1, Tj2)( 1 ≤ i≤ m, 1 ≤ j ≤ n).
基于以上条件，当接收到一个新的GPS点的时候，只需要更新距离矩阵和相似性矩阵中对应的行或列即可持续维护距离矩阵和相似性矩阵。
3.2 增量在线相似性计算（IOSC）
增量相似性计算在进行更新的时候事实上只需要某一相似度列参与运算，所以距离矩阵是可以省略的部分。通过动态计算距离矩阵的最后一列，可以减少存储开销。
受流处理的小批量策略启发，文章引入了时间偏移F来支持高效的距离更新。具体来说，就是在时间窗口[t – L – F, t]上维护用于增量距离计算的相似度矩阵V，F ≥0。当F为0时，得到实时轨迹间距离；当F>0时，将得到延迟的距离值。
图1详细介绍了IOSC的处理过程：算法的输入时轨迹流数据集ST、最近时间窗口长度L、时间偏移F和距离函数D。该算法首先初始化两个映射TD (整数为键，列表为值)和SC (整数为键，列表为值)为空。对于每个Ti∈ ST，它将键值对(i, Li= ∅)插入TD，其中Li存储在时间段[t − L − F, t]内到达的 Ti 的点，并添加 ((i, j), Li, j = ∅) 到SC，其中 Li, j 存储 Ti 和 Tj ( j ≠ i) 之间的最新相似度。接下来，对于每个到达点p = (id,t, l)，算法首先将 (p.t, p.l) 插入列表 TD[p.id] 中，然后计算 Tid 的时间长度，如果该长度超过L + F ，则删除过期点，并重新计算Tid 与其他流轨迹 Tj 之间的距离，即重新计算SC[( j, p.id)] 和 SC[(p.id, j)]。否则，对于每个剩余的𝑇𝑖，算法首先计算𝑝𝑖𝑑和每个𝑞∈𝑇𝑖之间的点对点距离，然后根据前一列 SC[(𝑖, 𝑝.𝑖𝑑)]计算新的相似性列𝐿𝑐。最后，更新𝑇𝑖和𝑇𝑖𝑑之间的距离。

图1 IOSC

3.3 基于直方图的相似性计算
基于直方图的相似性计算的核心在于建立一个动态直方图索引以及设计一个支持多个剪枝界限的算法。
对于动态直方图索引，具体来说，就是给定一个二维自由空间F，通过将F划分为M·N个不相交的等宽网格单元来构造直方图空间H，其中每个单元的宽度为δ。每个单元也称为直方图桶 hi ∈ H (1 ≤ i ≤ M · N)。接下来，通过计算位于每个桶 hi 中的 T 的样本点数量，将每个轨迹流 T 转换为轨迹直方图 HT 。这种索引构建非常高效，因为每个传入点都以时间复杂度 O(1) 插入到索引中。
给定轨迹 R 及其排序轨迹直方图 HR，算法HAS的目标是当前 M 个桶中的点的数量满足条件时找到 HR 的第 M 个桶，记为KM。在检测M的过程中，每个桶都有一个距离界限θm（1≤ m ≤ M）。θm的定义如下：
给定轨迹 T 和预定义的距离阈值 θd ，计算位于其前 m 个桶中的样本点的数量，以获得相应的距离界限 θm，其中 1 ≤ m≤ M。因此，可以得到一系列距离界限。HAS的伪代码如图。

图2 HAS

3.4 CostPartitioner
为了更好地支持分布式处理以及工作负载均衡，文章提出了Cost Partitioner，CostPartitioner的核心思路是平衡每个Flink任务需要处理的轨迹数量。
图3给出了 CostPartitioner 的伪代码，它以一组历史轨迹 S、Flink 任务的数量 P 和直方图空间 H 作为输入。该算法首先将两个映射 BC 和 GP 初始化为空（它们都使用整数作为键和整数作为值）。 BC 存储每个桶中的样本点数量，GP表示每个桶所属的 Flink 任务 ID。然后，算法对历史轨迹数据集进行采样，并在样本数据上构建动态直方图索引。接下来，它计算每个桶中的点数，并计算需要分配给每个任务的平均点数（即 AveCount）。然后，算法将至少具有 AveCount 点的每个桶分配给单个 Flink 任务并重新计算AveCount。通过调用01背包算法，将剩余样本数量少于 AveCount 的桶聚合为子任务。

图3 CostPartitioner

4.实验
实验数据集由三部分组成：T-Drive数据集、AIS数据集以及由前两者合成的Brinkhoff数据集。与baseline相比，Ghost不仅获得了 6-20 倍的效率提升和一个数量级的内存开销节省，还实现了在Flink上的3–8 倍工作负载平衡增益，并且表现出较低的参数敏感性和高鲁棒性。以下是部分实验数据。
图4 在参数F上的效率数据
图5 内存开销实验数据
5.总结
文章提出了一种增量在线相似性计算（IOSC）机制来加速成对轨迹流距离计算，该机制支持广泛的轨迹距离度量。与之前的研究相比，IOSC将轨迹长度方面的处理复杂度从二次降低为线性。在此基础上，文章提出了基于直方图的算法，该算法利用直方图索引和一系列剪枝界限来实现轨迹流的相似性搜索和连接。最后，这个方法也被扩展到分布式平台 Flink 以实现可扩展性，并且开发了CostPartitioner ，确保并行处理和工作负载平衡。实验表明，与baseline相比，Ghost不仅获得了 6-20 倍的效率提升和一个数量级的内存开销节省，还实现了在Flink上的3–8 倍工作负载平衡增益，并且表现出较低的参数敏感性和高鲁棒性。
-End-
本文作者
陈泽超
重庆大学物联网工程专业在读三年级本科生，重庆大学START团队成员。主要研究方向：时空数据索引。

重庆大学时空实验室（Spatio-Temporal Art Lab，简称Start Lab），旨在发挥企业和高校的优势，深入探索时空数据收集、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！年度有2~3名研究生名额，欢迎计算机、GIS等相关专业的学生报考！

直方图矩阵管理相似性矩阵
文章转载自时空实验室，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论