0 引言

随着基于位置服务应用的不断推广, 这些应用也同时产生了海量的空间文本数据.通常来讲, 每条空间文本数据包括一条空间坐标信息和一个文本标签集合.例如, 餐馆的经纬度和餐馆的特色标签集合; 用户的当前位置和用户兴趣标签集合等.基于这些数据, 用户可以通过空间和文本两个维度的过滤找到感兴趣的空间文本对象.本文主要研究了以下2种空间文本查询. ①布尔范围查询^[1], 该查询用于找到附近以$\epsilon$为半径的圆形范围内包含给定关键字集合的空间文本对象.例如, 用户可以搜索附近1 km内包含咖啡、奶茶等标签的餐馆. ②空间文本相似连接^[2], 该查询对数据集的每个空间文本对象, 在与其连接的数据集中找到满足与该对象空间距离小于等于$\epsilon$且文本标签集合Jaccard相似度^[2]大于等于$\theta$的相似对象.例如, 社交应用中需要为每个用户推荐附近100 m内与该用户有相似兴趣的潜在好友.可以发现, 上述查询分析在现实生活当中有着重要的应用价值.然而, 随着数据量的不断增长, 如何在海量的数据场景下高效地进行上述查询分析是十分具有挑战性的.首先在单机环境下, 由于内存大小的限制, 数据量的迅速递增导致了更多的磁盘读写操作, 进一步导致了较高的处理延时; 另外, 随着数据量的迅速递增, 单机环境每分钟能够处理的请求数(吞吐量)也在不断下降.

近年来, 随着基于内存的分布式计算平台Spark^[3]的流行, 有许多研究工作^[4-7]基于该平台探索了海量数据场景下的分布式解决方案.相对于基于Hadoop的解决方案, 基于Spark平台的解决方案可以达到更低的延时和更高的吞吐量.例如, 最近有文献提出了基于分布式内存计算的空间数据分析系统^[4].该系统相比于传统的数据库管理系统和基于Hadoop的分析系统(如Hadoop GIS^[8]), 在空间数据的查询性能方面提高了5~100倍^[4].考虑到上述优越的特性, 本文采用Spark作为实现平台, 并在该平台下研究如何对上述的2种空间文本查询进行高效处理.同时, 由于许多分析人员倾向于通过SQL语言去进行数据分析工作, 文章为上述查询提供了便捷的SQL接口.

另一方面, 在查询分析系统中, 索引技术有着重要的意义.普通用户的查询解集合通常只涵盖了查询数据集的一小部分, 在这样的场景下, 索引可以通过较好的剪枝能力加速查询, 从而提升整体性能.由于Spark是基于Master-Slave架构的分布式平台, 如何基于此设计面向空间文本数据的两层索引技术是一个待深入探索的问题.其中, 全局索引需要过滤掉不可能满足给定查询的数据分区; 然而由于全局索引存储于Master节点, 受限于单台节点的内存限制, 需要探索有较好空间扩展性的全局索引方法才能应对海量数据场景的挑战.除此之外, 局部索引对给定查询进行处理后, 通常将结果收集到Master节点; 由于传统的空间文本索引技术没有充分利用低频词汇的剪枝作用, 且空间开销较大, 因此, 需要设计高效的局部索引方案进行进一步的优化处理.

概括来说, 本文的主要贡献如下.

$\bullet$基于Spark平台实现了面向海量空间文本数据的两层索引框架, 该框架通过分阶段过滤的策略较大地提升了性能.

$\bullet$针对空间文本相似连接问题, 结合前缀过滤技术提出了Prefix-RI结构.

$\bullet$基于Spark平台, 提出了针对上述查询的分布式处理算法, 并与其他解决方案进行了充分的实验对比.

接下来, 本文将在第1节介绍问题定义、相关背景知识及先前的工作; 第2节介绍解决方案的整体框架; 第3节和第4节分别对局部索引和全局索引技术进行介绍; 第5节主要介绍提出的分布式处理算法; 第6节介绍实验结果和分析, 最后在第7节对全文进行总结.

1 问题定义及相关工作 1.1 问题定义

假定$\mathcal{D}$为一个空间文本数据集, $\mathcal{D}$中每个空间文本对象$o_i$可由一个欧氏空间的二维点坐标$\rho_i=(x_i, y_i)$和字符串集合$\gamma_i$组成; 其中, $\gamma_i$的字符串个数为$|\gamma_i|$.因此, 一个包含了$n$个空间文本对象的数据集$\mathcal{D}$可以表示为: $\{(\rho_1, \gamma_1), \cdots, (\rho_n, \gamma_n)\}$.

