海量地铁乘客轨迹相似性连接方法：以深圳地铁为例.pdf

海量地铁乘客轨迹相似性连接方法:以深圳地铁为例*王星苏1,熊 文1,张 瑞2(1.云南师范大学信息学院,云南 昆明 6 5 0 5 0 0;2.深圳北斗应用技术研究院有限公司,广东 深圳 5 1 8 0 0 0)摘 要:当前主要的轨迹相似性连接方法都以G P S轨迹为研究对象。针对G P S轨迹的优化方法无法直接用于解决地铁乘客轨迹相似性连接的问题,充分利用地铁乘客轨迹的时空特征,借助轨迹的重复性和对称性,将轨迹从点序列转化为O D序列。以O D序列为基础的轨迹,长度是原轨迹的一半,对应的索引空间变小,后续的计算量也随之减少。着重研究了基于P P J o i n+的轨迹连接算法在S p a r k平台上的设计与实现。在一个1 3结点S p a r k集群和一个包含5 0 0万个乘客轨迹集合(5.6亿条刷卡记录)的超大规模数据集上验证了该算法的有效性。实验结果显示,基于O D序列的P P J o i n+算法的执行时间为1 4.0 m i n,比默认的点序列轨迹连接算法的节约了6 2.5%,比D i m a连接算法的节约了7 8.2%,并表现出了良好的可扩展性。关键词:轨迹相似性;地铁系统;P P J o i n+;S p a r k中图分类号:T P 3 9文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 3.0 8.0 0 7A m a s s i v e s u b w a y p a s s e n g e r t r a j e c t o r y s i m i l a r i t y c o n n e c t i o n m e t h o d:A c a s e s t u d y o f S h e n z h e n m e t r o WANG X i n g-s u1,X I ONG W e n1,Z HANG R u i2(1.S c h o o l o f I n f o r m a t i o n S c i e n c e a n d T e c h n o l o g y,Y u n n a n N o r m a l U n i v e r s i t y,K u n m i n g 6 5 0 5 0 0;2.S h e n z h e n I n s t i t u t e o f B e i d o u A p p l i e d T e c h n o l o g y,S h e n z h e n 5 1 8 0 0 0,C h i n a)A b s t r a c t:T h e c u r r e n t m a i n t r a j e c t o r y s i m i l a r i t y c o n n e c t i o n m e t h o d s a r e b a s e d o n G P S t r a j e c t o r i e s.O p t i m i z a t i o n m e t h o d s f o r G P S t r a j e c t o r i e s c a n n o t b e d i r e c t l y a p p l i e d t o t h e p r o b l e m o f c o n n e c t i n g s u b-w a y p a s s e n g e r t r a j e c t o r i e s.B y f u l l y u t i l i z i n g t h e s p a t i o t e m p o r a l c h a r a c t e r i s t i c s o f s u b w a y p a s s e n g e r t r a-j e c t o r i e s a n d l e v e r a g i n g t h e t r a j e c t o r y s r e p e t i t i v e n e s s a n d s y mm e t r y,t h e t r a j e c t o r y i s t r a n s f o r m e d f r o m a p o i n t s e q u e n c e t o a n O D s e q u e n c e t o r e d u c e t h e t r a j e c t o r y l e n g t h a n d s a v e s t o r a g e s p a c e.T h i s p a p e r f o c u s e s o n t h e d e s i g n a n d i m p l e m e n t a t i o n o f t h e t r a j e c t o r y c o n n e c t i o n a l g o r i t h m b a s e d o n P P J o i n+o n t h e S p a r k p l a t f o r m.T h e m e t h o d i s v a l i d a t e d o n a 1 3-n o d e S p a r k c l u s t e r a n d a l a r g e-s c a l e d a t a s e t c o n t a i n-i n g 5 m i l l i o n p a s s e n g e r t r a j e c t o r i e s(5 6 0 m i l l i o n t a p r e c o r d s c o l l e c t e d i n t w o c o n s e c u t i v e m o n t h s).T h e e x p e r i m e n t a l r e s u l t s s h o w t h a t t h e P P J o i n+a l g o r i t h m b a s e d o n O D s e q u e n c e o n l y t a k e s 1 4.0 m i n u t e s,w h i c h s a v e s 6 2.5%o f t h e e x e c u t i o n t i m e c o m p a r e d t o t h e d e f a u l t p o i n t s e q u e n c e t r a j e c t o r y c o n n e c t i o n a l g o r i t h m a n d 7 8.2%o f t h e e x e c u t i o n t i m e c o m p a r e d t o t h e D i m a c o n n e c t i o n a l g o r i t h m,a n d e x h i b i t s g o o d s c a l a b i l i t y.K e y w o r d s:t r a j e c t o r y s i m i l a r i t y;m e t r o s y s t e m;P P J o i n+;S p a r k*收稿日期:2 0 2 2-0 6-0 9;修回日期:2 0 2 2-0 9-2 3基金项目:国家自然科学基金(6 1 8 6 2 0 6 6)通信作者:熊文(w e n.x i o n g h o t m a i l.c o m)通信地址:6 5 0 5 0 0 云南省昆明市云南师范大学信息学院A d d r e s s:S c h o o l o f I n f o r m a t i o n S c i e n c e a n d T e c h n o l o g y,Y u n n a n N o r m a l U n i v e r s i t y,K u n m i n g 6 5 0 5 0 0,Y u n n a n,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 5卷第8期2 0 2 3年8月 V o l.4 5,N o.8,A u g.2 0 2 3 文章编号:1 0 0 7-1 3 0 X(2 0 2 3)0 8-1 3 8 3-1 01 引言轨道交通系统凭借高速、舒适、准时等特点,已经成为城市居民出行的主要方式。随着城市人口不断增加和路网规模不断扩大,轨道交通系统客流量不断增加。以深圳地铁2 0 1 8年9月的数据为例,自动售检票系统A F C(A u t o F a r e C o l l e c t i o n)检票口每天平均采集到5 0 0万人次的刷卡记录。每张智能卡的刷卡记录按时间排序就形成了乘客的历史轨迹。如何理解百万级别乘客的出行需求和时空特征是轨道交通精细化运营的前提,而海量轨迹相似性计算方法是乘客时空特征分析和挖掘的基础。现有研究围绕基于阈值、基于t o p-k和基于距离 的 轨 迹 连 接T S-J o i n(T r a j e c t o r y S i m i l a r i t y J o i n)问题进行了大量的探索和实践。轨迹连接涉及2方面的问题,分别是轨迹相似性度量的选择和大规模轨迹相似性计算的优化。常用的轨迹相似性度量有动态时间规整距离(D y n a m i c T i m e W r a p p i n g)1、最 长 公 共 子 序 列(L o n g e s t C o mm o n S u b s e q u e n c e)2、实际编辑距离(E d i t D i s t a n c e o n R e a l s e q u e n c e)3和真实惩罚编辑距离(E d i t D i s t a n c e w i t h R e a l P e n a l t y)4等。杰卡德相似性度量及其考虑时空属性扩展的方法5也可以用来衡量轨迹的相似性。大规模轨迹相似性连接的计算过程主要涉及2类优化措施。第1类是基于集合属性的优化技术,第2类是基于时空属性的优化技术。第1类方法主要有P P J o i n+(P o s i t i o n a l f i l t e r i n g w i t h t h e P r e f i x f i l t e r i n g-b a s e d J o i n)6、E d-J o i n(E d i t J o i n)7和A d a p t J o i n8等。这类方法的特点是采用倒排索引、长度过滤、前缀过滤等作为优化措施。第2类方法主要有D I T A(D i s t r i b u t e d I n-m e m o r y T r a j e c t o r y A n a l y t i c s)9、D I S ON(D i s t r i b u t e d I n-m e m o r y t r a j e c t o r y s i m i l a r i t y S e a r c h a n d j o i n O n r o a d N e t w o r k)1 0和J U S T-J o i n1 1等。这类方法的特点是利用轨迹时空属性构建二级索引机制来进行优化。现有的T S-J o i n方法主要针对来自手机终端和地面车辆的G P S轨迹数据。这些针对G P S轨迹时空特征的优化措施,无法直接应用在轨道交通乘客轨迹的相似性连接问题中。以轨道交通乘客的刷卡记录形成的地铁轨迹为例,其与G P S轨迹相比有以下4个不同特征:(1)空间固定性。地铁乘客轨迹空间维度单元的站点是固定不变的,而G P S轨迹点的地理位置通常具有随机性。(2)高度稀疏性。刷卡轨迹记录的一次行程只有起点站和终点站2个“点”,而地面车辆一次行程对应的轨迹包含很多密集的G P S时空点。(3)O D(O r i g i n t o D e s t i n a t i o n)拓扑特征。乘客的一次行程一定包含“进站”和“出站”2条刷卡记录。一组时间上连续的进 站-出 站 组 合 即 认 为 是 一 个 轨 迹 段O D。(4)对称重复性。地铁乘客的出行规律会导致轨迹出现一定的对称重复性。以某位通勤乘客1天的上下班行程为例,早上A站进B站出,傍晚B站进A站出,且1个月内有2 0次相同的行程。由于地铁乘客轨迹时空特征与G P S轨迹时空特征明显不同,上述针对G P S轨迹的相似性连接方法很难直接用于解决地铁乘客轨迹的相似性连接问题。所以,本文尝试借助集合相似性连接方法来实现地铁乘客轨迹的相似性连接。这些方法的对比研究中,文献1 2 的实验结果表明,P P J o i n+在杰卡德距离上可以达到最好的实验效果,同时该算法也支持重叠相似度(O v e r l a p S i m i l a r i t y)、编辑距离(E d i t D i s t a n c e)和余弦相似度(C o s i n e S i m i-l a r i t y)等相似性度量方法。因此,本文使用P P J o i n+算法来解决地铁轨迹乘客的相似性连接问题。目前,还没有公开发表的文献讨论地铁乘客轨迹相似性连接的问题。本文充分探索地铁乘客轨迹的时空特征,在S p a r k平台上实现了基于P P J o i n+的地铁乘客轨迹相似性连接算法。该算法的核心是借助地铁乘客轨迹的拓扑特征,将轨迹从点序列转换为O D序列,缩短了轨迹长度;然后,借助轨迹的集合属性,进行长度过滤、前缀过滤等剪枝方法缩小轨迹对的候选集;最后,与在S p a r k上实现的相似性查询处理系统D i m a1 3进行对比。具体来讲,本文的主要工作有如下3点:(1)提出了一种基于O D的地铁乘客轨迹相似性度量方法,基于地铁乘客轨迹的拓扑特征,将原始轨迹从点序列转化为O D序列,缩短了轨迹长度,进一步减少了后续计算过程中轨迹占用的存储空间和计算量。(2)在S p a r k平台上实现了P P J o i n+算法来解决地铁乘客轨迹集合的相似性连接问题。借助轨迹的集合属性,利用倒排索引、长度过滤和前缀过滤等剪枝方法生成记录的自索引和相似索引,以加速地铁乘客轨迹的相似性连接。(3)在一个超大规模真实数据集和一个1 3结4831C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 3,4 5(8)点的S p a r k集群上验证了该方法。实验结果表明,对5 0 0万条轨迹进行相似性连接,执行时间只需要1 4 m i n,与默认算法的相比节约了6 2.5%,与D i-m a的相比平均节约了7 8.2%。并且,本文提出的方法在大规模数据环境下表现出了良好的可扩展性。2 背景和动机2.1 轨道交通大数据平台随着城市居民数量不断增长和地铁路网的不断扩张,传统的信息化设施已经不能满足地铁精细化运营的需求。因此,运营管理者开始构建新一代信息化基础设施 轨道交通大数据平台,尝试系统地使用大数据、物联网和人工智能等相关技术,充分利用数据资源来提升地铁的运营水平。以深圳地铁集团轨道交通大数据平台为例,大数据平台分为4个部分。最底层为数据采集层,是由多个不同传感网络构成的数据采集传输系统,这些典型的数据有动态的A F C刷卡记录和传感器数据、静态的列车调度和排班到站信息。第2层为数据仓库层,是以多源异构数据为基础构建的不同主题库。第3层为算法层,提供了一系列通用的大规模数据处理、数据挖掘算法,例如轨迹聚类算法。最上层为应用层,主要负责提供实时监控、地铁运营、车辆调度、应急管理、智慧警务和公共服务等功能。2.2 乘客群体移动时空特征轨道交通系统每天高速运转,为城市居民出行服务。深入理解数以百万计乘客的出行需求和时空特征是地铁路网规划、区间车调度、应急管理、智慧警务的基础。海量的历史和增量A F C刷卡记录既包含了个体移动的时空特征,也包含了城市居民群体移动的规律,隐藏着巨大的价值。例如,通过轨迹相似性分析可以了解城市居民职住地和日常通勤时空特征,以进一步指导地铁线网规划;在智慧警务领域,可以根据轨迹相似性判断犯罪嫌疑人的团伙,为警察断案提供决策依据。因此,对海量乘客的轨迹进行深入细致的挖掘和分析显得尤为迫切。但是,百万级轨迹的相似性连接面临着算法和算力2方面的挑战。因为已有的轨迹相似性连接方法都以地面G P S轨迹为研究对象,一系列优化方法不能直接运用于地铁轨迹的相似性计算。传统的数据库技术和单结点的计算资源也无法满足实际计算需求。因此,本文借助S p a r k大数据计算引擎和经典的P P J o i n+算法来实现百万级轨迹的相似性连接。3 问题定义地铁乘客轨迹的相似性连接研究的目的是找出具有相似特征的轨迹集合,挖掘乘客的伴随状态。地铁刷卡记录的行程轨迹具有独特的时空特征。具体来讲,一组时间上连续的进出站即可认为是一次行程,一次行程包含一个起点站和一个终点站。本文充分利用地铁轨迹独特的时空特征,在分布式计算引擎S p a r k上实现了百万级别乘客地铁轨迹相似性连接算法。整个过程包含一系列数据预处理和计算过程,例如对刷卡记录的分组排序、切割、合并;轨迹对过滤;相似性计算等。为了更精确地描述整个数据处理过程,首先给出以下4个定义:定义1(乘客轨迹点)乘客轨迹点是具有卡号i d、检票时间t i m e、检票站点s t a t i o n及检票类型t y p e 4个属性的时空点。定义乘客迹点P如式(1)所示:P=i d,t i m e,s t a t i o n,t y p e (1)定义2(基于点的地铁乘客轨迹)基于点的地铁轨迹P T(P o i n t-b a s e d T r a j e c t o r y)指的是每位乘客按照刷卡时间戳排序形成的轨迹点序列。数据预处理阶段会解决由于设备不稳定、乘客逃票等原因导致的数据异常情况,例如进站或出站行程缺失,同一站点进出等。P T定义如式(2)所示:P T=i d,P1,P2,Pn (2)定义3(基于O D的地铁乘客轨迹)基于O D的轨迹O DT(O D-b a s e d T r a j e c t o r y)以基于点的轨迹为基础,经过一系列转化而成。首先,对基于点的轨迹进行异常处理;然后,将一组既满足时间上连续也满足进站出站逻辑的2个点认定为一个O D,如式(3)所示;最后,经过切割、合并和时间规整,得到基于O D的地铁轨迹。假设点轨迹P T的长度为n,O DT的长度缩短为n/2。O DT定义如式(4)所示:O D=PO,PD (3)O DT=i d,O D1,O D2,O Dn/2 (4)其中,O D代表一组时间上连续的进站-出站组合,PO代表一次行程的进站点,PD代表一次行程的出站点。5831王星苏等:海量地铁乘客轨迹相似性连接方法:以深圳地铁为例定义4(时空倒排表)以O DT中前I个O D为前缀,时空倒排表的索引包括某个前缀O D、该前缀位于该O DT中的位置,以及以该前缀为分界,相应O D T的后缀长度3部分。索引数量为w。表1描述了基于O D的多属性时空倒排表,表中的一行代表一个桶(B u c k e t)。以索引(O Dw,i,p)为例,其中,i表示O Dw在该轨迹序列中的位置,p为O Dw所在位置的后缀长度,即轨迹总长度减i。该索引对应的轨迹集均有2个特征:(1)桶里所有轨迹的第i个轨迹段均为O Dw;(2)以O Di为分界,轨迹后缀长度为p,总长度为w+p。T a b l e 1 O D-b a s e d s p a t i o t e m p o r a l i n v e r t e d t a b l e表1 基于O D的时空倒排表i n d e xB u c k e tO D1,3,9i d2,i d7,i duO Dw,i,pi d5,i d9,i dv4 轨迹相似性连接方法本文基于地铁A F C刷卡数据完成乘客轨迹的相似性连接,具体步骤如图1所示。首先进行数据预处理得到基础轨迹;然后充分利用地铁轨迹的时空特征,生成基于O D的轨迹;再通过一系列过滤方法建立索引,获取高相似对候选集;最后以基于O D的轨迹相似性度量方法进行计算,得到每个乘客对应的伴随状态乘客集合。F i g u r e 1 T e c h n o l o g y r o a d m a p图1 技术路线图4.1 数据预处理原始的A F C刷卡记录存在一系列冗余信息和数据质量问题。例如,刷卡记录中混杂了刷卡充值记录、消费记录和公交车刷卡信息。设备老旧、乘客逃票、网络不稳定、软件功能不合理等因素,会导致读卡失效或数据传输失败,票卡数据集存在站点名异常、轨迹点重复、记录缺失等一系列数据质量问题。为了准确地计算乘客地铁轨迹相似性,首先要对原始刷卡记录进行预处理。数据预处理主要包括:过滤地铁进出站刷卡记录,纠正异常站点名,剔除含空值、重复值的轨迹点。需要特别说明的是,使用文献1 4 中的基于乘客出行模式规律的方法对缺失的刷卡记录进行填充。4.2 基于O D的轨迹生成A F C刷卡数据集中的进出站属性使地铁轨迹拥有独特的时空特征,例如O D属性、对称性和重复性等特点。并且,地铁系统每晚都会关闭停止服务。本文借助这些特征来解决异常O D的问题。异常问题包括:O D中进站或出站信息缺失、同站进出、进站以后间隔2 4 h才出站。针对以上问题,剔除了行程缺失的O D,并保留同一天O D时间跨度在1 8 h内的轨迹段。为使后续索引表的长度可控,本文对剩下的每一个轨迹点按图2完成时间规整。F i g u r e 2 T r a n s f o r m a t i o n o f t i m e s e q u e n c e图2 时间序列转换将连续的时间转为离散值,转换以后相同时间的2个轨迹点可确保时间差不超过1 0 m i n,从而降低比较成本,且阈值可以调整。对基于点的轨迹以O D为单位切割,最后生成基于O D的轨迹。假设点轨迹长度为n,O D轨迹生成算法的时间复杂度为O(n),空 间复杂度为O(n)。具体用到 的S p a r k算子如图3所示。其中,s e g T r a是输入为基于点的轨迹,输出为基于O D的轨迹的函数。F i g u r e 3 O D-b a s e d t r a j e c t o r y g e n e r a t i o n图3 基于O D的轨迹生成4.3 获取相似对候选集并验证本文主要采用以杰卡德相似度为基础的长度6831C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 3,4 5(8)过滤、前缀过滤、后缀长度与位置信息过滤3种剪枝方法6,1 5,筛选出可能达到相似度阈值的轨迹对并将其存入时空倒排表。以轨迹序列TS和TC为例,2个轨迹的杰卡德相似度如式(5)所示:S i mJ a cTS,TC =TSTCTSTC(5)将P P J o i n+算法归纳为生成自时空倒排索引表和 相 似 时 空 倒 排 索 引 表2部 分,索 引 均 为(O Dw,i,p)。自时空倒排索引表S S I I(S e l f S p a t i a l-t e m p o r a l I n v e r t e d I n d e x)指的是按照相同的索引生成规则,每条轨迹产生一个或多个自索引。再以自索引为键对卡号进行分组聚合操作,得到主键为轨迹自时空索引的倒排表,同一个桶里的轨迹至少有一个相同的O D,自时空索引所对应的桶一定是真实有效的。相似时空倒排 索引表C S I I(C a n d i d a t e S p a t i a l-t e m p o r a l I n v e r t e d I n d e x)指的是对每条轨迹进行推算,得到可能与自己相似的其他轨迹的索引集合,此时表的主键为轨迹i d,再将索引集合字段的值逐个切分为多行,得到表的外键。最后基于自时空倒排索引表的主键和相似时空倒排索引表的外键将2个表进行连接,过滤重复i d对,得到可能相似的i d对候选集并验证。自时空倒排索引表由基于轨迹长度和前缀的剪枝技术生成。设有TS和TC,Lx表示卡x轨迹的长度,若LSLC,两者的并集不会小于LS,交集不会大于LC。假设杰卡德相似性阈值为J,那么有式(6):LSLCJ(6)在长度过滤的基础上,进一步用前缀剪枝限制轨迹索引的数目,生成更少的候选轨迹。仅仅 以 前 缀O D为 索 引 的 倒 排 表 里,每 个O Dw对应的桶都包含多个必须相互比较的轨迹。为缩小倒排表的长度,前缀长度Lp取值需尽量小。设TS表示某个轨迹,T是所有轨迹的集合。若TS与轨迹集合T中的任意轨迹Tt都有式(7):S i mJ a cTS,Tt J(7)先确定此种情况发生时J的最大值为Jm a x。交集最大值为LS减去前缀长度,并集最小值为LS,故此种情况发生时,有式(8):Jm a x=LS-iLS(8)当J取值大于Jm a x时可规避上述情况。TS的前缀长度取值如式(9)所示:LSp=1-J LS+1(9)前缀中的O D就是原始自时空倒排表的索引,对应的桶里保存了轨迹前缀中含有该索引的所有卡号集 合。自 时 空 索 引 生 成 的 空 间 复 杂 度 为O(LS)。相似时空倒排索引表由基于O D位置和长度信息的剪枝生成。在自时空索引的基础上,如果不仅以前缀O D为索引,还在其后加入该O D在当前轨迹中的位置及对应的后缀长度,即索引由O Dw变为O Dw,i,p ,该索引对应的桶中任一轨迹的第i个轨迹段均为O Dw,且该轨迹的长度均为i+p。那么可以通过规避相似却没有公共索引的情况来推算与之相似的其余轨迹索引集合。设有轨迹TS和TC,由式(9)得到各自前缀长度LSp和LCp,前缀索引下标分别为i和j。TS的前缀和TC的前缀各不相同,p、q分别为2个轨迹的后缀长度。为了不漏掉这种特殊情况,令其最大相似度大于阈值J,即可得到相似索引。当pq,TS和TC交集的最大值为LS-i+1-(p-q)。由式(1 0)可知,TS和TC交集最大值取值为q+1,而TS和TC并集最小值取值为LS+j-1。LS=i+p(1 0)当pq,其最大相似度的推导过程与上文类似,不再赘述。若TS和TC的杰卡德相似度达到阈值J,式(1 1)必成立。Jq+1LS+j-1,pqLS-i+1i+j-1+q,pq(1 1)TS的相似时空索引集合元素形如(O DSw,j,q)。若TC的自时空索引(O DCi,i,p),i1,LCp属于TS的相似时空索引集合,那么TC将被认为是TS的相似候选轨迹。剪枝生成时空倒排索引表的步骤如下所示:输入:轨迹集合、杰卡德相似度阈值。输出:自时空索引表、相似时空索引表。步骤1 按O D在全局的出现频次排序;步骤2 基于式(9)生成前缀子串;步骤3 以前缀元素的当前位置i和后缀长度p建立循环;步骤4 在循环内以式(1 1)迭代生成相似时空索引;7831王星苏等:海量地铁乘客轨迹相似性连接方法:以深圳地铁为例步骤5 基于式(1 1)迭代完成后生成自时空索引,直到前缀子串遍历完成。对候选集大小进行估计发现,相似索引个数与前缀子串长度以及j、q的取值范围有关。提高轨迹质量、增强轨迹语义和缩短轨迹长度能够有效限制候选集的大小。假设有源轨迹TS,由式(9)得前缀长度LSp。当pq,求q的取值范围。j取最小值1时,q取值最小,如式(1 2)所示:qJLS-1 (1 2)q的取值在qm i n,p ,累计q1=p-qm i n+1个值。式(1 3)为各个q对应的j值范围,得到j的最大取值jM1。jq+1J -LS+1 (1 3)当pq,求q的取值范围。当j取最小值1时,q取值最大,如式(1 4)所示:qLS-i+1J -i (1 4)q的取值在p,qm a x ,累计q2=qm a x-p+1个值。式(1 5)为各个q对应的j值范围,得j的最大取值jM2。jLS-i+1J -i-q+1 (1 5)由剪枝流程可知,TS产生相似时空索引键的个 数C S I C(C a n d i d a t e S p a t i a l-t e m p o r a l I n d e x C o u n t)如式(1 6)所示:C S I CS=LSp(q1jM1+q2jM2)(1 6)从空间占用上看,基于O D序列的轨迹长度只有原始轨迹的1/2,同时缩短的前缀子串进一步减少了时空索引数量。索引大小由C S I CS变为原来的1/8,大量索引放入主存的难度降低。上一节得到基于O D的乘客轨迹O DT,以此为基础产生时空索引表。通过过滤规则得到相似对候选集。具体来讲,计算过程在S p a r k上的实现可分为以下步骤:(1)轨迹重排。s p a r k C o n t e x t读取轨迹O DT,按照O D在全局的出现频率对读取后生成的轨迹弹性分布式数据集O DT R D D(R e s i l i e n t D i s t r i b u-t e d D a t a s e t)逐 一 重 排 为O O DT R D D(O r d e r e d O D-b a s e d T r a j e c t o r y R D D),并持久化(c a c h e)以备后用。统计所有经过时间规整的各个O D的出现频率,将每个卡号的轨迹按此出现频率降序排列。虽然升序排列能减少剪枝产生的轨迹对数目,但分析结果表明,共有偏僻路线并不能很好地代表高相似,且产生的自索引大小在一个可以放入主存的合理范围内。(2)获取相似对。对O O DT R D D进行一系列剪枝操作,得到分布式的自时空倒排索引S S I I R D D和相似时空倒排索引C S I I R D D。然后将S S I I R D D通过c o l l e c t算子聚集到程序d r i v e r端并广播至各个工作结点。使分布式时空索引实现广播连接,连接操作产生的结果是一组满足阈值的候选轨迹相似对,并且保存在S P R D D(S i m i l a r P a i r s R D D)中。(3)验证高相似对。复用持久化的轨迹,将O O DT R D D c o l l e c t至d r i v e r端,广播至S P R D D的各分区所在结点完成连接操作,避免s h u f f l e开销。同时,前文的时间规整保证了若2个轨迹点具有相同的时间,那么他们的时间跨度不会超过某个阈值。这样使验证阶段的范围比较转为等值比较,减少了计算量。从时间消耗上看。S p a r k计算所消耗的时间通常由数据存储磁盘到计算引擎内存的I/O、结点内部的计算、结点间s h u f f l e操作的I/O和计算,以及其他时间开销组成。构建索引时,O O DT R D D只需要进行m a p操作即可产生所有轨迹对应的S S I I R D D和C S I I R D D。m a p操作属于结点内的计算,不涉及s h u f-f l e操作。时间开销只取决于该阶段最后一个任务完成计算的耗时,没有跨结点的网络传输所产生的额外时间开销。然而,获取和验证高相似对均会导致非常耗时的s h u f f l e操作。为了避免大量通信,将s h u f f l e连接转为广播连接,节约了时间成本。与此同时,O O DT R D D的持久化操作也避免了磁盘到内存的数据重复读写,从I/O上进一步减少了时间花销。5 实验与结果分析5.1 实验环境本文所有算法和数据处理流程均使用S c a l a语言实现,并在一个1 3个结点的S p a r k集群上完成测试。S p a r k集群包括1个M a s t e r结点和1 2个W o r k e r结点,与HD F S集群混合式部署。每组实验均执行3次,实验结果为3次实验结果的平均值。集群中每个结点软硬件配置完全一样。结点8831C o m p u t e r E n g i n e e r i n g&S c i e n c e 计算机工程与科学 2 0 2 3,4 5(8)F i g u r e 4 L o g i c e x e c u t i o n g r a p h o f S p a r k P P J o i n+a l g o r i t h m图4 S p a r k P P J o i n+算法的逻辑执行图硬件配置如下:(1)C P U:1 6-c o r e I n t e l(R)X e o n(R)S i l v e r 4 1 1 0 C P U 2.1 0 GH z;(2)内存:3 2 G B;(3)硬盘:2 T B。软件版本如下:(1)操作系统:C e n t O S 7.2;(2)H a d o o p:2.7.7;(3)S p a r k:2.4.0;(4)J a v a:1.8.0_1 9 1;(5)S c a l a:2.1 1.1 2。5.2 实验数据集深圳北斗应用技术研究院是深圳地铁集团大数据技术服务提供商。本文研究所涉及的大规模刷卡数据集大小为9 4.7 G B,时间范围为2 0 1 8年9月1日至2 0 1 8年1 0月3 1日,包含5 0 0余万张智能卡在2个月内的地铁刷卡交易记录,共计5.6亿条。记录内容包含进出站拍卡、消费和充值等,示例见表2。T a b l e 2 D e s c r i p t i o n o f m e t r o t r a j e c t o r y d a t a i n p o i n t s表2 以点为单位的地铁轨迹数据描述属性属性值描述i d7 2 8 3*深圳通卡号t i m e2 0 1 8-0 9-0 8 1 1:4 3:1 9检票时间s t a t i o n罗湖站检票站点t y p e地铁入站检票类型5.3 不同连接方法对比本文使用2 0 1 8年9月的A F C刷卡数据分别测试基于点和基于O D的2种不同轨迹相似性连接方法。图5描述了不同连接方法的轨迹对数量,横坐标为不同的相似度阈值,纵坐标为候选轨迹对数量和达到相似度的轨迹对数量。候选集大小随着阈值的增加而减少。从图5可知,基于O D的轨迹连接方法过滤效果更好,与基于点的过滤方法相比,候选集最多减少为原来的0.1 5,平均减少了7 4%。F i g u r e 5 N u m b e r o f t r a j e c t o r y p a i r s o f d i f f e r e n t T S-J o i n m e t h o d s图5 不同轨迹连接方法的轨迹对数量图6描述了同一集群环境,不同轨迹相似性连接方法的运行时间。可以看到,阈值改变时,基于O D的轨迹相似性连接方法的执行时间均低于基于点的连接方法的。当相似度阈值取0.8 5时,执行时间差最大,基于O D的轨迹相似性连接方法的比基于点的连接方法的减少了6 2.5%。随着相似度阈值的增大,2种方法的执行时间均有缩短,方法间的执行时间差异逐渐减小。F i g u r e 6 R u n t i m e c o m p a r i s o n o f d i f f e r e n t T S-J o i n m e t h o d s图6 不同轨迹相似性连接方法运行时间对比基于点序列的轨迹相似性强调不同乘客共同出现在不同站点的频次,关注点不在乘客行程。基于O D序列的相似性强调乘客有相同的行程,有相同的起点和终点。前者可以用于基于位置的服务L B S(L o c a t i o n-B a s e d S e r v i c e s)相关的应