ACM SIGSPATIAL 2021: 时空伴随之分布式时空k邻近连接（附视频、论文和PPT）

时空实验室 2021-11-11

689

是否突然发现健康码变为黄色，或者收到信息称自己是确诊患者的“时空伴随者”？新冠疫情形势依然严峻，防控仍在进行。如何才能快速找到确诊患者的“时空伴随者”来进行精准防控？本篇文章将带来被国际顶级的空间数据智能会议ACM SIGSPATIAL 2021成功接收的、重庆大学与京东智能城市研究院、武汉大学、西安电子科技大学、西南交通大学合作的论文：《Distributed Spatio-Temporal k Nearest Neighbors Join》，作者为：Ruiyuan Li, Rubin Wang, Junwen Liu, Zisheng Yu, Huajun He, Tianfu He, Sijie Ruan, Jie Bao, Chao Chen, Fuqiang Gu, Liang Hong, Yu Zheng。

1.问题背景

随着定位技术的飞速发展，产生大量的时空数据。在时空数据分析中，𝑘邻近连接是最常见的操作之一，生活中经常使用到它，比如在疫情防控的情况下，当出现一名感染患者时，采用kNN Join找到感染患者记录点最近的人群，称他们为患者的密切接触者，需要被隔离，防止疫情的扩散。

但现有的解决方案只考虑空间接近度，故提出了时空k邻近连接（ST-kNN Join），它同时考虑空间接近度和时间同时性，找到给定时空记录点的k个最近的记录点。在疫情防控时，如图1所示，给定一名感染患者u1，寻找其密切接触者。只考虑空间接近度的情况下，可以在p1区域中找到u2，p2区域中找到u2和u3，p3区域中找到u3。因此u2和u3都属于u1的密切接触者，应该被隔离。但是如果考虑时间的同时性，那么u3不再是u1的密切接触者，因为u1在p3区域出现的时间为t7，而u3在p3区域出现的时间为t2。也就是说，只有u2才是密切接触者，这样便带来了更加精准的疫情防控措施。除了疫情防控外，ST-kNN还可以应用于许多其他的领域，例如拼车、同伴检测和旅行推荐。

图1：流感预防

但是执行ST-kNN Join仍有三个方面的挑战：1）数据量庞大。时空数据以极高的频率不断产生，导致数据量极大；2）维度较高。时空数据除了空间信息，还加入了时间信息，数据处理使用变得困难；3）多种数据类型，时空数据包含各种数据类型，除了基本的数据点（例如GPS点）外，还有以线的形式存在的轨迹，以及以多边形的形式存在的驻留区域，如图2所示。

图2：各种几何类型数据

对于以上问题，我们采用分布式处理框架来应对庞大的数据量，并且提出了一种基于Apache Spark的新型分布式解决方案，它有效地支持各种数据类型来进行ST-kNN Join的计算。

2.基本框架

图3展示了我们提出的 ST-kNN Join解决方案的框架，它包括四个主要步骤：1）数据分区；2）第一轮本地连接；3）第二轮本地连接；4）结果合并。

图3：ST-kNN Join框架

我们将数据集S分成几个时空分区（ST-partitions），为了实现良好的负载均衡，每个分区的对象数量几乎相同。具体做法为：首先随机提取一部分样本对象S’，然后采用扫描线算法划分α个时间分区；基于四叉树划分β个空间分区。这样共划分α*β个互不相交且样本数量大致相等的时空分区，最后将每个对象s划分到时空分区中，若与多个时空分区交叉则复制到每个交叉的分区中。

第一轮本地连接会对每个时空分区建立两个本地索引：时间范围计数索引（TRC-index）和3D R-tree索引。对于非点时空对象r，可以通过这两个索引确定每一个在该分区的对象r所在的扩展时间范围（ETR）和扩展空间区域（EMBR）。之后会详细介绍时间范围计数索引（TRC-index）机制。

第二轮本地连接将基于r的ETR和EMBR检查上一步计算出与扩展时空区域相交的所有时空分区，在所有满足的时空分区中基于3D R-Tree执行kNN搜索，生成一组r对应区域局部的ST-kNN。

最后对于每个对象r对应的多个局部ST-kNN结果合并成为一个全局结果，在这个过程中我们对其进行了优化。

3.时间范围计数索引（TRC-index）