一个空间文本查询$Q$通常包括一个空间查询$Q_s$和一个文本查询$Q_t$.对于空间查询$Q_s$, 文章主要关注常用的圆形范围查询.圆形范围查询可由$(\tau, \epsilon)$定义, 其中$\tau$为查询圆中心, $\epsilon$为查询半径.对于文本查询, 在布尔范围查询中, 文本查询$Q_t$可以由一个目标字符串集指定, 表示必须包含目标字符串集合中的所有字符串才符合文本查询条件; 在空间文本相似连接中, 其定义为两个空间文本对象的字符串集合$\gamma_j$和$ \gamma_k$的Jaccard相似度.如果$\gamma_j$和$ \gamma_k$的Jaccard相似度大于等于给定的阈值, 则满足文本查询条件.下面给出具体的定义.

定义1.1  假设$dist(\rho, \tau)$为点$\rho$和$\tau$的欧氏空间距离, 则布尔范围查询$Q=\{Q_s=(\tau, \epsilon), Q_t\}$将在数据集$\mathcal{D}$中找出满足查询的子集$\theta$, 使得

$ \begin{align*} \theta=\{o_i \in \mathcal{D} \ | \ dist(\rho_i, \tau) \leq \epsilon \wedge Q_t \subseteq \gamma_i\}. \end{align*} $

定义1.2  两个空间文本对象$o_j$和$o_k$的文本相似度为其字符串集合$\gamma_j$和$\gamma_k$的Jaccard相似度, 其为

$ sim_t(o_j, o_k)=\frac{|\gamma_j \cap \gamma_k|}{|\gamma_j \cup \gamma_k|}. $

其中, $|\gamma_j \cap \gamma_k|$表示两个字符串集合相同的个数, 且$|\gamma_j \cup \gamma_k|=|\gamma_j|+|\gamma_k|- |\gamma_j \cap \gamma_k|$.易知$0 \leq sim_t(o_j, o_k) \leq 1$ :当$\gamma_j$和$\gamma_k$没有相同字符串时, $sim_t(o_j, o_k)$为0;当$\gamma_j$和$\gamma_k$相同时, $sim_t(o_j, o_k)$为1.

定义1.3  给定空间文本数据集$\mathcal{D}_1$和$\mathcal{D}_2$, 假定空间距离阈值为$\epsilon$且文本相似度阈值为$\lambda$ ($0 \leq \lambda \leq 1$), 空间文本相似连接将找出

$ \begin{align*} \theta=\{o_i \in \mathcal{D}_1, o_j \in \mathcal{D}_2 \ | \ dist(\rho_i, \rho_j) \leq \epsilon \wedge sim_t(o_i, o_j) \geq \lambda \}. \end{align*} $

1.2 相关工作

空间文本查询.空间文本查询(如上述的布尔范围查询)近年来已经被广泛研究^[9-11]. Zhou等^[12]将文本搜索的研究扩展到空间数据库, 他们提出了两个混合的空间文本索引, 其将R^*-tree^[13]和倒排列表松散地组合, 并进一步提出了Inverted file-R^*-tree结构和R^*-tree-Inverted File结构. Chen等^[1]提出了紧密结合空间索引和倒排文件的IR-tree结构.他们使用了一个R-Tree^[14], 并将倒排列表集成到R-tree的每个节点, 对相应子树的文本内容进行索引.除了布尔范围查询外, 也有很多工作致力于研究结合了空间相似度和文本相似度的top-$k$问题. Wu等^[15]提出了一种基于密度的方法来找出$k$个最相似的区域; Choudhury等^[16]进一步研究了如何对多个top-$k$查询组成的批查询进行优化.上述工作都是基于欧氏空间下的研究, 而Luo等^[17]进一步研究了路网下的空间文本查询.另外, Chen等^[18]还研究了流数据场景下的空间文本查询处理.

空间文本相似连接.相似连接在许多领域有着广泛的应用^[19-20], 文本相似连接和空间相似连接都是研究热点.文本相似连接寻找两个文本数据集中所有满足相似度大于等于给定阈值的解对, 常用的相似度量函数包括Jaccard相似度, Cosine相似度等; Sarawagi等^[21]首次提出基于倒排列表支持文本相似连接, 对于每个文本对象, 将其包含的字符串映射到该对象; 在构建完该列表后, 通过扫描当前对象包含的各个字符串所映射的列表, 并累计与自身的重复元素个数来计算相似性.为了进一步减少需要扫描的字符串个数, 文献[22]进一步提出了前缀过滤技术. Bayardo等^[23]进一步提出了支持Jaccard相似度和Cosine相似度的前缀过滤技术.在空间相似连接方面, 由于R-Tree索引技术在该领域的广泛应用, 常见的连接算法通常基于R-Tree实现.在文献[4]中, 作者基于Spark平台和R-Tree索引对基于距离的空间相似连接和$k$最近邻空间相似连接进行了分布式的高效支持.

