雷建云，彭 媛，孫 翀，帖 軍

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢 430074)

隨著互聯(lián)網(wǎng)以及移動(dòng)通信網(wǎng)絡(luò)的快速發(fā)展，越來越多的社交網(wǎng)絡(luò)軟件方便了人們交流以及信息的傳播，比如微博、Twitter等.微博每天在線用戶可達(dá)一億，Twitter每天產(chǎn)生4億多條的推文，這些主流媒體軟件都會(huì)產(chǎn)生帶有時(shí)間和地理位置標(biāo)簽的短文本數(shù)據(jù)對(duì)象，產(chǎn)生的數(shù)據(jù)對(duì)象具有“海量”的特征.人們已經(jīng)不再僅僅依靠社交圈進(jìn)行聯(lián)系，在實(shí)際生活中也可根據(jù)地理位置進(jìn)行信息的共享，越來越多的對(duì)象和空間位置緊密關(guān)聯(lián)起來.如何在海量擁有時(shí)間、地理位置標(biāo)簽的短文本數(shù)據(jù)對(duì)象中快速找到滿足用戶感興趣的信息已經(jīng)成為當(dāng)前熱點(diǎn)研究問題之一.

傳統(tǒng)的移動(dòng)社交網(wǎng)絡(luò)環(huán)境下短文本查詢算法大多采用集中式環(huán)境查詢且只考慮數(shù)據(jù)對(duì)象間文本內(nèi)容和地理位置的相關(guān)性，導(dǎo)致反饋給用戶結(jié)果花費(fèi)的時(shí)間較長，可能失去時(shí)效性，無法滿足用戶的現(xiàn)實(shí)需求.因此，設(shè)計(jì)一個(gè)在海量數(shù)據(jù)下考慮時(shí)間維度的短文本查詢算法具有重大意義，存在社會(huì)經(jīng)濟(jì)價(jià)值.

1 相關(guān)工作

近年來，由于移動(dòng)社交網(wǎng)絡(luò)的迅速發(fā)展，基于位置查詢服務(wù)被廣泛研究.2009年Gao Cong等人[1]提出基于Rtree和倒排索引的IR-tree索引，引入語言模型計(jì)算文本相關(guān)性，返回Top-k個(gè)相關(guān)性最強(qiáng)的web對(duì)象.Jinling Jiang等人[2]提出TKLUS(top-klocal user search)查詢，結(jié)合文本相關(guān)性和距離相關(guān)性計(jì)算出用戶分?jǐn)?shù)，返回查詢對(duì)象top-k個(gè)最具影響力的用戶.綜合考慮文本信息和地理位置信息成為用戶查詢問題的普遍解決方法[3-5].但是，僅考慮文本和空間位置信息不能滿足所有需求，還需要考慮時(shí)間維度[6-8].

2014年，Magdy等人[9]提出Mercury實(shí)時(shí)查詢系統(tǒng)，該系統(tǒng)能夠在內(nèi)存有限的條件下對(duì)擁有時(shí)間和地理位置屬性的微博數(shù)據(jù)進(jìn)行實(shí)時(shí)熱點(diǎn)查詢.2017年，李晨等人[10]針對(duì)帶有地理位置和時(shí)間標(biāo)簽的文本信息，提出多樣性感知的時(shí)空文本信息的k近鄰查詢處理方法，基于Rtree建立其經(jīng)度、緯度與時(shí)間的混合三維索引，有效綜合了數(shù)據(jù)對(duì)象的時(shí)間變量和空間變量，但對(duì)于數(shù)據(jù)流來說存在數(shù)據(jù)量增長快的特征，維護(hù)索引代價(jià)較高，只適合于離線數(shù)據(jù).

為了能夠?qū)崿F(xiàn)高效查詢目的，時(shí)空索引的研究得到快速發(fā)展,對(duì)于空間數(shù)據(jù)索引，Rtree索引[11]基本思想是將地理空間遞歸劃分為不同層次的樹結(jié)構(gòu)，滿足空間條件查詢.隨之發(fā)展了時(shí)空數(shù)據(jù)索引，如RT-tree[12]，3DR-tree[13]，TPR-tree[14]，等.3DR-tree是Theodoridis等人提出將時(shí)間屬性作為第三維加入到二維空間索引中的.TPR-tree是基于R*-tree提出的在三維空間中的移動(dòng)對(duì)象對(duì)未來移動(dòng)位置的預(yù)測(cè).

