一种社交网络环境下并行短文本查询算法

雷建云，彭 媛，孙 翀，帖 军

(中南民族大学 计算机科学学院，武汉 430074)

随着互联网以及移动通信网络的快速发展，越来越多的社交网络软件方便了人们交流以及信息的传播，比如微博、Twitter等.微博每天在线用户可达一亿，Twitter每天产生4亿多条的推文，这些主流媒体软件都会产生带有时间和地理位置标签的短文本数据对象，产生的数据对象具有“海量”的特征.人们已经不再仅仅依靠社交圈进行联系，在实际生活中也可根据地理位置进行信息的共享，越来越多的对象和空间位置紧密关联起来.如何在海量拥有时间、地理位置标签的短文本数据对象中快速找到满足用户感兴趣的信息已经成为当前热点研究问题之一.

传统的移动社交网络环境下短文本查询算法大多采用集中式环境查询且只考虑数据对象间文本内容和地理位置的相关性，导致反馈给用户结果花费的时间较长，可能失去时效性，无法满足用户的现实需求.因此，设计一个在海量数据下考虑时间维度的短文本查询算法具有重大意义，存在社会经济价值.

1 相关工作

近年来，由于移动社交网络的迅速发展，基于位置查询服务被广泛研究.2009年Gao Cong等人[1]提出基于Rtree和倒排索引的IR-tree索引，引入语言模型计算文本相关性，返回Top-k个相关性最强的web对象.Jinling Jiang等人[2]提出TKLUS(top-klocal user search)查询，结合文本相关性和距离相关性计算出用户分数，返回查询对象top-k个最具影响力的用户.综合考虑文本信息和地理位置信息成为用户查询问题的普遍解决方法[3-5].但是，仅考虑文本和空间位置信息不能满足所有需求，还需要考虑时间维度[6-8].

2014年，Magdy等人[9]提出Mercury实时查询系统，该系统能够在内存有限的条件下对拥有时间和地理位置属性的微博数据进行实时热点查询.2017年，李晨等人[10]针对带有地理位置和时间标签的文本信息，提出多样性感知的时空文本信息的k近邻查询处理方法，基于Rtree建立其经度、纬度与时间的混合三维索引，有效综合了数据对象的时间变量和空间变量，但对于数据流来说存在数据量增长快的特征，维护索引代价较高，只适合于离线数据.

为了能够实现高效查询目的，时空索引的研究得到快速发展,对于空间数据索引，Rtree索引[11]基本思想是将地理空间递归划分为不同层次的树结构，满足空间条件查询.随之发展了时空数据索引，如RT-tree[12]，3DR-tree[13]，TPR-tree[14]，等.3DR-tree是Theodoridis等人提出将时间属性作为第三维加入到二维空间索引中的.TPR-tree是基于R*-tree提出的在三维空间中的移动对象对未来移动位置的预测.

目前，时空短文本查询算法大多采用集中式环境处理查询算法，随着数据量的迅速增长已不能满足性能和效率的需求.因此，本文提出一种社交网络环境下并行短文本查询算法，在海量数据下综合考虑文本内容相似性、空间和时间属性来建立多版本时空索引，利用大数据分布式MapReduce框架实现并行计算，确保查询结果具有时效性，提高了查询效率，使查询到的结果质量更优.

2 问题描述

将无法在海量短文本数据对象得到快速响应且查询结果可能失去时效性的问题作为本文的切入点.查询结果是距离用户时间、地理位置相对接近且文本相关性较大的数据对象.

查询对象q={x,y,time,words,T,R}，其中x，y为地理坐标的经纬度，time表示用户查询时间，words为查询的关键字集合，T为查询的时间范围，R表示查询的空间距离范围.

设定D={p1,p2,…，pn}为数据对象集合，对于集合D中任意数据对象p={uid,x,y,time,words}，uid表示用户id，x，y为地理坐标的经纬度，time表示发布时间，words为用户发布短文本中提取的关键字集合，如表1所示.

表1 数据对象集合

定义1 文本相关性. 对于查询对象与数据对象的文本相关性定义如下：

(1)

利用Jaccard相似度函数计算文本内容之间的相关性.

定义2 空间相关性. 根据查询对象与数据对象之间的欧式距离与给定距离R来度量空间相关性，空间相关性公式如下：

(2)

教师可以在大学英语教学中融入中国文化元素，帮助学生更多地了解中国文化并发挥英语传播中国文化的作用。教师可以开设中国文化类英语课程，用英语授课，帮助学生系统地学习中国文化。教师也可以引导学生多途径、自主地进行学习，如引导学生通过电视（CCTV International中央电视台英语频道）、英语广播(China Radio International中国国际广播电台)、英文报纸（如China Daily《中国日报》、21stCentury《21世纪英文报》）来学习中国文化及中国视角和价值观。在教学中，让学生不仅学习西方文化的英语表述，也要学习中国文化的英语表述，获得用英语表达中国文化的能力。