分布式分析系统.由于数据规模的不断增长, 分布式的计算框架现在越来越受欢迎. Apache Spark^[3]是一个基于内存计算的分布式计算框架.自发布以来, 在机器学习、图处理和流数据处理方面起着重要作用.与面向磁盘和批量处理的Hadoop平台相比, Spark可以使用分布式内存缓存和计算提供低查询延迟和高吞吐量的服务. Xie等^[4]基于Spark提出了基于分布式内存计算的空间数据分析系统.该系统实现了一系列面向海量空间数据的查询操作(圆形范围查询、$k$最近邻查询及空间相似连接等).与其他空间数据分析系统如Spatial Hadoop^[5]相比, 在真实数据集下的实验证明了其性能优越于其他的主流空间数据分布式分析系统.

1.3 背景知识

前缀及长度过滤技术^[22].给定字符串集合$\gamma$和Jaccard相似度阈值$\lambda$, 可以为其生成长度为$|\gamma|-\lceil \lambda \times |\gamma| \rceil+1$的前缀.对于两个字符串集合$\gamma_j$和$\gamma_k$, 如果其Jaccard相似度大于等于$\lambda$, 则在统一的字符串排序下, $\gamma_j$和$\gamma_k$的前缀应该至少有一个字符串是相同的.基于此, 可以大大减小搜索的字符串个数.此外, 还可以通过长度过滤技术进行预过滤.对于$\gamma_j$和$\gamma_k$, 如果这两者的Jaccard相似度大于等于$\lambda$, 则有$\frac{|\gamma_j \cap \gamma_k|}{ |\gamma_j \cup \gamma_k| } \geq \lambda$, 既$|\gamma_j \cap \gamma_k| \geq \lambda \times |\gamma_j \cup \gamma_k| $.根据集合的性质, 易知$|\gamma_j| \geq |\gamma_j \cap \gamma_k|$且$|\gamma_j \cup \gamma_k| \geq |\gamma_k|$, 所以进一步得到

$ \begin{align*} |\gamma_j| \geq |\gamma_j \cap \gamma_k| \geq \lambda \times |\gamma_j \cup \gamma_k| \geq \lambda \times |\gamma_k|, \end{align*} $

同理可证$|\gamma_k| \geq \lambda \times |\gamma_j|$.因此, 可以对$|\gamma_j|$和$|\gamma_k|$的大小关系进行验证, 从而初步排除不满足相似性要求的解.

布隆过滤器技术^[24].一个布隆过滤器由$n$个二进制位($\{\mathcal{B}[1], \cdots, \mathcal{B}[n]\}$)组成, 这些二进制位最开始全部初始化为0.通常来讲, 布隆过滤器使用一组独立的$k$个哈希函数$\{h_1, \cdots, h_{k}\}$.对于需要索引的每个元素, 首先, 通过各个哈希函数将该元素映射到$[1, n]$区间内的一个数; 然后, 置对应的二进制位为1.为了检查一个给定元素是否存在, 可以通过检查哈希函数组对该元素哈希后的各个对应二进制位是否值为1.如果全为1, 则该元素有很大概率存在于布隆过滤器中, 否则一定不存在.假定索引的数据集包含$m$个元素, 则布隆过滤器误报(false-positive)的概率为

$ \begin{align*} Pr_{\rm false-positive}=\Big(1-\Big(1-\frac{1}{n}\Big)^{mk} \Big)\approx(1-{\rm {e}}^{\frac{-km}{n}}). \end{align*} $

2 整体框架 2.1 查询接口

通过扩展Spark SQL提供的接口, 本文为2种空间文本查询提供了便捷的SQL接口.例如, 给定一个布尔范围查询, 想找到离点$(20, 2)$距离在3 km内且包含字符串"咖啡"的空间文本对象, 那么对应的SQL示例如下所示,

SELECT * FROM t WHERE POINT(t.x, t.y) IN CIRCLERANGE(POINT(20, 2), 3) AND CONTAINS(t.s, "咖啡").

2.2 框架细节

结合Spark平台Master-Slave结构的特点, 本文采用了面向空间文本查询的两层索引框架(见图 1)^{[4, 25]}.该框架利用了分阶段过滤的策略.首先, 通过全局索引过滤掉大部分不可能包含查询解集的分区; 然后, 进一步利用局部索引技术在每个候选分区上进行进一步的加速从而达到性能提升.下面对分布式索引的3个构建过程进行详细阐述:

数据分区.分区阶段将数据拆分并映射到集群的各个节点.一般来说, 分区策略主要关注以下3个问题. ①数据局部性, 在空间上相近的数据或者文本相似度较高的数据对象应分配给同一分区; ②负载均衡, 所有分区的大小应大致相同; ③可扩展性, 分区的时间成本应该是可以接受的.在本文的问题背景下, 通过空间相似性或文本聚类分区是直观的策略.然而, 与通过空间相似性分区相比, 基于文本聚类的分区太过耗时.在实验中, 发现通过空间相似度分区的平均耗时仅为34 s, 而基于文本聚类分区的平均耗时为数个小时; 显然, 前者具有更好的可扩展性.因此, 选择了基于空间的分区策略, 称为STRPartitioner^[4-5]. STRPartitioner实现了Sort-tile-recursive算法^[26]的第一次迭代, 以确定分区边界, 即最小边界矩形(MBR).基于这些MBRs, 可以进一步构建一个临时的R-tree来将每个对象映射到特定的分区.给定分区数目后, Sort-tile-recursive算法会根据数据的空间相似性进行分区(数据局部性); 且通常来讲, 分区后的各个分区大小基本相近(负载均衡).因此, STRPartitioner很好地解决了上述3个问题.