目前，時(shí)空短文本查詢算法大多采用集中式環(huán)境處理查詢算法，隨著數(shù)據(jù)量的迅速增長已不能滿足性能和效率的需求.因此，本文提出一種社交網(wǎng)絡(luò)環(huán)境下并行短文本查詢算法，在海量數(shù)據(jù)下綜合考慮文本內(nèi)容相似性、空間和時(shí)間屬性來建立多版本時(shí)空索引，利用大數(shù)據(jù)分布式MapReduce框架實(shí)現(xiàn)并行計(jì)算，確保查詢結(jié)果具有時(shí)效性，提高了查詢效率，使查詢到的結(jié)果質(zhì)量更優(yōu).

2 問題描述

將無法在海量短文本數(shù)據(jù)對(duì)象得到快速響應(yīng)且查詢結(jié)果可能失去時(shí)效性的問題作為本文的切入點(diǎn).查詢結(jié)果是距離用戶時(shí)間、地理位置相對(duì)接近且文本相關(guān)性較大的數(shù)據(jù)對(duì)象.

查詢對(duì)象q={x,y,time,words,T,R}，其中x，y為地理坐標(biāo)的經(jīng)緯度，time表示用戶查詢時(shí)間，words為查詢的關(guān)鍵字集合，T為查詢的時(shí)間范圍，R表示查詢的空間距離范圍.

設(shè)定D={p1,p2,…，pn}為數(shù)據(jù)對(duì)象集合，對(duì)于集合D中任意數(shù)據(jù)對(duì)象p={uid,x,y,time,words}，uid表示用戶id，x，y為地理坐標(biāo)的經(jīng)緯度，time表示發(fā)布時(shí)間，words為用戶發(fā)布短文本中提取的關(guān)鍵字集合，如表1所示.

表1 數(shù)據(jù)對(duì)象集合

定義1 文本相關(guān)性. 對(duì)于查詢對(duì)象與數(shù)據(jù)對(duì)象的文本相關(guān)性定義如下：

(1)

利用Jaccard相似度函數(shù)計(jì)算文本內(nèi)容之間的相關(guān)性.

定義2 空間相關(guān)性. 根據(jù)查詢對(duì)象與數(shù)據(jù)對(duì)象之間的歐式距離與給定距離R來度量空間相關(guān)性，空間相關(guān)性公式如下：

(2)

教師可以在大學(xué)英語教學(xué)中融入中國文化元素，幫助學(xué)生更多地了解中國文化并發(fā)揮英語傳播中國文化的作用。教師可以開設(shè)中國文化類英語課程，用英語授課，幫助學(xué)生系統(tǒng)地學(xué)習(xí)中國文化。教師也可以引導(dǎo)學(xué)生多途徑、自主地進(jìn)行學(xué)習(xí)，如引導(dǎo)學(xué)生通過電視（CCTV International中央電視臺(tái)英語頻道）、英語廣播(China Radio International中國國際廣播電臺(tái))、英文報(bào)紙（如China Daily《中國日?qǐng)?bào)》、21stCentury《21世紀(jì)英文報(bào)》）來學(xué)習(xí)中國文化及中國視角和價(jià)值觀。在教學(xué)中，讓學(xué)生不僅學(xué)習(xí)西方文化的英語表述，也要學(xué)習(xí)中國文化的英語表述，獲得用英語表達(dá)中國文化的能力。

定義3 時(shí)間相關(guān)性. 根據(jù)給定合理的時(shí)間范圍T計(jì)算時(shí)間相關(guān)性，公式為：

(3)

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

定義4 綜合相關(guān)性分?jǐn)?shù). 綜合相關(guān)性分?jǐn)?shù)查詢對(duì)象與數(shù)據(jù)對(duì)象相關(guān)的衡量標(biāo)準(zhǔn)，是將文本相關(guān)性、空間相關(guān)性和時(shí)間相關(guān)性線性結(jié)合，定義如下：

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

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

(4)

其中α和β為權(quán)重參數(shù)，0<α<1,0<β<1,0<α+β<1.

定義5 Top-k時(shí)空查詢. 用戶查詢時(shí)不能將所有數(shù)據(jù)展示給用戶，因此選取數(shù)據(jù)集D中距離查詢對(duì)象在時(shí)間和地理位置以及文本最接近的Top-k個(gè)數(shù)據(jù)對(duì)象返回給用戶.根據(jù)相關(guān)性分?jǐn)?shù)得到結(jié)果集合:

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

(5)

其中Result滿足的條件為：Result?D,|Result|=k,pi∈Result,pj∈(D-Result),Rank(q,pi)≥Rank(q,pj).

