邓 涛,陈红梅,王丽珍
（云南大学信息学院，昆明，650504）
随着移动互联网、全球定位等技术的蓬勃发展，百度地图、美团、滴滴等各类基于位置的服务应用不断涌现，用户可以通过位置及文本信息来获得各式各样便利的服务.在这些服务背后，往往都有一套有效的技术来支撑其服务质量，因此诸如空间关键字查询（Spatial⁃Keyword Query，SKQ）、空间轨迹分析、POI推荐这些基于空间数据的技术引起了大量研究兴趣［1-12］，其中SKQ［1-4］被广泛研究.在一般情况下，SKQ根据用户给出的一组查询关键字和空间约束，返回一组与查询关键字相关且满足空间约束的空间对象（一个空间对象通常由两部分组成：一个地理位置和一组描述关键字）.为了更好地捕获用户需求，Fang et al［13］提出一种新颖的SKQ：空间模式匹配（Spatial Pattern Matching，SPM）.
SPM允许用户通过空间模式表达查询需求.一个空间模式P是一个图G()V，E，其中，每个顶点vi是一个查询关键字wi（如学校，超市等），每条边ek=(vi，vj)表达两个顶点vi和vj之间的空间约束（如1 km以内）.SPM从空间对象集中查询满足空间模式P的所有匹配实例.一个匹配实例M是一个空间对象子集，其中的空间对象包含P中顶点的查询关键字，空间对象之间满足P中边的空间约束.
例如，用户A每天送孩子上学后再搭乘公交车上班，下班后再接孩子回家.他想要购买一套满足如下要求的住宅：（1）住宅与学校、车站邻近，但考虑到噪音问题，车站、学校至少应该与住宅距离500 m；
（2）车站去往学校的途中应该有超市，即车站与学校同时与超市邻近，以便下班接孩子的同时能够顺路到超市购物.针对这种复杂的用户需求，传统SKQ无法直接表达并解决.而SPM可以采用空间模式表达用户需求，并通过空间模式匹配查询满足空间模式的空间对象子集.
然而，SPM是一个NP难问题［13］.为了提高空间模式匹配效率，基于IR⁃tree索引结构和多路连接操作，Fang et al［13］提出有效的空间模式匹配算法MPJ（Multi⁃Pair⁃Join）及其改进算法MSJ（Multi⁃Star⁃Join），并证实这两个算法的匹配效率比基于传统GPM（Graph Pattern Matching）的算法［14-15］有显著提升.但是，面对空间大数据，MPJ与MSJ算法的匹配效率依然较低，所以有必要改变计算框架，设计更高效的空间模式匹配算法.随着大数据技术的不断发展，各类可以支持海量数据计算的并行计算框架（如Spark，hadoop，storm）日渐成熟，为设计高效的空间模式匹配算法提供了另一种研究思路.
针对现有空间模式匹配算法处理空间大数据时的低效率问题，本文基于并行计算框架Spark，研究SPM的并行解决方案，设计高效的空间模式匹配并行算法.具体地，本文首先分析MSJ算法在处理空间大数据时低效的原因，并在此基础上提出最小边界矩形匹配（r⁃match）及其匹配方法.针对IR⁃tree叶结点占比大这一问题，提出r⁃match剪枝策略，有效避免了不必要的叶结点匹配.基于以上内容，本文设计了基于空间模式中边并行的空间模式匹配算法PMSJ（Parallel Multi Star Join）.实验结果表明，PMSJ算法可以有效提升空间模式匹配效率.
目前SKQ主要可分为三种类型.
第一种类型是检索一组对象，使每个对象在空间和文本邻近方面都与查询高度相关.具体地，这类SKQ包括top⁃k布尔查询、top⁃k排名查询和范围查询［1，16-18］.为了方便这些查询，研究者们提出各种结合空间和文本信息的索引技术，它们可以粗略地分为关键字优先索引和空间优先索引.关键字优先索引包括反向R树（Inverted R⁃tree）［19］和反向线性四叉树（IL⁃Quadtree）［20］；
空间优先索引包括信息检索R树（IR2⁃tree）［21］和关键字R树（KR*⁃tree）［22］等.通常，关键字优先索引更适合于关键字较少的查询，而空间优先索引更适用于关键字较多的查询.
第二种类型是查询一组对象，它们不仅在空间上邻近还共同包含所有查询关键字.这类SKQ包括空间组关键字查询［23］和最接近关键字查询［24］.
第三种类型是基于模式的空间关键字查询，即SPM.SPM采用空间模式表达用户查询需求，并返回匹配空间模式的所有对象子集.SPM问题是NP难问题，传统SKQ算法不能有效地解决［13］.为了提升匹配效率，基于IR⁃tree索引结构和多路连接操作，Fang et al［13］提出两个有效算法MPJ与MSJ.MSJ通过精简空间模式，启发式地确定边连接序及精简边匹配，进一步提升了匹配效率.然而，面对空间大数据，MPJ与MSJ的匹配效率依然较低.与上述工作不同，本文基于并行计算框架Spark，研究SPM的并行解决方案，设计高效的空间模式匹配并行算法.
2.1 问题定义设D为空间对象集，每个空间对象oi∈D包含空间坐标(xi，yj)与一组关键字doc(oi)，图1展示了一个空间对象集.
图1 空间对象集Fig.1 Spatial object set
定义1空间模式（Spatial Pattern）空间模式P是一个简单图P=G(V，E)，如图2所示，它遵守以下约束：
（1）每个顶点vi∈V都有一个关键字wi.如果wi∈doc(os)，则对象os与顶点vi匹配.
（2）每条边(vi，vj)∈E都有一个距离区间[li，j，ui，j]，它规定了匹配顶点的两个对象的距离上界与下界.
（3）每条边(vi，vj)∈E由如下四个符号之一描述.设边(vi，vj)的一对匹配对象是os和ot，即wi∈doc(os)，wj∈doc(ot)，|os-ot|∈[li，j，ui，j]，则四个符号的意义是：
图2 空间模式Fig.2 A spatial pattern
①vi→vj（vi排斥vj）：D中不存在与os的距离小于li，j且包含wi的对象.
②vi←vj（vj排斥vi）：D中不存在与ot的距离小于li，j且包含wj的对象.
③vi↔vj（vi与vj相互排斥）：vi→vj并且vi←vj.
④vi-vj（vi与vj相互包容）：D中允许存在与os的距离小于li，j且包含wj的对象，与ot的距离小于li，j且包含wi的对象.
定义2边匹配（e-match）对于边(vi，vj)，如果两个对象os和ot匹配两个顶点vi和vj，且同时满足边(vi，vj)的空间约束，即距离区间约束[li，j，ui，j]和符号约束（→，←，↔或—），则称空间对象os和ot是边(vi，vj)的一个匹配，记为e⁃match.
定义3模式匹配（match）给定一个空间模式P=G(V，E)和一个空间对象子集M⊆D，如果存在一个满射∅：V→M，使得每条边(vi，vj)∈E，对象对(∅(vi)，∅(vj))是(vi，vj)的一个e⁃match，则称空间对象子集M是模式P的一个匹配，记为match.
问 题给定空间对象集D和一个空间模式P，SPM在D中查找P的所有模式匹配.
如图3所示，四个由虚线连接的对象构成了图2所示的空间模式在图1所示空间对象集上的一个模式匹配.四个对象均包含空间模式中所对应的关键字且满足距离与符号约束.其中边house，station被“→”符号连接，因此在图3中不存在任何一个对象包含关键词station且与o1的距离小于0.5 km.
图3 SPM查询示例Fig.3 An example of SPM query
2.2 IR-tree为提升SKQ效率，Zhou et al［19］提出IR⁃tree索引结构.基于IR⁃tree，Fang et al［13］提出SPM的两个有效算法MPJ和MSJ.本文的算法PMSJ中也采用IR⁃tree计算边匹配.IR⁃tree有如下特点：（1）空间对象都保存在叶结点中；
（2）内部结点由子结点最小边界矩形组成；
（3）每个结点都包含一张反向表，其中存储了结点中的每个关键字及包含该关键字的子结点最小边界矩形.图4a展示了一棵扇出大小为2的IR⁃tree的空间对象分区.图4b展示了根据图4a构造的IR⁃tree的结构，图中虚线框即为结点的反向表.
图4 IR-tree空间对象分区（a）与结构（b）Fig.4 IR-tree spatial object partition（a）and structure（b）
2.3 MapReduce为了提升面对空间大数据时SPM的匹配效率，本文基于并行计算框架Spark，设计高效的空间模式匹配并行算法，其核心是分布式并行计算模型MapReduce.
MapReduce是由Google公司研究提出的一种面向大规模数据处理的并行计算模型［25］，该模型的核心是Map函数和Reduce函数，由开发者负责实现.相应地，MapReduce模型的一次操作也主要分为两个阶段.第一阶段，Map函数接收一组键值对并产生一组key，value.然后通过Shuffle过程，根据键和归并值将无序的key，value转为有序的key，value-list，传递给Reduce函数.第二阶段，Reduce函数接收一组key，value-list并输出一组新的键值对作为这次操作的结果.
首先分析经典空间模式匹配算法MSJ的执行效率，然后基于并行计算框架Spark，提出高效的空间模式匹配并行算法PMSJ.
3.1 经典算法MSJ的执行效率分析MSJ主要包括如下基本步骤：（1）初始化：根据空间模式P构造有界模式，通过有界模式来找出错误模式，排除多余边以及收紧边的上下界；
（2）计算e⁃match：找出所有边在IR⁃tree的最底层内部结点上的匹配对，根据各边匹配对的数量计算所有边的连接顺序，再计算除相互包容边之外所有边的e⁃match；
（3）剪枝：根据星型和锚点剪枝原则，剪去不足以形成空间模式匹配的空间对象；
（4）连接：根据连接顺序生成空间模式的所有匹配.上述步骤中，步骤（2）是影响算法效率的关键步骤.
步骤（2）通过在IR⁃tree上搜索生成e⁃match.IR⁃tree是一棵平衡树，M表示结点的最大容量，即扇出.m为结点的最小容量，且m≤设|D|=N，那么IR⁃tree的树高h满足不等式|logM N-1| ≤h≤|logm N-1|.IR⁃tree在第k层的结点数nk满足不等式mk-1≤nk≤Mk-1.随着层数k的增大，层中包含的结点数nk呈指数级上升，需要纳入计算e⁃match的结点数量同样呈指数级上升.此外，步骤（2）返回的e⁃match数量越多，步骤（3）和步骤（4）需要进行剪枝及连接的e⁃match也越多.
表1给出了在一棵扇出为100的IR⁃tree上查询五个不同的空间模式时MSJ算法各个步骤所花费的时间.
可以看出，计算e⁃match所占时间显著高于其他步骤，将这一步骤并行化是一个有效提升SPM匹配效率的方法.基于IR⁃tree的性质，Cao et al［17］给出这样一个事实：在一棵IR⁃tree的所有结点中叶结点占比高达99%以上，并且空间对象全部存储在叶结点.所以，当计算e⁃match至叶结点层时，需要对大量空间对象进行计算，如果在叶结点层计算e⁃match前对上层结点匹配对进行剪枝，一定会提升匹配效率.
表1 MSJ算法各个步骤的时间花费（单位：ms）Table 1 Time-consuming of each step of MSJ algorithm（unit：ms）
3.2 并行算法PMSJ从3.1节可知，计算各边e⁃match是MSJ中最耗时的步骤，所以e⁃match查询的并行化是PMSJ的核心步骤.
PMSJ算法可以概括为如图5所示的六个步骤：（1）对空间模式进行精简排错；
（2）自上而下逐层计算各边的r⁃match直到最后一层内部结点为止，此步骤中各边的r⁃match计算并行执行；
（3）对r⁃match进行剪枝；
（4）根据各边r⁃match的数量计算边的连接顺序；
（5）根据各边的r⁃match计算其e⁃match，此步骤同样并行执行；
（6）根据步骤（3）计算的连接顺序，连接步骤（5）得到的e⁃match，生成模式匹配.下面详述PMSJ的核心步骤：并行r⁃match计算、r⁃match剪枝、并行e⁃match计算.
图5 PMSJ流程Fig.5 The procedure of PMSJ
3.3 并行r-match计算首先给出IR⁃tree中r⁃match的正式定义.因为vi←vj与vi→vj是类似的，而vi↔vj可以被转换为vi→vj与vj→vi，所以在此只须考虑vi-vj与vi→vj两种边.
定义4最小边界矩形匹配（r-match）设ni和nj为IR⁃tree上位于同一层的两个内部结点，ri与rj分别表示ni与nj的最小边界矩形（Mini⁃mum Bounding Ractangles，MBRs），inv(ni)，inv(nj)分别表示ni与nj的反向表.当ni与nj满足如下条件时，(ni，nj)是空间模式P中边(vi，vj)的一对r⁃match：（1）ni，nj分别与vi，vj匹配，即wi∈inv(ni)，wj∈inv(nj)；
（2）vi-vj时，dmin(ri，rj)≤ui，j且dmax(ri，rj)≥li，j，dmin(ri，rj)和dmax(ri，rj)分别表示ri与rj的最小距离和最大距离；
（3）vi→vj时，在满足（2）的前提下，IR⁃tree同一层中不存在结点nk(k≠j)满足dmax(ri，rj)＜li，j.
综上，引理1成立.
根据引理1，对于空间模式的一条边，构成第k层r⁃match的一对结点ni，nj的父结点同样是第k-1层的一对r⁃match，因此，只需在k-1层的r⁃match中进行计算便可得出第k层的r⁃match.同时，一条边的r⁃match查询可视作一个单独的子问题.综上，r⁃match计算满足并行化前提条件.第一个MapReduce任务Job1由如下步骤组成：（1）将模式P的各边分发至集群中的Mapper；
（2）Mapper将IR⁃tree的根作为初始的r⁃match，逐层计算所分配边的r⁃match；
（3）Reducer将所有Mapper产生的r⁃match汇总进行下一步处理.
3.4 r-match剪枝所有边的r⁃match汇总后，可以根据边的连接约束，进行r⁃match剪枝，下面举例说明剪枝的必要性并给出剪枝策略.
设空间模式P的两条相邻边如图6所示，边school⁃station、station⁃home的r⁃match数量分别为三对和两对.如要连接边school⁃station与station⁃home，则顶点station对应的结点应该同时出现在school⁃station和station⁃home的r⁃match中.因为n3没有出现在边station⁃home的r⁃match中，则边school⁃station的r⁃match(n1，n3)可以剪枝.
图6 r-match剪枝示例Fig.6 An example of r-match pruning
综上所述，r⁃match剪枝策略如下：设ci为ni在vi的邻接边(vi，vj)的r⁃match集中出现的邻接边数.当ci小于vi的邻接边时，所有包含ni的r⁃match被剪枝.图6中，顶点station的结点n3仅在邻接边school⁃station的r⁃match中出现，则c3值为1，而顶点station的邻接边数为2.所以，包含n3的r⁃match被剪枝.
3.5 并行e-match计算当r⁃match计算进行至IR⁃tree最后一层非叶结点时，任意一对r⁃match(ni，nj)的子结点不再是MBRs而是具体的空间对象，因此下一次计算将直接得到e⁃match.与r⁃match类似，一条边的e⁃match同样可以根据上一层的r⁃match计算，而且一条边的e⁃match计算也可以视为单独的子问题，满足并行化的前提条件.为了计算边的e⁃match，第二个MapReduce任务Job2由如下步骤组成：（1）将模式P的各边以及对应的r⁃match集分发至集群中的Mapper；
（2）Mapper根据分配到的边及其r⁃match集计算边的e⁃match；
（3）Reducer将所有Mapper产生的e⁃match汇总进行下一步处理.
实验目的是评估本文提出的PMSJ的效率，并与经典算法MPJ，MSJ进行对比分析.
4.1 实验设置实验环境：AMD R7⁃2700x CPU，48 GB内存的PC机.在PC机上搭建了一个由四台虚拟机组成的Spark分布式集群，包含一个master节点、三个worker节点以及Hadoop hdfs文件系统，其中master节点内存为20 GB、worker节点内存为8 GB.PMSJ算法运行于Spark集群.MPJ，MSJ算法采用Fang et al［13］提供的程序，运行于master节点.
数据集：采用Fang et al［13］提供的四个真实空间数据集，表2给出了这些数据集的统计信息，这些数据集的IR⁃tree扇出为100.
表2 空间数据集信息Table 2 Information of spatial datasets
空间模式：采用Fang et al［13］的方法生成空间模式.即对每个数据集，采用图7所示的12个模式结构，为每个模式结构生成20个空间模式，共计240个空间模式.
图7 空间模式结构Fig.7 Structures of spatial patterns
4.2 模式顶点数的影响为了评估空间模式中顶点个数对算法效率的影响，首先将每个数据集对应的240个模式根据顶点个数分为五组，然后计算各组模式的平均匹配时间，结果如图8所示.由图可知，顶点数量较少时，MPJ，MSJ与PMSJ运行时间的差距不大；
当顶点数量增加时，MPJ，MSJ的运行时间显著增加，而PMSJ的运行时间增长平缓.在模式中，顶点数与边数是正相关的，MPJ，MSJ需要依次计算各边的e⁃match，因此边数直接影响运行时间；
而在PMSJ中，这一过程是并行执行的，运行时间不会显著增加.
图8 空间模式中顶点数对算法效率的影响Fig.8 The effect of vertex number on the efficiency of algorithms
4.3 模式边符号约束的影响为了评估空间模式中边符号约束对算法效率的影响，引入参数η∈{0.6，0.7，0.8，0.9，1} .vi→vj，vi←vj，vi↔vj与vi-vj四种符号出现的概率为η(1-η)，(1-η)η，(1-η)2以及η2［13］.为每个数据集生成五个不同参数的模式集.实验结果如图9所示，由图可知，随着η的增大，三个算法的运行时间均逐渐降低.因为η越大，模式集中带有相互包容符号“—”的边越多，这些边在计算e⁃match时可能被跳过，所以MPJ，MSJ和PMSJ的运行时间都缩短了.但在所有数据集上，PMSJ的执行效率都显著高于MPJ与MSJ.
4.4 模式距离区间的影响为了评估空间模式中边距离区间对算法效率的影响，引入参数γ∈{0.2，0.6，1，1.5，2} 以调整边的距离区间.在生成新模式集时，对原模式集中各边的距离区间[li，j，ui，j]，保持li，j不变，ui，j变为li，j+(ui，j-li，j)×γ.为每个数据集生成五个不同参数的模式集，实验结果如图10所示.由图可知，随着γ的增大，MPJ，MSJ和PMSJ的运行时间均增大，这是因为边距离区间增大时，MPJ，MSJ与PMSJ在进行r⁃match和e⁃match查询时将考虑更多的结点.也可以看到，在所有数据集上，PMSJ的执行效率都显著高于MPJ与MSJ.
图9 空间模式中边符号约束对算法效率的影响Fig.9 The effect of sign on the efficiency of algorithms
图10 空间模式中边距离区间对算法效率的影响Fig.10 The effect of distance interval on the efficiency of algorithms
4.5 伸缩性为了评估PMSJ的伸缩性，从原始数据集中按20%，40%，60%和80%的比例随机抽取对象生成四个子集，模式数据集不变.子集可能不包含某些模式顶点的关键字，这些模式不会产生匹配，因此在计算平均运行时间时这些模式将不被考虑.实验结果如图11所示.由图可知，MPJ与MSJ在数据集扩大时运行时间显著增加，PMSJ的运行时间则保持平缓上升.因此，PMSJ的伸缩性更好.
图11 伸缩性Fig.11 Scalability
为了提升面向大数据时空间模式匹配算法的效率，本文提出基于并行计算框架Spark的空间模式匹配算法PMSJ.其中空间模式每条边的匹配都被视为一个子问题而并行执行.在四个真实数据集的实验证明该算法的效率相比传统算法MPJ，MSJ有显著的提升.目前PMSJ是从空间模式的角度来设计并行算法，未来可以考虑如何针对索引结构来设计并行算法.
猜你喜欢模式匹配关键字剪枝人到晚年宜“剪枝”保健医苑(2022年5期)2022-06-10履职尽责求实效 真抓实干勇作为——十个关键字，盘点江苏统战的2021华人时刊(2022年1期)2022-04-26基于YOLOv4-Tiny模型剪枝算法成都信息工程大学学报(2021年6期)2021-02-12基于模式匹配的计算机网络入侵防御系统电子制作(2019年13期)2020-01-14成功避开“关键字”动漫界·幼教365(大班)(2019年10期)2019-10-28具有间隙约束的模式匹配的研究进展移动信息(2018年1期)2018-12-28OIP-IOS运作与定价模式匹配的因素、机理、机制问题中央民族大学学报（自然科学版）(2018年3期)2018-11-09剪枝天津诗人(2017年2期)2017-03-16基于散列函数的模式匹配算法山东工业技术(2015年21期)2015-07-27一种面向不平衡数据分类的组合剪枝方法计算机工程(2014年6期)2014-02-28