局部索引构建.对于每个分区, 可以构建局部索引对查询进行加速.此外, 需要收集每个分区的空间边界信息(每个分区的MBR)和文本统计信息, 以进一步构建全局索引.它们是(id, MBR, $\beta$)的形式, 其中id标识分区, $\beta$表示每个分区的文本摘要数据用以在全局索引上引入文本的剪枝作用.

全局索引构建.使用在局部索引构建中收集的统计信息, 可以在主节点中进一步构建全局索引.

3 局部索引构建

为了更高效地支持各个分区的查询加速, 本文采用了RI$^+$索引结构^[25].下面, 首先介绍对于空间文本查询问题的两个重要观察, 然后进一步介绍RI(Refined Index)^[25]结构.最后, 将结合低频词汇的剪枝作用对RI$^+$索引的细节进行介绍.

3.1 RI结构

IR-Tree^[1]结构是处理布尔范围查询的经典结构. IR-Tree结构基于R-Tree进行扩展, 在R-Tree的每一层嵌入了倒排列表以对子节点的文本数据进行索引.这样, 在非叶子节点搜索时, 通过匹配当前的查询字符串在倒排列表中的映射节点可以快速找到满足文本过滤条件的子节点, 在空间过滤的同时结合了文本的剪枝作用, 极大地减小了搜索空间.然而, 对于IR-Tree有两个重要的观察. ① IR-Tree在每一层都嵌入了倒排列表结构, 因此, 每个字符串会被冗余地显式存储, 并导致巨大的空间开销; ② IR-Tree在每一层的搜索都进行了准确的匹配, 这并不是必要的.

基于这两个观察, 可以对IR-Tree进行以下优化. ①在非叶子节点, 不再基于倒排列表进行文本剪枝, 而是用布隆过滤器对子节点的文本信息进行抽象.由于布隆过滤器没有显式地存储字符串, 可以达到更小的空间开销. ②在叶子节点, 依然基于倒排列表进行准确匹配, 以保证能够找出所有满足空间和文本要求的空间文本对象并避免误报的发生.

3.2 RI$^+$结构

上面提到的IR-Tree结构和RI结构都是基于空间索引结构的扩展结构, 然而往往都忽视了低频词汇在文本过滤中的剪枝作用.由于低频词汇只被少数空间文本对象拥有, 通过基于文本索引(如倒排列表)的扩展结构对数据进行索引时, 可以通过低频词汇快速缩小搜索空间.基于此, 这里采用了RI$^+$索引结构(见图 2). RI$^+$结构基于倒排列表结构对空间文本数据集进行组织, 对于低频字符串, 将包含该字符串的对象组织为R-Tree结构; 对于非低频词汇, 将包含该字符串的对象组织为上述的RI结构.

对于布尔范围查询, 首先在查询字符串集合中找到低频词汇(在构建RI$^+$索引结构时同时维护了一个布隆过滤器以保存所有的低频词汇).在找到低频词汇后, 将该低频词汇映射到对应的R-Tree结构.由于低频词汇对应的对象数目较少, 这里只需要使用该R-Tree结构进行空间过滤即可; 然后, 在叶子节点进行最后的文本过滤以找出最终解.如果没有找到低频词汇, 则直接选择查询字符串集合的第一个字符串$s_j$并映射到其对应的RI结构.考虑到非低频词汇对应的空间文本对象数目较多, 基于R-Tree进行索引只能利用空间的剪枝作用, 无法高效地处理空间文本查询; 因此, 这里为了进一步结合文本的剪枝作用并且达到时间和空间占用上的平衡, 通过RI结构对非低频词汇对应的空间文本对象进行组织(注意到, RI结构基于布隆过滤器进行优化, 相比IR-Tree等结构有着更低的空间占用).最后, 通过非低频词汇$s_j$对应的RI结构处理新的空间文本查询$Q''=\{Q_s=(\tau, \epsilon), Q_{t}-s_j\}$.

4 全局索引构建

全局索引并不总是有益的.一方面, 使我们能够访问较少的分区, 从而节省更多的CPU资源, 降低网络成本; 但另一方面, 会导致额外的空间开销和时间开销.为了充分利用文本的剪枝作用, 本文采用了BFR全局索引结构^[25]以应用于海量空间文本数据的场景.