圖1給出一個(gè)查詢問題實(shí)例，如圖顯示出5個(gè)不同地理位置發(fā)布的5條短文本數(shù)據(jù)對(duì)象p1至p5，數(shù)據(jù)對(duì)象信息如表1所示.查詢對(duì)象q，給定查詢關(guān)鍵字集合為{武漢，景點(diǎn)}，時(shí)間、空間范圍分別為1h內(nèi)和距離查詢對(duì)象30 km內(nèi)，綜合考慮時(shí)間文本內(nèi)容相關(guān)性和時(shí)間、空間因素，Top-3時(shí)空查詢的結(jié)果為p1,p5,p3.

圖1 查詢實(shí)例Fig.1 Query instance

上述Top-3時(shí)空查詢結(jié)果可通過依次計(jì)算查詢對(duì)象與數(shù)據(jù)對(duì)象的綜合相關(guān)性分?jǐn)?shù)得到.若數(shù)據(jù)量非常大，計(jì)算代價(jià)會(huì)很大，花費(fèi)時(shí)間長.為減少查詢時(shí)間，滿足用戶高效性需求，我們綜合考慮時(shí)間、空間屬性，建立基于Rtree的MVSTR-tree索引，從而有效提高查詢效率.

3 基于滑動(dòng)窗口方法MVSTR-tree索引

如何在海量數(shù)據(jù)中快速查詢到滿足條件的數(shù)據(jù)，索引是有效途徑之一，索引可大大加快查詢速度.Rtree索引是傳統(tǒng)空間數(shù)據(jù)索引，具有結(jié)構(gòu)簡(jiǎn)單、適用范圍廣的特點(diǎn).

社交網(wǎng)絡(luò)數(shù)據(jù)是不斷動(dòng)態(tài)增加的，如果單獨(dú)構(gòu)建一個(gè)索引，當(dāng)數(shù)據(jù)更新時(shí)會(huì)存在時(shí)間代價(jià)大的缺點(diǎn).為了提高查詢效率和減少更新代價(jià)，本文提出構(gòu)建MVSTR-tree索引.MVSTR-tree索引在時(shí)間維度上利用滑動(dòng)窗口對(duì)數(shù)據(jù)流進(jìn)行分割，在水平方向上將時(shí)間分為不同時(shí)間段，垂直方向?qū)⒚總€(gè)時(shí)間段數(shù)據(jù)集合建立Rtree索引，不同時(shí)間段版本的Rtree索引共同構(gòu)成MVSTR-tree索引.MVSTR-tree索引使用到的變量定義如表2所示.

表2 符號(hào)表

移動(dòng)社交網(wǎng)絡(luò)的數(shù)據(jù)是以數(shù)據(jù)流的形式到來，滑動(dòng)窗口劃分為N個(gè)基本窗口，每個(gè)基本窗口保存一個(gè)周期P內(nèi)的所有數(shù)據(jù)，滑動(dòng)窗口內(nèi)保存時(shí)間段為N·P的數(shù)據(jù).采用滑動(dòng)窗口來建立索引的策略，MVSTR-tree索引結(jié)構(gòu)如圖2所示.

圖2 MVSTR-tree索引結(jié)構(gòu)Fig.2 Structure of MVSTR-tree index

實(shí)時(shí)更新滑動(dòng)窗口代價(jià)較大，因此采用窗口劃分和緩沖區(qū)處理方法，將更新周期P內(nèi)的數(shù)據(jù)放入緩沖區(qū)，當(dāng)周期P到來時(shí)，將緩沖區(qū)數(shù)據(jù)放入基本窗口中并建立起地理位置的Rtree索引.如圖2所示的窗口W1,索引個(gè)數(shù)達(dá)到N個(gè)時(shí)，表示滑動(dòng)窗口已滿，即完成MVSTR-tree索引的構(gòu)建，構(gòu)建MVSTR -tree索引算法如算法1所述.

因?yàn)樯缃痪W(wǎng)絡(luò)數(shù)據(jù)是動(dòng)態(tài)變化且數(shù)量非常大，為了保證得到的結(jié)果具有時(shí)效性，需要更新維護(hù)MVSTR-tree索引結(jié)構(gòu)，保持窗口的個(gè)數(shù)為N.每當(dāng)更新周期到來時(shí)，將更新周期內(nèi)的數(shù)據(jù)存入新基本窗口中，建立新版本索引，刪除過期基本窗口和對(duì)應(yīng)的索引文件，成為更新后的MVSTR-tree索引.圖2中滑動(dòng)窗口W1，基本窗口個(gè)數(shù)為N，經(jīng)過更新周期P后，增加新的基本窗口以及生成索引文件，刪除過期基本窗口，生成滑動(dòng)窗口W2，MVSTR-tree索引結(jié)構(gòu)隨之更新.