为了确定一个分区是否至少包含k个满足时间同时性要求的对象，我们提出一种新的轻量级索引结构，称为时间范围计数索引（TRC-index，Time Range Count Index）。它可以有效地得到所给ETR的最小交叉时间范围数。简单来说，当我们得到了给定时间范围tr不相交的时间范围的上限数N，就可以计算获得与tr相交的时间范围下限数|S_i| - N。如图4(a)所示，有五个时间范围数据，即|S_i| = 5，计算每个时间区域中包含的tr开始和结束的数量并保存，如图4(b) 和4(c)。对于待查询的ETR，可以很快地找到开始时间大于ETR的最大时间的时间范围数量，以及结束时间小于ETR开始时间的时间范围数量（即与ETR不相交的时间范围数）。图4(d)中ETR所对应图4(a)不相交的时间范围{tr₁,tr₄,tr₅}。之后可以计算出与所给ETR相交的时间范围的下限数为2。

图4：TRC-index图示

利用TRC-index，我们可以快速且有效地找到S_i中与所给tr相交的时间范围的最小数量。由于TRC-index为轻量级索引，在消耗极小资源的情况下，能够很好地广播到所有分区中。

4.合并优化

在两轮局部连接操作之后，我们在每个ST分区中获得了r的局部kNN结果。为获取全局结果，我们需要对局部结果进行合并操作。在合并过程中，需要利用shuffle操作，将相同r的局部结果重新分区到一个新分区后组合成全局结果。一个对象会被分配到多个ST分区，所以在不同的结果中可能存在重复的组合。

为了减少网络传输的资源消耗，本文采取先删除重复项再进行重新分区。如图5所示，假设出现如下组合(r, s)出现在时空分区0,1,2中，我们将r的ETR和s相交部分的开始时间称为时间参考点(temporal reference point, TRP)，将r对应的EMBR和s所在的MBR相交的左下角点称为空间参考点(spatial reference point, SRP)。我们只保留同时包含TRP和SRP的时空分区内的结果（即图5中保留时空分区0）。

图5：删除重复项

5.实验评估

我们使用三个真实的数据集来验证ST-kNN Join的效果，数据的统计如下表1所示。

表1：静态数据集

表2显示了用来测试参数的几何组合，旨在找出引入参数的影响。

表2：用于参数测试的几何数据集

表3为实验中测试的参数，默认值用黑体表示。

表3：参数设置

我们采取控制变量的方法，对表3中每一个参数进行测试。主要记录不同数据的执行时间(Execution Time, ET)、R和S的复制扩增(Copy Amplification, CA)和命中率(Hit Rate, HR)三个方面。结果如下图表示。我们可以明显看出在划分时空分区的时候需要选择合适的α，β参数，参数过小使得分区内的执行时间长，而参数过大使得时空分区过小从而降低命中率。binNum的增加可以提高TRC-index的精确度，而且TRC-index是轻量级索引，本身对资源消耗可以忽略不计。

图6：关于参数α的影响

图7：关于参数β的影响

图8：关于参数binnum的影响

图9：关于参数𝛿的影响

图10：关于参数k的影响

我们还对每一种几何数据每一步的运行时间进行了记录，如下图。明显看出多数情况下，第一轮本地连接的执行时间较长，因为这个阶段我们要进行索引的构建。此外，py-py组合在第一轮本地连接时的执行时间远小于其他数据类型。可能是因为滴滴的时空数据集分布稀疏，亦或者因为其数据量较小。

图11：各种数据集每一阶段的效率

我们对比了各种框架下的效率。ST-kNNJ是本文提出的最终框架。我们重写了Simba和LocationSpark两种框架的代码，使其支持进行ST-kNN Join的计算。将这两种框架和本文的框架(ST-kNNJ)以及采用R树的ST-kNNJ_R和不进行合并优化的ST-kNNJ_nr进行比较，结果如下图所示。可明显看出相比其他框架，ST-kNNJ有着不错的效果。

图12：各种框架效率

系统Demo链接：http://stknnjoin.urban-computing.com/

关注公众号，回复"ST-kNNJ"，下载PPT和论文

重大时空团队（CUST，Chongqing University Spatio-Temporal group）吸收企业和高校的优势，深入探索时空数据接入、存储、管理、挖掘、可视化相关技术，并积极推进学术成果在产业界的落地！目前尚有两个研究生名额，欢迎计算机、GIS等相关专业的学生报考！

数据库

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