BFR索引是基于R-Tree结构的多叉树结构, BFR索引的非叶子节点和R-Tree的非叶子节点一样, 只保存了空间边界信息.其叶子节点的每个记录存储了一个数据分区的id、空间边界信息及布隆过滤器.分区的空间边界信息由该分区所有点坐标信息获得; 这里数据分区对应的布隆过滤器存储了该分区下每个空间文本对象包含的字符串.由于没有显式地存储字符串数据, 通过布隆过滤器存储文本数据的方案可以达到更低的空间占用.同时, 通过布隆过滤器可以对相应的空间文本查询进行文本维度的过滤.

BFR索引的查询算法.给定布尔范围查询, 可以基于BFR索引进行搜索并返回符合查询的候选分区.其中, 在非叶子节点过滤出与查询中心的距离在空间阈值范围内的子节点; 在叶子节点, 除了空间过滤外, 进一步检查查询的所有字符串是否都存在于分区对应的布隆过滤器中.如果都存在则满足文本过滤条件, 该分区成为候选分区以进行进一步处理; 否则被丢弃.

5 分布式的空间文本查询算法实现

本节将针对研究的两种空间文本查询问题进行依次探究.首先, 将基于上述的框架和索引结构对布尔范围查询的分布式算法进行探究; 然后, 将对空间文本相似连接进行更为深入的探索.

5.1 布尔范围查询

基于上述的两层索引框架, 布尔范围查询的分布式处理算法如下.

全局过滤.首先, 基于全局索引选出候选分区.具体来讲, 通过BFR索引结构找出所有空间边界与给定的圆形查询范围有交叉且其布隆过滤器包含所有的查询字符串的分区, 并对这些分区进行局部过滤.

局部过滤.针对全局过滤后得到的每个分区, 基于每个分区建立的vRI$^+$v索引结构进行布尔范围查询; 最后, 将每个候选分区处理后的结果汇集到全局节点.

5.2 空间文本相似连接

作为当下主流的分布式空间数据分析框架, 先前的工作^[4]提出了两种基于距离的空间相似连接方案.下面, 对这两种方案进行回顾, 并基于这两种方案进行扩展提出6种分布式下的空间文本相似连接方案.

5.2.1 分布式下的空间相似连接

给定空间数据集合$\mathcal{R}$和$\mathcal{S}$, 基于距离的空间相似连接将找出所有的$(r, s)$, 满足$r \in \mathcal{R}, s \in \mathcal{S}$且$dist(r, s)$小于等于给定的距离阈值$\epsilon$.先前的工作^[4]主要提出了两种分布式下基于距离的空间相似连接方案, 其细节如下.

(1) 首先, 基于Sort-tile-recursive^[26]算法对于$\mathcal{R}$数据集进行分区, 收集其各个分区的空间边界信息(MBR)并以这些分区的边界信息构建$\mathcal{R}$的R-Tree结构.然后, 将这个R-Tree广播到各个节点.基于这个对$\mathcal{R}$的分区边界信息构建的R-Tree, 对$\mathcal{S}$中的每个点$s_i$求出与$s_i$距离在距离阈值$\epsilon$内的$\mathcal{R}$数据集分区列表.例如, 假设$\mathcal{R}$的分区边界中, 与点$s_i$的距离小于等于$\epsilon$的分区边界对应的分区id列表为$\{1, 3, 4, 8\}$, 可以将点$s_i$冗余映射为$\{(s_i, 1), (s_i, 3, ), (s_i, 4), (s_i, 8)\}$.最后, 对$\mathcal{S}$冗余映射后的数据集合$\mathcal{S}'$, 按每个数据的映射的分区号进行重新分区.这样, $\mathcal{R}$和$\mathcal{S}'$的分区数目相同, 且$\mathcal{R}$的任一分区(不妨设为第$i$个分区)只能与$\mathcal{S}'$的对应分区(第$i$个分区)进行连接操作.

(2) 首先, 对$\mathcal{R}$和$\mathcal{S}$分别基于Sort-tile-recursive算法进行分区, 并对两个数据集分别收集各个分区的空间边界信息; 显然对于$\mathcal{R}$和$\mathcal{S}$的任一分区对$(\mathcal{R}_i, \mathcal{S}_j)$, 当前仅当两个分区的最小距离min$dist(\mathcal{R}_i, \mathcal{S}_j) \leq \epsilon$时, 其可能存在满足连接条件的点对.因此, 可以分别对这两个数据集构建基于分区边界信息的R-Tree结构, 并对这两个R-Tree进行连接操作找出所有满足min$dist(\mathcal{R}_i, \mathcal{S}_j) \leq \epsilon$的分区对, 最后对这些分区对进行局部的连接操作.

5.2.2 分布式下的空间文本相似连接