算法1MVSTR -tree索引的構(gòu)建輸入N個(gè)周期P內(nèi)數(shù)據(jù)集合, 輸出構(gòu)建的MVSTR-tree索引初始化滑動(dòng)窗口,鏈表While滑動(dòng)窗口未滿創(chuàng)建鏈表節(jié)點(diǎn)將周期P內(nèi)數(shù)據(jù)集合D={p1,p2,…,pn}放入滑動(dòng)窗口中 將集合D全部數(shù)據(jù)作為整體,取最小外界矩形(MBR)作為根節(jié)點(diǎn)以根節(jié)點(diǎn)MBR的4 個(gè)頂點(diǎn)(k=4)作為初始聚類中心,并計(jì)算距離將空間數(shù)據(jù)劃分到最近的聚類中心按照K-Means算法,計(jì)算聚類中新的聚類中心,重新劃分,不斷迭代聚類,形成4個(gè)聚類;否則迭代執(zhí)行步驟4上述的聚成的4個(gè)類分別作為整體,執(zhí)行步驟5,6,7直到整個(gè)Rtree構(gòu)建完成將新建索引文件存儲(chǔ)在分布式文件系統(tǒng)(HDFS)中 在鏈表節(jié)點(diǎn)中存放索引文件路徑End WhileReturn MVSTR-tree

4 分布式Top-k時(shí)空查詢算法

在維護(hù)MVSTR-tree索引的良好結(jié)構(gòu)下，若在集中式系統(tǒng)下實(shí)現(xiàn)海量數(shù)據(jù)查詢，計(jì)算能力受到硬件條件限制，造成查詢時(shí)間較長，不能滿足用戶的查詢需求，降低了用戶體驗(yàn)滿意度.為提高Top-k時(shí)空查詢效率，本文提出了DMRTop-k查詢算法.該算法利用了MapReduce框架，將查詢?nèi)蝿?wù)劃分為多個(gè)Map子查詢?nèi)蝿?wù)，從而實(shí)現(xiàn)并行查詢目標(biāo).當(dāng)所有子查詢完成后，Reduce任務(wù)將子查詢結(jié)果匯總，得到最后的Top-k結(jié)果集.

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

1)根據(jù)用戶限定的時(shí)間范圍條件，過濾出MVSTR-tree索引中滿足時(shí)間條件的子版本索引；

2)利用MapReduce框架實(shí)現(xiàn)并行化計(jì)算，使每個(gè)Map任務(wù)對(duì)應(yīng)一個(gè)子版本索引文件，作為Map任務(wù)的輸入單位.首先，每個(gè)Map任務(wù)進(jìn)行子版本索引重構(gòu)，再根據(jù)空間距離范圍條件在子版本索引下執(zhí)行Top-k時(shí)空查詢，返回子查詢結(jié)果；

3)將所有Map任務(wù)子查詢結(jié)果匯總到一個(gè)Reduce任務(wù)，Reduce任務(wù)對(duì)結(jié)果進(jìn)行排序并得到最終結(jié)果.

算法中的Map函數(shù)描述如下：

算法2Map函數(shù)輸入子版本索引文件,查詢對(duì)象q輸出子查詢結(jié)果集重構(gòu)子版本索引文件還原Rtree結(jié)構(gòu)初始化數(shù)組HFor each p在范圍R內(nèi)的數(shù)據(jù)對(duì)象Do //遍歷滿足地理范圍的數(shù)據(jù)對(duì)象計(jì)算綜合相關(guān)性分?jǐn)?shù),Rank(q,p)=αSimwords(q,p)+βSimdist(q,p)+(1-α-β)Simtime(q,p) If數(shù)組H元素個(gè)數(shù)< k then 將p加入H中并排序 Else then If數(shù)組最低分>Rank(q,p) then //判斷計(jì)算的綜合相關(guān)性是否大于最低綜合相關(guān)性分?jǐn)?shù) Continue Else then 將H的最低分?jǐn)?shù)對(duì)象移除 將p加入H中并排序 End If End IfEnd ForReturn H