定义3 时间相关性. 根据给定合理的时间范围T计算时间相关性，公式为：

(3)

其中t=q·time-p·time.

定义4 综合相关性分数. 综合相关性分数查询对象与数据对象相关的衡量标准，是将文本相关性、空间相关性和时间相关性线性结合，定义如下：

Rank(q,p)=αSimwords(q,p)+βSimdist(q,p)+

(1-α-β)Simtime(q,p),

(4)

其中α和β为权重参数，0<α<1,0<β<1,0<α+β<1.

定义5 Top-k时空查询. 用户查询时不能将所有数据展示给用户，因此选取数据集D中距离查询对象在时间和地理位置以及文本最接近的Top-k个数据对象返回给用户.根据相关性分数得到结果集合:

Result={p1,p2,…,pk},

(5)

其中Result满足的条件为：Result⊆D,|Result|=k,pi∈Result,pj∈(D-Result),Rank(q,pi)≥Rank(q,pj).

图1给出一个查询问题实例，如图显示出5个不同地理位置发布的5条短文本数据对象p1至p5，数据对象信息如表1所示.查询对象q，给定查询关键字集合为{武汉，景点}，时间、空间范围分别为1h内和距离查询对象30 km内，综合考虑时间文本内容相关性和时间、空间因素，Top-3时空查询的结果为p1,p5,p3.

图1 查询实例Fig.1 Query instance

上述Top-3时空查询结果可通过依次计算查询对象与数据对象的综合相关性分数得到.若数据量非常大，计算代价会很大，花费时间长.为减少查询时间，满足用户高效性需求，我们综合考虑时间、空间属性，建立基于Rtree的MVSTR-tree索引，从而有效提高查询效率.

3 基于滑动窗口方法MVSTR-tree索引

如何在海量数据中快速查询到满足条件的数据，索引是有效途径之一，索引可大大加快查询速度.Rtree索引是传统空间数据索引，具有结构简单、适用范围广的特点.

社交网络数据是不断动态增加的，如果单独构建一个索引，当数据更新时会存在时间代价大的缺点.为了提高查询效率和减少更新代价，本文提出构建MVSTR-tree索引.MVSTR-tree索引在时间维度上利用滑动窗口对数据流进行分割，在水平方向上将时间分为不同时间段，垂直方向将每个时间段数据集合建立Rtree索引，不同时间段版本的Rtree索引共同构成MVSTR-tree索引.MVSTR-tree索引使用到的变量定义如表2所示.

表2 符号表

移动社交网络的数据是以数据流的形式到来，滑动窗口划分为N个基本窗口，每个基本窗口保存一个周期P内的所有数据，滑动窗口内保存时间段为N·P的数据.采用滑动窗口来建立索引的策略，MVSTR-tree索引结构如图2所示.

图2 MVSTR-tree索引结构Fig.2 Structure of MVSTR-tree index

实时更新滑动窗口代价较大，因此采用窗口划分和缓冲区处理方法，将更新周期P内的数据放入缓冲区，当周期P到来时，将缓冲区数据放入基本窗口中并建立起地理位置的Rtree索引.如图2所示的窗口W1,索引个数达到N个时，表示滑动窗口已满，即完成MVSTR-tree索引的构建，构建MVSTR -tree索引算法如算法1所述.

因为社交网络数据是动态变化且数量非常大，为了保证得到的结果具有时效性，需要更新维护MVSTR-tree索引结构，保持窗口的个数为N.每当更新周期到来时，将更新周期内的数据存入新基本窗口中，建立新版本索引，删除过期基本窗口和对应的索引文件，成为更新后的MVSTR-tree索引.图2中滑动窗口W1，基本窗口个数为N，经过更新周期P后，增加新的基本窗口以及生成索引文件，删除过期基本窗口，生成滑动窗口W2，MVSTR-tree索引结构随之更新.

算法1MVSTR -tree索引的构建输入N个周期P内数据集合, 输出构建的MVSTR-tree索引初始化滑动窗口,链表While滑动窗口未满创建链表节点将周期P内数据集合D={p1,p2,…,pn}放入滑动窗口中 将集合D全部数据作为整体,取最小外界矩形(MBR)作为根节点以根节点MBR的4 个顶点(k=4)作为初始聚类中心,并计算距离将空间数据划分到最近的聚类中心按照K-Means算法,计算聚类中新的聚类中心,重新划分,不断迭代聚类,形成4个聚类;否则迭代执行步骤4上述的聚成的4个类分别作为整体,执行步骤5,6,7直到整个Rtree构建完成将新建索引文件存储在分布式文件系统(HDFS)中 在链表节点中存放索引文件路径End WhileReturn MVSTR-tree