上述两种方案找出了满足连接条件的局部分区对.对于每个局部分区对, 文章进一步探索了相应的空间文本相似连接算法.本文在第1.3节中回顾了前缀过滤技术, 前缀过滤作为文本相似连接当中广泛应用的技术, 能够大大减少需要扫描的字符串数目.对于需要连接的两个空间文本数据分区$\mathcal{R}_i$和$\mathcal{S}_j$, 最直接的想法是基于传统的文本相似连接算法进行扩展.对于$\mathcal{R}_i$分区里的每个空间文本对象$o=(\rho, \gamma)$, 首先对其包含的字符串集合根据给定的Jaccard阈值$\lambda$生成长度为$|\gamma|-\lceil \lambda \times |\gamma| \rceil+1$的前缀; 然后, 基于倒排列表结构将前缀中的各个字符串映射到$o$.依此对$\mathcal{R}_i$分区的所有数据进行索引后, 对于$\mathcal{S}_j$中的每个空间文本对象, 同样生成其文本前缀, 并基于前面生成的倒排列表结构依次扫描当前前缀当中的每个字符串.对于映射的每个$\mathcal{R}_i$中的对象, 如果与当前$\mathcal{S}_j$的空间文本对象空间距离在给定范围内的话, 则加其为候选解.最后, 对所有的候选解进行验证, 检查各个候选解与当前空间文本对象的文本Jaccard相似度是否大于等于$\lambda$.

注意到上面的方案是先利用文本剪枝作用再利用空间距离进行过滤, 另外一种直接的思路是先进行空间过滤再进行文本剪枝.类似第5.2.1节提到的第二种方案, 可以先对$\mathcal{R}_i$和$\mathcal{S}_j$分别构建R-Tree结构, 然后将两个R-Tree进行连接, 最后找出所有满足空间连接条件的叶子节点对; 对于叶子节点对, 可以依照上面提到的文本连接算法进行进一步处理.注意由于$\mathcal{R}_i$对应的R-Tree中每个叶子节点可能和$\mathcal{S}_j$的R-Tree的多个叶子节点进行连接, 这样每次连接的时候都需要对其叶子节点构建一次基于文本前缀的倒排列表结构, 导致了额外的开销.因此, 这里需要在构建$\mathcal{R}_i$的R-Tree时, 在其叶子节点同时嵌入该叶子节点包含的空间文本对象对应的基于前缀的倒排列表结构, 以避免多次创建该倒排列表的额外开销.

上述两个方案的缺陷是只利用了一个维度的剪枝能力.比如上述的第二个方案, 首先基于空间过滤再进行文本剪枝; 当给定的空间距离阈值很大且文本相似度阈值也很大时, 由于此时空间的剪枝能力几乎失效, 该方案会产生大量的叶子节点对.然而, 根据文本相似度限制, 此时真正满足连接条件的数据对应该较少.显然, 在这种场景下第二个方案的效率大大降低.同样, 在空间距离阈值很小且文本相似度也很小的场景下, 基于文本优先的方案也会产生效率问题.回顾在研究布尔范围查询时, 文章采用了RI结构, 其同时利用了空间和文本的剪枝能力. RI结构同样可以应用于空间文本相似连接问题, 在该问题背景下, 本文对RI结构进行修改并提出了Prefix-RI结构.具体来讲, Prefix-RI结构相对于RI结构的修改如下.

(1) 叶子节点不需要对其包含的所有字符串进行索引, 而是对每个空间文本对象的文本前缀中的字符串进行索引.

(2) 在非叶子节点的布隆过滤器中, 只存储子树中包含的空间文本对象的文本前缀中的字符串.

利用在$\mathcal{R}_i$上建立的Prefix-RI索引, 可以对$\mathcal{S}_j$中的每一条记录在Prefix-RI索引上查找与其相似的对象集合.其算法细节如算法1所示.

在阐述该算法前, 先介绍Prefix-RI结构的一个重要性质.

性质5.1  给定基于空间文本数据集合$\mathcal{R}$建立的Prefix-RI索引, 对于$\mathcal{S}$中的任意一个空间文本对象$o_s=(\rho_s, \gamma_s)$, 若该索引的非叶子节点$\mathcal{N}$对应的子树包含与$o_s$相似的对象, 则对于$o_s$的文本前缀, 其至少有一个字符串存在于$\mathcal{N}$对应的布隆过滤器中.

证  明  不失一般性的, 假设非叶子节点$\mathcal{N}$对应的子树下存在一个与$o_s$相似的空间文本对象$o_r$.由前缀过滤技术的性质可知, $o_s$和$o_r$的文本前缀至少存在一个相同的字符串$\zeta$.同时, 根据前面所述的Prefix-RI索引的结构特点, 非叶子节点$\mathcal{N}$对应的布隆过滤器中存储了该子树下包含的所有空间文本对象的文本前缀; 因此, 可知$\zeta$必然存在于$\mathcal{N}$对应的布隆过滤器中.综上, 性质得证.