DMRTop-k算法里的每個(gè)Map函數(shù)任務(wù)主要是找出對(duì)應(yīng)索引滿足空間位置條件的數(shù)據(jù)對(duì)象，計(jì)算與查詢對(duì)象的綜合相關(guān)性分?jǐn)?shù)，輸出子Top-k時(shí)空查詢結(jié)果.當(dāng)子查詢完成后，Reduce函數(shù)為合并階段，完成對(duì)多個(gè)Map子查詢輸出的匯總，返回Top-k時(shí)空查詢結(jié)果，Reduce函數(shù)如下所示.

算法3Reduce函數(shù)輸入所有Map子查詢的結(jié)果集輸出Top-k時(shí)空查詢結(jié)果集初始化 P,ResultFor each in結(jié)果集 do P.push(p,Rank)Sort(P)Result=GetTop-k (P) //取前Top-k個(gè)結(jié)果Return Result

5 實(shí)驗(yàn)與分析

5.1 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)分為集中式構(gòu)建維護(hù)索引環(huán)境和分布式查詢環(huán)境，配置見表3.

分布式平臺(tái)搭建在Hadoop集群上，本文采用5個(gè)結(jié)點(diǎn)的集群，Hadoop集群的節(jié)點(diǎn)分為1個(gè)master節(jié)點(diǎn)和4個(gè)slave節(jié)點(diǎn).

表3 實(shí)驗(yàn)配置

本文實(shí)驗(yàn)采用的數(shù)據(jù)集包括：1)微博數(shù)據(jù)集.包括106條微博語料，每條數(shù)據(jù)包含文本信息、發(fā)布時(shí)間以及真實(shí)地理坐標(biāo).利用Python的分詞工具對(duì)文本信息預(yù)處理提取出文本中的關(guān)鍵字；2)在Twitter數(shù)據(jù)集抽取5×106條數(shù)據(jù)，每條數(shù)據(jù)對(duì)象包括關(guān)鍵字集合、發(fā)布時(shí)間和地理位置坐標(biāo)信息.

5.2 實(shí)驗(yàn)結(jié)果與分析

設(shè)置時(shí)間T為1h，P為5min，T為30min，將調(diào)節(jié)權(quán)重的參數(shù)α設(shè)定為0.3，β設(shè)定0.4，k設(shè)定為10.由圖3顯示在兩個(gè)數(shù)據(jù)集下，隨著實(shí)驗(yàn)數(shù)據(jù)量的增大，本文提出的DMRTop-k算法的查詢時(shí)間明顯低于單機(jī)下的Rtree算法[11]的查詢時(shí)間，在數(shù)據(jù)量越大的情況下查詢時(shí)間增加緩慢，有效地減少了查詢時(shí)間.

圖3 數(shù)據(jù)量大小對(duì)查詢時(shí)間的影響Fig.3 Query time effect of datasize

圖4 k取值對(duì)查詢時(shí)間的影響Fig.4 Query time effect of k

圖4顯示在兩個(gè)數(shù)據(jù)集下選取106條數(shù)據(jù)時(shí)隨k值改變的時(shí)間變化趨勢(shì)，本文提出的DMRTop-k算法的查詢時(shí)間低于Rtree算法查詢時(shí)間，在同一算法下隨著k值的變化查詢時(shí)間的變化趨勢(shì)較小.圖5顯示的是在不同的數(shù)據(jù)量下，總體是隨著slave節(jié)點(diǎn)數(shù)的增大，查詢時(shí)間減少.slave節(jié)點(diǎn)數(shù)越多，查詢時(shí)間越少，極大地減小了查詢時(shí)間.

圖5 slave數(shù)對(duì)查詢時(shí)間的影響Fig.5 Query time effect of slave number

6 結(jié)語

本文的工作主要是：(1)綜合考慮時(shí)間屬性和地理位置屬性，解決社交網(wǎng)絡(luò)下傳統(tǒng)短文本查詢算法對(duì)時(shí)效不敏感的問題；(2)設(shè)計(jì)了基于MapReduce框架下的時(shí)空查詢算法，實(shí)現(xiàn)對(duì)海量數(shù)據(jù)高效查詢的目標(biāo).

本文在計(jì)算文本內(nèi)容相似性時(shí)，只是使用Jaccard相似度函數(shù)評(píng)價(jià)查詢對(duì)象與數(shù)據(jù)對(duì)象之間關(guān)鍵字的匹配程度，沒有考慮文本之間的語義、詞性和文本結(jié)構(gòu)等因素，下一步的工作是考慮文本間多個(gè)因素來提高文本相似性匹配的準(zhǔn)確度.