4 分布式Top-k时空查询算法

在维护MVSTR-tree索引的良好结构下，若在集中式系统下实现海量数据查询，计算能力受到硬件条件限制，造成查询时间较长，不能满足用户的查询需求，降低了用户体验满意度.为提高Top-k时空查询效率，本文提出了DMRTop-k查询算法.该算法利用了MapReduce框架，将查询任务划分为多个Map子查询任务，从而实现并行查询目标.当所有子查询完成后，Reduce任务将子查询结果汇总，得到最后的Top-k结果集.

DMRTop-k算法的流程步骤如下：

1)根据用户限定的时间范围条件，过滤出MVSTR-tree索引中满足时间条件的子版本索引；

2)利用MapReduce框架实现并行化计算，使每个Map任务对应一个子版本索引文件，作为Map任务的输入单位.首先，每个Map任务进行子版本索引重构，再根据空间距离范围条件在子版本索引下执行Top-k时空查询，返回子查询结果；

3)将所有Map任务子查询结果汇总到一个Reduce任务，Reduce任务对结果进行排序并得到最终结果.

算法中的Map函数描述如下：

算法2Map函数输入子版本索引文件,查询对象q输出子查询结果集重构子版本索引文件还原Rtree结构初始化数组HFor each p在范围R内的数据对象Do //遍历满足地理范围的数据对象计算综合相关性分数,Rank(q,p)=αSimwords(q,p)+βSimdist(q,p)+(1-α-β)Simtime(q,p) If数组H元素个数< k then 将p加入H中并排序 Else then If数组最低分>Rank(q,p) then //判断计算的综合相关性是否大于最低综合相关性分数 Continue Else then 将H的最低分数对象移除 将p加入H中并排序 End If End IfEnd ForReturn H

DMRTop-k算法里的每个Map函数任务主要是找出对应索引满足空间位置条件的数据对象，计算与查询对象的综合相关性分数，输出子Top-k时空查询结果.当子查询完成后，Reduce函数为合并阶段，完成对多个Map子查询输出的汇总，返回Top-k时空查询结果，Reduce函数如下所示.

算法3Reduce函数输入所有Map子查询的结果集输出Top-k时空查询结果集初始化 P,ResultFor each in结果集 do P.push(p,Rank)Sort(P)Result=GetTop-k (P) //取前Top-k个结果Return Result

5 实验与分析

5.1 实验环境

实验分为集中式构建维护索引环境和分布式查询环境，配置见表3.

分布式平台搭建在Hadoop集群上，本文采用5个结点的集群，Hadoop集群的节点分为1个master节点和4个slave节点.

表3 实验配置

本文实验采用的数据集包括：1)微博数据集.包括106条微博语料，每条数据包含文本信息、发布时间以及真实地理坐标.利用Python的分词工具对文本信息预处理提取出文本中的关键字；2)在Twitter数据集抽取5×106条数据，每条数据对象包括关键字集合、发布时间和地理位置坐标信息.

5.2 实验结果与分析

设置时间T为1h，P为5min，T为30min，将调节权重的参数α设定为0.3，β设定0.4，k设定为10.由图3显示在两个数据集下，随着实验数据量的增大，本文提出的DMRTop-k算法的查询时间明显低于单机下的Rtree算法[11]的查询时间，在数据量越大的情况下查询时间增加缓慢，有效地减少了查询时间.

图3 数据量大小对查询时间的影响Fig.3 Query time effect of datasize

图4 k取值对查询时间的影响Fig.4 Query time effect of k

图4显示在两个数据集下选取106条数据时随k值改变的时间变化趋势，本文提出的DMRTop-k算法的查询时间低于Rtree算法查询时间，在同一算法下随着k值的变化查询时间的变化趋势较小.图5显示的是在不同的数据量下，总体是随着slave节点数的增大，查询时间减少.slave节点数越多，查询时间越少，极大地减小了查询时间.

图5 slave数对查询时间的影响Fig.5 Query time effect of slave number

6 结语

本文的工作主要是：(1)综合考虑时间属性和地理位置属性，解决社交网络下传统短文本查询算法对时效不敏感的问题；(2)设计了基于MapReduce框架下的时空查询算法，实现对海量数据高效查询的目标.

本文在计算文本内容相似性时，只是使用Jaccard相似度函数评价查询对象与数据对象之间关键字的匹配程度，没有考虑文本之间的语义、词性和文本结构等因素，下一步的工作是考虑文本间多个因素来提高文本相似性匹配的准确度.