接下来对基于Prefix-RI索引结构的搜索算法进行详细介绍.如算法1所示, 对于$\mathcal{S}_j$中的一个空间文本对象$o_s=(\rho_s, \gamma_s)$, 首先根据文本相似度阈值$\lambda$计算其前缀长度(行1).由于Prefix-RI索引为树形结构, 需要从其根节点开始扫描并从上至下递归到叶子节点(行3—5).当扫描到非叶子节点时(行6), 首先检查$o_s$的文本前缀当中是否至少有一个字符串存在于该节点对应的布隆过滤器(行7—13);当该非叶子节点满足上述条件时, 则对该节点中满足空间范围要求的子节点进行递归搜索(行14—16).最后, 当扫描到叶子节点时(行17), 将$o_s$的文本前缀当中的各个字符串都映射到包含其的对象列表(行20—21), 并进行长度过滤和空间过滤以进一步找到候选对象(行22—23), 并对这些候选对象进行最后的验证(行24).

可以看出, 上述的第三种方案, 通过结合空间和文本两个维度的剪枝作用, 可以更好地应对前面两种方案的失效场景.最后, 结合第5.2.1节中提到的两种分布式空间相似连接方案, 可以和上述3种方案进行进一步的组合.具体来讲, 首先通过这两种空间连接方案产生需要进行空间文本连接的局部分区对; 然后, 对于每个局部分区对, 采用本文介绍的3种空间文本数据连接方案进行进一步处理.根据这样的组合, 总共有6种分布式的空间文本相似连接方案: Spatial-first, Textual-first, Hybrid, Allpairs-Spatial-first, Allpairs-Textual-first及Allpairs-Hybrid. 表 1对这6种方案进行了详细介绍.

6 实验探究 6.1 实验设置

为了验证所提出算法的实际运行效果, 本文基于Spark SQL实现了相应的索引技术和2种空间文本查询操作.此外, 本文采用了由9个节点组成的集群进行实验探究, 由于实验设备的采购时间不一致, 主要包括以下3种不同配置的机器: ① 1台具有24核Intel Xeon E5-2620 2.00 GHz处理器和192 GB RAM的机器; ② 5台配备6核Intel Xeon E5-2603 v3 1.60 GHz处理器和20 GB RAM的机器; ③ 3台配备6核Intel Xeon E5-2609 1.90 GHz处理器和16 GB RAM的机器.选择一台类型①的机器作为主节点, 其他机器都作为从节点; 另外, 每个从节点使用15 GB内存和所有可用的6个CPU进行后续计算.所有节点都运行在Ubuntu 14.04.2 LTS系统下, 且各个节点都安装了Hadoop 2.6.1和Spark 1.6.3框架.

本文使用了两个真实的海量数据集. ① OSM数据集, 其包含3 000万条记录.数据集的空间部分来自于OpenStreetMap项目^[27], 每个点由二维坐标表示; 另外, 每一个点关联了从SNAP^[28] (斯坦福网络数据集项目)收集的文本数据集中提取的字符串集合. ② TX-CA数据集^[27].该数据集中的点坐标代表了美国德克萨斯州和加利福尼亚州的真实道路网络和街道.此外, 将每个点的所在州、县和城镇名称相结合作为该点相关联的字符串集合.该数据集总共拥有2 600万条记录, 包括TX数据集共1 400万条, CA数据集共1 200万条.

基于以前的工作^[4-5], 本文主要关注吞吐量(每分钟处理的请求数)和时间延迟两个性能指标.对于布尔范围查询, 开启了10个线程不断地发出查询来模拟用户并发请求; 总共进行500次查询以进一步计算性能指标.为了生成测试集, 首先从原始数据集中随机选择一条记录, 并使用其点坐标作为查询位置; 然后, 为了进一步了解字符串数目对查询性能的影响, 还从该记录中随机选择1到4个字符串作为查询字符串集合.此外, 本文还尝试探索查询区域对性能的影响; 这里, 查询区域定义为查询半径与数据集边界的长和宽较小值的百分比, 默认值为$1\%$.在实验中, 查询区域比例在$\{1\%, 5\%, 10\%, 15\%, 20\%\}$之间变化.对于空间文本相似连接, 其空间距离阈值变化范围为$\{0.01, 0.02, 0.03, 0.04, 0.05\}$ (近似对应了$1\%$至$5\%$的查询区域); 其文本相似度阈值变化范围为$\{0.6, 0.7, 0.8, 0.9\}$, 这里对文本相似度阈值的选择有以下考虑. ①许多与文本相似连接相关的工作都将文本相似度阈值限定在0.5以上^{[23, 29]}, 并且较小的文本相似度阈值没有实际意义; ②当前的取值范围能够很好地覆盖实际应用场景.比如, 社交推荐等应用通常指定文本相似度阈值在0.6至0.7范围内变化; 文本去重等应用通常指定文本相似度阈值在0.8至0.9范围内变化.在所有实验中, HDFS块大小为64 MB; 由于集群总共有72个CPU核可用, 本文将数据集默认分为144个分区.

由于当下缺乏直接支持上述2种空间文本查询的分布式系统, 在实验中, 对于布尔范围查询的实验对比, 论文采取了以下3种方案. ①基于当下主流的空间数据分布式分析系统进行扩展.由于这些系统大多基于R-Tree进行索引, 可以通过在R-Tree的叶子节点层加入倒排列表结构使这些平台能够处理布尔范围查询.这里由于文献[4]的大量实验对比证明了其杰出的性能, 本文基于文献[4]提出的系统进行了扩展, 此方案在实验对比中简称为Baseline1. ②基于IR-Tree实现的分布式空间文本分析方案. IR-Tree主要用于局部索引的构建, 该方案依然使用了BFR索引作为全局索引技术, 此方案在实验对比中简称为Baseline2. ③基于RI$^+$索引实现的方案, 在实验中简称为RI$^+$.对于空间文本相似连接对提出的6种方案(Spatial-first, Textual-first, Hybrid, Allpairs-Spatial-first, Allpairs-Textual-first及Allpairs-Hybrid)进行了实验对比.

6.2 实验结果分析

索引空间开销.针对OSM数据集, 统计了两层索引的维护开销(在TX-CA数据集上的结果与此相似).首先, 针对3 000万条空间文本数据进行索引时, 采用的全局索引的空间占用仅为49.57 MB.通常, 维护全局索引的Master节点的物理内存可达到上百GB, 因此, 所采用的全局索引也能很好地应对更大的数据集带来的挑战.对于局部索引, IR-Tree的空间占用为59.8 GB而RI$^+$的空间占用为40.4 GB.可以发现, 采用的两层索引框架在空间占用方面具有较好的可扩展性.

查询字符串数目的影响.如图 3所示为查询字符串数目对布尔范围查询性能的影响.从图中可以看到, 这3种方案在查询字符串数目增大的时候性能都有提升.这是由于只有1个查询字符串的时候, 通常会有较多符合查询条件的解; 一方面查询命中的分区会更多, 另外在每个分区下的处理时间也更大.当查询字符串数目增大时, 满足条件的解数目大大减少, 带来了更强的剪枝能力.另外, 当查询字符串数目在2到4之间变化时, 此时性能变化不大; 这说明此时解集数目基本没有太大变化.注意到在有多个查询字符串时, 本文采用的索引技术由于更好地利用了低频词汇的剪枝能力, 取得了更好的性能.

查询范围的影响.如图 4所示, 当查询范围从$1\%$增大到$20\%$时, 3种方案都有性能的下降.一方面, 查询范围越大, 该查询在全局索引过滤时命中的分区个数越多; 另外一方面, 局部索引的空间剪枝能力也在变小.但是, 可以观察到, 由于Baseline1没有很好地利用文本的过滤能力, 在查询范围变大时性能下降明显要比其他两个更快; 另外由于RI$^+$索引技术更好地利用了低频词汇的剪枝能力, 其性能依然比Baseline2要更好, 达到了更好的稳定性.

数据集大小的影响.如图 5所示为数据集大小对布尔范围查询的影响.当数据规模从1千万增长到6千万($2 \times $ OSM数据集)时, 从实验结果来看, 文章提出的方案展现了更好的扩展性; 当数据规模增大时, 文章提出的方案性能下降趋势更慢.

全局索引的有效性验证.为了验证文章采用的全局索引的有效性, 通过图 6展示了使用R-Tree作为全局索引和使用BFR索引作为全局索引这两种方案的性能对比.基于前面的实验结果, 这里局部索引直接采用了RI$^+$索引结构.可以看到, 相对于只利用空间剪枝的全局索引, BFR索引技术达到了更好的性能.

文本相似度阈值的影响.如图 7所示为文本相似度阈值对空间文本相似连接的性能影响.随着文本相似度阈值的增大, 6种方案的耗时都在下降.显然文本相似度阈值越大, 根据前缀过滤技术的原理, 此时需要扫描的字符串数目越小; 因此, 需要验证的空间文本对象对数目也在下降.注意到, 在这6种方案中, 由于Hybrid方案同时结合了空间和文本的剪枝能力, 在实验中取得了最好的性能.相比之下, 由于Allpairs-Hybrid引入的分区对数目较多, 因此相比Hybrid的额外开销也会更大.另外, 实验发现基于文本优先的连接方案取得了最差的性能(包括Textual-First和Allpairs-Textual-First两个方案).

空间距离阈值的影响.如图 8所示, 随着空间距离阈值的增大, 所有方案的耗时都在增大.但对比可以发现, Hybrid方案消耗的时间最少且增长趋势更为缓慢; 这主要由于其结合了文本的剪枝作用, 所以, 对于查询空间范围的增大更为不敏感, 在实验中展现了更好的适应性.

7 总结

本文采用了分布式环境下的两层索引框架(包括全局索引和局部索引), 基于该框架本文提出了分布式的处理算法以解决空间文本相似连接等查询问题.同时, 本文基于Spark平台实现了所提出的分布式算法, 并在两个真实的数据集下进行了充分的实验对比, 实验结果验证了本文提出的算法的有效性.随着越来越多的工作致力于解决路网场景下的查询问题^[30-34], 在将来的工作中, 我们将进一步研究路网下的空间文本查询问题.