宋雨萌，陳 默，于 戈

東北大學 計算機科學與工程學院，沈陽 110169

1 引言

近幾年，成熟的定位技術(shù)與社交網(wǎng)絡相結(jié)合形成了新的地理社交網(wǎng)絡（geo-social networks，GSNs），如Foursquare、Gowalla、大眾點評等。和傳統(tǒng)的社交網(wǎng)絡相比，地理社交網(wǎng)絡引入了地理因素，用戶可以通過“簽到”向他人分享自己此刻所在的地點，在地理社交網(wǎng)絡平臺與好友分享和傳播信息[1-3]。簽到行為包含了用戶的行為趨勢、生活習慣等興趣偏好。挖掘簽到數(shù)據(jù)中用戶的興趣偏好，以進行個性化且高實用性的查詢對基于不同目的的用戶、商家或第三方而言至關(guān)重要。然而用戶的興趣偏好傾向于隨時間推移而變化。這是由于在生活中，用戶在各種社交網(wǎng)絡不斷建立新的友誼，導致社交網(wǎng)絡結(jié)構(gòu)變化。而社交網(wǎng)絡結(jié)構(gòu)的關(guān)鍵性變化致使用戶對外部事件的反應產(chǎn)生了改變[4]。Pereira 等人在文獻[5]中通過帶有地理標簽的推特數(shù)據(jù)實驗證明了在不同時間內(nèi)的用戶興趣偏好存在差異。

受時間對用戶興趣偏好影響的啟發(fā)，本文構(gòu)建了一種能夠檢測用戶動態(tài)偏好的時序地理社交網(wǎng)絡模型。在GSNs 的簽到數(shù)據(jù)中，時間是常見且必要的維度，帶有時間標簽的簽到數(shù)據(jù)反映了用戶在包含該時間戳的短時間內(nèi)的興趣偏好。因此時序地理社交網(wǎng)絡模型對用戶的社交關(guān)系信息、簽到時間標簽以及簽到位置信息等建模，并通過動態(tài)偏好值模型評估用戶的動態(tài)興趣偏好。同時，提出了時序地理社交網(wǎng)絡中基于動態(tài)偏好的組查詢（dynamic preference-based group query，DPG），搜索附近區(qū)域中在指定時間窗口內(nèi)具有特定興趣的top-k個其他具有社交關(guān)系的用戶，用于用戶發(fā)起活動或商家推廣活動。為優(yōu)化查詢算法，設計了UTC-tree（users'temporal check-in tree）索引用戶時序簽到記錄，提高用戶動態(tài)偏好值的計算速度。最后通過實驗驗證UTC-tree的有效性及DPG查詢算法的可擴展性。

2 相關(guān)工作

近年來，地理社交網(wǎng)絡的研究，如GSNs 中的查詢與推薦[6]，基于GSNs 數(shù)據(jù)的本地事件檢測[7]、線上社交關(guān)系推斷[8]、地點聚類[9]等問題引起了國內(nèi)外學者的研究熱潮，其中基于地理社交網(wǎng)絡的查詢及推薦為用戶提供了更個性化的線下社交活動服務，文獻[10-14]均為基于地理社交網(wǎng)絡的查詢與推薦研究，其目標旨在為用戶查詢符合要求的活動用戶或POI（point of interest）。在一些用于發(fā)起活動的查詢中，為了取代活動發(fā)起者手動選擇活動參與者用戶組，保證活動參與者用戶組的社交熟悉度，許多工作中也提出了多種不同類型的組查詢。文獻[15-20]是用于不同場景的組查詢研究。在基于地理社交網(wǎng)絡的研究中，大量的時空數(shù)據(jù)索引研究被用于加速不同的查詢方法，其中包括空間索引的研究、時間索引的研究等。文獻[21-31]均為可用于基于地理社交網(wǎng)絡查詢的時空數(shù)據(jù)索引研究。

下面對與本文相關(guān)的基于地理社交網(wǎng)絡的查詢與推薦研究、組查詢研究及時空數(shù)據(jù)索引研究三方面進行介紹：

（1）基于地理社交網(wǎng)絡的查詢與推薦研究。文獻[10]提出一種基于簽到記錄的無監(jiān)督時空嵌入方法，對地點、時間、用戶進行編碼，用于多種個性化推薦任務。Wang等人提出一種用于POI推薦的時序個性化模型TPM（temporal personalized model）[11]，TPM引入Topic-Region潛在變量，對用戶偏好的有序性與循環(huán)性進行建模，顯著縮小預測空間，有效緩解數(shù)據(jù)稀疏性。Lian等人提出了一種基于隱式反饋的內(nèi)容敏感協(xié)同過濾框架[12]，解決POI推薦中的新用戶冷啟動問題。以上地理社交網(wǎng)絡中的推薦模型側(cè)重于對POI 推薦的研究，并不能完全適用于DPG 查詢場景。文獻[13]提出RkGSK（reverse top-kgeo-social keyword query），考慮距離、文本和社交信息為地理標記對象查詢潛在客戶。文中提出了混合索引GIMtree 和有效的剪枝策略解決RkGSK 查詢。文獻[14]提出KNNIG（K-nearest neighbor based interest group query），查詢通過用戶歷史簽到數(shù)據(jù)提取用戶的興趣值，并考慮用戶興趣值和空間距離兩方面因素，使用網(wǎng)格索引及剪枝算法為用戶返回距離其較近并且與其有一樣興趣愛好的k個其他用戶的集合。以上兩種查詢分析用戶興趣時，并未考慮用戶的動態(tài)偏好可能導致查詢結(jié)果的偏差。DPG查詢通過用戶的簽到地點與時間分析用戶的動態(tài)偏好，保證用戶對查詢關(guān)鍵字在近期內(nèi)具有較高的興趣。且大多數(shù)基于地理社交網(wǎng)絡的查詢在考慮地理因素時使用不能精確衡量用戶之間真實距離的歐式距離，無法滿足真實的查詢需求。

（2）組查詢研究。NSG（nearest star group query）[15]檢索m個用戶的最近k個子圖，其中每個子圖中有一個用戶與其他所有用戶有社交關(guān)系。GSGQ（geosocial group query）[16]查詢具有最小的好友約束的用戶組，保證一個有凝聚力的群體。Yang 等人提出STGQ（social-temporal group query）[17]，查詢考慮了候選者的可用時間和社交關(guān)系，為用戶尋找最佳的活動時間和社交關(guān)系最親近的參與者用戶組，使用有效的剪枝技術(shù)與樞軸時間槽的思想減少運行時間。Hung 等人提出用戶社區(qū)發(fā)現(xiàn)框架，使用概率后綴樹結(jié)構(gòu)存儲用戶軌跡信息[18]，并對軌跡之間的距離使用聚類算法形成不同用戶組社區(qū)。Li 等人提出SaRG（social-aware ridesharing group query）[19]，通過考慮社交關(guān)系和空間最近鄰查詢一組乘客，由于SaRG 查詢是一個NP 難問題，文中提出一組剪枝技術(shù)與幾種增量策略減少重復計算。文獻[20]為用戶查詢一個包含查詢頂點的具有共同價值觀的空間敏感社區(qū)，保證社區(qū)內(nèi)具有高度結(jié)構(gòu)內(nèi)聚性與空間內(nèi)聚性。其中結(jié)構(gòu)內(nèi)聚性主要衡量社區(qū)的社交關(guān)系，空間內(nèi)聚性主要衡量社區(qū)地理位置的緊密程度。提出的DPG查詢更關(guān)注組成員的共同興趣偏好而不是他們的社交關(guān)系與地理距離。以上組查詢不完全符合DPG 查詢背景，無法評價用戶組動態(tài)偏好和用戶組中空間路網(wǎng)距離關(guān)系。

綜上所述，本文提出的DPG查詢其優(yōu)勢在于，不僅考慮空間及社交關(guān)系的約束，同時考慮用戶的動態(tài)偏好，獲取較好的查詢效果。在空間上考慮用戶之間的路網(wǎng)距離，保證更有實用價值的查詢工作。在查詢中使用剪枝算法提高查詢效率。

（3）時空數(shù)據(jù)索引研究。在數(shù)據(jù)索引方面，許多空間索引可用于最近鄰查詢，但它們只關(guān)注空間維度，無法處理時間維度，不能用于DPG查詢，例如，網(wǎng)格索引、R-tree索引、四叉樹索引等。網(wǎng)格索引[21-22]是將空間劃分成相同大小或不同大小的網(wǎng)格，查詢時首先計算查詢區(qū)域覆蓋的網(wǎng)格單元，再在具體網(wǎng)格中查找對象。網(wǎng)格索引易于實現(xiàn)，可以快速查找符合條件的對象。R-tree 索引[23]使用最小外接矩陣（minimum bounding rectangle,MBR）作為存儲節(jié)點，中間層節(jié)點的MBR覆蓋所有孩子節(jié)點的MBR，實體存放在葉子節(jié)點的MBR中。R-tree索引能夠有效提高存儲和查詢的效率。四叉樹索引[24]是一種基于空間劃分的索引結(jié)構(gòu)。四叉樹索引將整個空間區(qū)域遞歸劃分成不同層次的樹結(jié)構(gòu)，每個子空間區(qū)域劃分為大小相同的四個區(qū)域。當數(shù)據(jù)均勻時，四叉樹索引具有較高的空間數(shù)據(jù)插入和查詢效率。一些相關(guān)的索引也不能適應DPG 查詢，例如B-tree（selftunable spatio-temporal B+-tree）[25]、RUM-tree（R-trees with update memos）[26]、TPR*-tree（time parameterized R*-tree）[27]等時空索引主要關(guān)注于對可預測軌跡的移動對象的索引，并不能應用于DPG 查詢。SWST(sliding window spatio-temporal index)[28]和PIST（practical index for spatio-temporal）[29]可用于索引離散移動的目標，但不能有效索引空間中的文本信息。aRB-tree[30]由R-tree和B-tree組合而成，每一個R-tree中的區(qū)域指向一個B-tree，B-tree 中存儲每一個時間標簽下在該區(qū)域的歷史集合。Tao等人在文獻[31]基礎上提出sketch索引，解決了aRB-tree不能重復計數(shù)的問題，即某對象在不同時間標簽訪問同一區(qū)域。但由于B 樹不能索引時間間隔，因此無法對以上索引進行時間間隔的調(diào)整，若在等長的時間間隔下，僅根據(jù)空間范圍進行索引不能有效加速DPG查詢。

綜上，已有的相關(guān)索引不適用于本文提出的DPG 查詢。為此，本文提出新的索引UTC-tree 加速DPG 查詢，其優(yōu)勢在于同時考慮時間、動態(tài)偏好、用戶三種約束，使用B+樹對時間維度進行索引，使用Bloom計數(shù)過濾器對用戶id與興趣標簽進行過濾，在查詢過程中可對UTC-tree 進行快速剪枝，有效提高動態(tài)偏好值的計算速度。

3 問題定義

3.1 時序地理社交網(wǎng)絡模型

簽到數(shù)據(jù)中，簽到地點與用戶興趣偏好相關(guān)，簽到時間標簽則反映了用戶偏好的時序性，而現(xiàn)有的地理社交網(wǎng)絡查詢研究中[10-14]，地理社交網(wǎng)絡模型并未包括用戶的簽到時間信息，無法評估用戶的動態(tài)偏好。因此，本文構(gòu)建了時序地理社交網(wǎng)絡模型用于用戶的動態(tài)偏好研究。時序地理社交網(wǎng)絡為一無向圖，用三元組G(U,P,E)表示，其中：

（1）U={u1,u2,…,un}為用戶節(jié)點集合。

（2）P={p1,p2,…,pn}為興趣點節(jié)點集合。每個興趣點pi與一個興趣標簽集合相關(guān)聯(lián)，表示在pi簽到的用戶具有中的興趣偏好，例如在羽毛球館簽到的人則對羽毛球感興趣偏好。

（3）E=EUU∪EUP是網(wǎng)絡中所有邊的集合。EUU={(ui,uj)|ui∈U,uj∈U}表示用戶-用戶邊集合，即該邊連接的兩個節(jié)點ui、uj是好友關(guān)系。EUP={(ui,pj)|ui∈U,pj∈P}表示用戶-興趣點邊集合，即用戶ui在興趣點pj進行簽到行為。每個用戶-興趣點邊e(ui,pj)與一個時間標簽集合Ti-j相關(guān)聯(lián)，表示用戶ui在興趣點pj的簽到時間，其中是ui在pj點第k次簽到的時間戳（精確到秒），對于任意

圖1是一個時序地理社交網(wǎng)絡示意圖，其中“●”為用戶，“▲”為興趣點，興趣點附近的矩形框中為興趣點相關(guān)的興趣標簽集合，實線表示用戶之間的社交關(guān)系，虛線表示用戶與興趣點的簽到關(guān)系，虛線中的時間標簽集合表示用戶于相應興趣點的簽到時間標簽集合。由圖可知，用戶u1與u2為好友關(guān)系，且都于興趣點p1簽到，p1與興趣標簽h1、h2、h3相關(guān)。u1分別于在p1進行過4次簽到。用戶u7與圖中任何人都不是好友，他分別于在p3簽到3次，于在p4簽到1次。

Fig.1 Example of temporal geo-social network圖1 時序地理社交網(wǎng)絡示意圖

3.2 動態(tài)偏好值模型

設U為用戶集合，其中每個用戶u(u∈U)為一個二元組，用表示。其中，id為用戶的唯一身份標識，如該用戶在某社交網(wǎng)絡中的用戶名，為用戶的動態(tài)偏好向量，記錄了該用戶在時間窗口內(nèi)對不同興趣標簽h的動態(tài)偏好值大小，ts為起始時間，te為終止時間，ts

定義1（動態(tài)偏好值）用戶u在時間窗口內(nèi)對某興趣標簽h的動態(tài)偏好值I(u,h,)為：

其中，Du表示用戶u在時間窗口內(nèi)（近一段時間內(nèi)）所有簽到過的位置點集合，Dh表示所有關(guān)聯(lián)興趣標簽h的位置點集合。函數(shù)N(u,l,)統(tǒng)計用戶u在時間窗口內(nèi)于位置點l處簽到的次數(shù)。

表1 為用戶u1在時間窗口<2018-05-01 00:00:00,2018-05-07 23:59:59>的動態(tài)偏好向量。動態(tài)偏好值越大表示用戶近期對該興趣標簽越感興趣。如表1所示，在過去一周內(nèi)用戶u1對“運動”比“讀書”更感興趣。

Table 1 Example of u1's dynamic preference vector in<2018-05-01 00:00:00,2018-05-07 23:59:59>表1 用戶u1在時間窗口<2018-05-01 00:00:00,2018-05-07 23:59:59>的動態(tài)偏好向量

3.3 DPG查詢定義

Fig.2 Location of u1and surrounding users圖2 u1及周邊用戶位置圖

Table 2 User data of u1's friends表2 u1好友的用戶數(shù)據(jù)

基于時序地理社交網(wǎng)絡模型及動態(tài)偏好值模型，提出DPG 查詢。DPG 查詢?yōu)橛脩粼诟浇鼌^(qū)域內(nèi)搜索當前距離最近且近期對某興趣標簽集合的動態(tài)偏好值最高的社交好友用戶組。圖2 和表2 為DPG查詢的一個示例。圖2為用戶u1及周邊用戶位置圖，其中“★”為用戶u1所在位置，“▲”為u1好友所在位置，“●”為非u1好友所在位置。u1發(fā)起查詢，查找3名好友共同打羽毛球。表2為u1好友當前距u1的距離，以及最近一個月、三個月、半年、一年內(nèi)對羽毛球的偏好度。其中A 為高偏好度，B 為中偏好度，C 為低偏好度。偏好度即用戶對某興趣標簽的熱衷程度，若某用戶在一時間窗口內(nèi)多次參加同一活動，則認為用戶對該興趣有高偏好度。若u1的查詢距離為1 500 m 內(nèi)，當動態(tài)偏好查詢時間窗口為一個月時，DPG 查詢將會返回結(jié)果集{u2,u5,u8}，該結(jié)果集較其他用戶集而言距用戶u1較近且在最近一個月內(nèi)對羽毛球偏好度較高，將更適合參與該次活動。當動態(tài)偏好查詢時間窗口為三個月時，由于u5在三個月內(nèi)對羽毛球偏好度很低，而距u1較遠的u4在三個月內(nèi)對羽毛球具有中偏好度，故DPG 查詢的查詢結(jié)果集為{u2,u4,u8}。

定義2（動態(tài)偏好評分函數(shù)）動態(tài)偏好評分函數(shù)I*(u,q.H,)評價候選用戶u在時間窗口內(nèi)對DPG查詢q的興趣標簽集合q.H的符合程度。

|q.H|為興趣標簽集合中的興趣標簽個數(shù)，Ihmax為候選用戶在時間窗口內(nèi)對查詢興趣標簽h的前k個動態(tài)偏好值之和。

假設DPG 查詢q1的興趣標簽集合為q1.H1={“運動”}，DPG 查詢q2的興趣標簽集合為q2.H2={“音樂”}，q1、q2的查詢時間窗口均為<2018-05-01 00:00:00,2018-05-07 23:59:59>，且I“音樂”max=I“運動”max，在表1 中，用戶u1在時間窗口內(nèi)對q1.H1的動態(tài)偏好評分高于對q2.H2的動態(tài)偏好評分。

為了真實評價用戶之間的距離，查詢距用戶最近的k個其他好友，DPG查詢使用路網(wǎng)距離計算用戶間距離。

定義3（路網(wǎng)距離）路網(wǎng)由一帶權(quán)無向圖G=(V,E,W)表示，其中V為路網(wǎng)中所有節(jié)點的集合，E為路網(wǎng)中兩個節(jié)點之間的道路e的集合，W為e的權(quán)值集合。每條道路e的權(quán)值w表示兩個相鄰節(jié)點之間的路網(wǎng)距離。

若某用戶u位于邊e=(vi,vj)上，u與節(jié)點vi之間的長度為lu，則u在路網(wǎng)上的位置表示為，其中l(wèi)u∈[0,w(e)]，i

定義4（DPG 查詢評價函數(shù)）Rank(G,q)評價候選用戶集合G(|G|=k)對DPG查詢q的符合程度，該函數(shù)考慮了動態(tài)偏好值與距離兩方面影響因素。

Dmin為當前距查詢發(fā)起點q.l最近的k個用戶到q.l的路網(wǎng)距離和，∑u∈Gdist(u,q.l)為當前檢驗的用戶集合G中用戶到q.l的路網(wǎng)距離和，dist(u,q.l)為用戶u的位置點u.l與查詢發(fā)起點q.l之間的路網(wǎng)距離，q.H為興趣標簽集合，∑u∈GI*(u,q.H,)為G中的所有用戶的動態(tài)偏好評分之和。參數(shù)λ∈[0,1]用來調(diào)整距離和動態(tài)偏好評分所占比重。

定義5（基于動態(tài)偏好的組查詢，DPG）給定查詢用戶q.u、查詢興趣標簽集合q.H、查詢點q.l、查詢范圍半徑q.r、查詢時間窗口、查詢用戶數(shù)k，DPG 查詢返回Rank值（式（3））最高的用戶集

4 DPG查詢

4.1 DPG查詢系統(tǒng)框架

DPG 查詢系統(tǒng)的框架如圖3 所示，包括用戶界面、用戶模塊、好友模塊、簽到模塊、DPG 查詢模塊5個功能模塊以及數(shù)據(jù)庫。DPG查詢模塊實現(xiàn)DPG查詢算法。DPG查詢算法使用用戶時序簽到記錄索引UTC-tree計算用戶動態(tài)偏好值，避免大量簽到記錄的遍歷，再由剪枝算法過濾距離或動態(tài)偏好值不符合要求的用戶，生成結(jié)果用戶集。UTC-tree由簽到記錄及POI數(shù)據(jù)生成，根據(jù)興趣標簽及時間窗口篩選簽到記錄，加速用戶動態(tài)偏好計算，優(yōu)化DPG 查詢速度。用戶實時定位數(shù)據(jù)為DPG查詢提供準確的用戶經(jīng)緯度位置，聯(lián)合路網(wǎng)數(shù)據(jù)可計算用戶間的路網(wǎng)距離。用戶好友關(guān)系數(shù)據(jù)存儲具有好友關(guān)系的用戶，由好友模塊進行維護，用于滿足DPG查詢的好友約束。

4.2 UTC-tree索引

4.2.1 UTC-tree索引構(gòu)建

DPG 查詢對簽到記錄與POI 數(shù)據(jù)建立UTC-tree索引，UTC-tree索引可以避免遍歷所有簽到記錄而進行動態(tài)偏好評分計算，加速DPG 查詢。UTC-tree 索引受TA-tree（temporal activity tree）[32]的啟發(fā)，TA-tree是一嵌入Bloom 過濾器的B+樹索引，葉子節(jié)點由數(shù)據(jù)項組成，其中ui為用戶身份標識，tp為ui參與活動ak的時間標簽，為描述ak的關(guān)鍵字集合。B+樹以tp為關(guān)鍵字構(gòu)建，內(nèi)部節(jié)點中每個指針嵌入一Bloom過濾器，Bloom過濾器由當前指針指向的葉子節(jié)點中每個數(shù)據(jù)項的生成。由于TAtree中的Bloom過濾器只通過過濾關(guān)鍵字加速查詢，無法對用戶id 進行篩選，同時普通的Bloom 過濾器無法刪除數(shù)據(jù)，無法進行索引的動態(tài)維護，故不適用于DPG查詢。

Fig.3 DPG query system architecture圖3 DPG查詢系統(tǒng)框架

圖4是一個UTC-tree索引示例。與TA-tree索引相似，UTC-tree也是一種B+樹，但在內(nèi)部節(jié)點的每個指針中嵌入Bloom 計數(shù)過濾器。使用Bloom 計數(shù)過濾器替代Bloom 過濾器的優(yōu)勢在于前者能對過濾器中元素進行刪除，而后者不能。UTC-tree葉子節(jié)點中的數(shù)據(jù)項為簽到記錄三元組，uid為簽到用戶u的身份標識，t為簽到時間，H為簽到地點相關(guān)的興趣標簽集。B+樹以簽到時間t為關(guān)鍵字建立，以加速查詢在時間窗口內(nèi)的簽到記錄。Bloom計數(shù)過濾器由當前指針指向的子樹中所有葉子節(jié)點中數(shù)據(jù)項的H及uid生成。查詢時根據(jù)Bloom計數(shù)過濾器對UTC-tree中數(shù)據(jù)項不存在h和uid的分支進行剪枝，以減少查詢數(shù)據(jù)量。

Fig.4 Example of UTC-tree index圖4 UTC-tree索引示例

在UTC-tree中，Bloom計數(shù)過濾器的哈希函數(shù)的選擇會影響過濾的錯誤率[33]，當哈希函數(shù)個數(shù)k=(ln 2)×(m/n)時，錯誤率最小，其中m為位數(shù)組的大小，n為輸入元素個數(shù)。由于UTC-tree 中簽到記錄條數(shù)隨時間增加而增加，為保證Bloom計數(shù)過濾器的有效性，DPG 查詢對UTC-tree 實行增量更新策略。在建立UTC-tree 時設Bloom計數(shù)過濾器輸入元素個數(shù)為n*，n*=|R|+α|R|，α∈[0,1]，其中|R|為當前簽到記錄條數(shù)，α為可新增簽到記錄條數(shù)與全部簽到記錄條數(shù)之比。當新增簽到記錄時，使用變量count對新增簽到記錄條數(shù)進行計數(shù)，若count≤α|R|，則直接將記錄加入UTC-tree，否則重新構(gòu)建UTC-tree。當n*-|R|較大時，將減少整體更新次數(shù)，但會犧牲過濾的準確性。若n*-|R|較小，可以保證過濾時具有較低的錯誤率，但需要在短時間內(nèi)整體更新多次。

4.2.2 基于UTC-tree的優(yōu)化算法

下面給出UTC-tree 的優(yōu)化查詢過程，分別采用UTC-tree 葉子節(jié)點查詢算法和UTC-tree 動態(tài)偏好評分算法實現(xiàn)。UTC-tree 葉子節(jié)點查詢算法用于查詢UTC-tree 節(jié)點node的子樹中包含特定的簽到記錄{|uid∈q.U,t∈(ts,te),H∩Hu≠?}的葉子節(jié)點集合。如算法1 所示，若node為內(nèi)部節(jié)點，根據(jù)node中關(guān)鍵字t篩選符合時間窗口的Bloom 計數(shù)過濾器集合（第3行），其次通過Bloom計數(shù)過濾器篩選含有查詢興趣標簽與候選好友用戶的子節(jié)點，并迭代執(zhí)行UTC-tree葉子節(jié)點查詢算法（第4～7行）。若node為葉子節(jié)點，則將該節(jié)點加入結(jié)果集G（第8～9行）。

算法1UTC-tree 葉子節(jié)點查詢算法LeafNode Query(node,ts,te,q.H,q.U)

輸入：UTC-tree的節(jié)點node，時間窗口起始時間ts，時間窗口終止時間te，興趣標簽集合q.H，待選好友用戶集合q.U。

輸出：node節(jié)點子樹中包含簽到記錄{|uid∈q.U,t∈(ts,te),H∩Hu≠?}的葉子節(jié)點集合G。

UTC-tree 動態(tài)偏好評分算法能夠快速查詢用戶u在時間窗口中的簽到記錄并對查詢興趣標簽集合q.H相關(guān)的簽到記錄計數(shù)，利用式（1）、式（2）統(tǒng)計u的動態(tài)偏好評分Istar。UTC-tree動態(tài)偏好評分算法如算法2 所示。算法首先初始化變量Ntotal用以對u的簽到記錄總數(shù)計數(shù)，初始化數(shù)組N[|q.H|]用以對u在關(guān)于q.H的簽到記錄總數(shù)計數(shù)，初始化棧S并將UTC-tree 根節(jié)點root入棧以遍歷UTC-tree（第1～2 行）。當S不為空時，若出棧節(jié)點npop為內(nèi)部節(jié)點，根據(jù)篩選符合時間要求的子節(jié)點指針集合，并通過子節(jié)點指針中的Bloom計數(shù)過濾器查詢含有用戶u的子節(jié)點，將相應子節(jié)點入棧S（第5～9行）；若出棧節(jié)點npop為葉子節(jié)點，Ntotal對用戶u的簽到記錄計數(shù)，若某條簽到記錄相關(guān)的興趣標簽集合Hu與q.H的交集不為空，則將相應興趣標簽的計數(shù)數(shù)組N[|q.H|]加1（第11～14 行）。最后將Ntotal、N[|q.H|]及候選用戶中在時間窗口內(nèi)對查詢興趣標簽h的前k個動態(tài)偏好值之和Ihmax代入式（1）、式（2）計算Istar（第16～17行）。

算法2UTC-tree 動態(tài)偏好評分算法getIstar(u,q.H,ts,te,root,Ihmax)

輸入：用戶u，興趣標簽集合q.H，時間窗口起始時間ts，時間窗口終止時間te，UTC-tree 根節(jié)點root，候選用戶在時間窗口內(nèi)對查詢興趣標簽h的前k個動態(tài)偏好值之和Ihmax。

輸出：用戶u的動態(tài)偏好評分Istar。

4.3 DPG查詢算法

DPG查詢使用UTC-tree加速計算用戶動態(tài)偏好評分，快速過濾候選用戶，并采用剪枝策略對候選用戶進行剪枝，加快查詢速度。算法偽代碼如算法3所示。算法首先使用UTC-tree葉子節(jié)點查詢算法在時間窗口內(nèi)搜索包含q.H中任意興趣標簽h和U中用戶身份標簽uid的葉子節(jié)點，將符合距離、偏好要求的用戶按照距uq的路網(wǎng)距離升序加入隊列queue（第2～6行）。其次，使用queue隊首k個用戶初始化結(jié)果集G，計算G的DPG 查詢函數(shù)值初始化Rankmax（第7～13 行）。最后，將queue中剩余用戶依次出隊替換G，使替換后DPG評價函數(shù)值增幅最大，根據(jù)未能使DPG 評價函數(shù)增大的用戶動態(tài)偏好值Iudeq對queue中其余候選用戶進行剪枝。由于queue中其余候選用戶按照路網(wǎng)距離升序排列，若queue中用戶的動態(tài)偏好評分小于Iudeq，根據(jù)式（3），該候選用戶替換G中任何用戶都不能使DPG查詢評分函數(shù)值增加，故可直接將其從queue中剪枝（第14～19行）。

算法3DPG查詢算法

輸入：候選好友用戶集合U，查詢興趣標簽集合q.H，查詢點q.l，查詢范圍半徑q.r，UTC-tree根節(jié)點root，查詢用戶數(shù)k，起始時間ts，終止時間te。

輸出：結(jié)果集G。

DPG查詢算法示例圖5是一個DPG查詢算法的運行示意圖。查詢q的查詢中心為q.l，查詢?nèi)藬?shù)k=2，查詢興趣標簽集合H={“羽毛球”}，時間窗口=<2018-05-01 00:00:00,2018-05-07 23:59:59>，距離q.l最近的k個用戶距離和為1 500，λ=0.5，候選用戶隊列queue={u1,u2,u3,u4,u5}，各用戶距q.l的路網(wǎng)距離與動態(tài)偏好評分如表3所示。

Table 3 Example of DPG query algorithm表3 DPG查詢算法示例

如圖5（a）所示，首先u1、u2出隊，初始結(jié)果集G={u1,u2}，結(jié)果集G的DPG查詢評價函數(shù)值為Rankmax=0.594。在圖5（b）中，u3出隊，依次替換G={u1,u2}中的用戶。當u3替換u1時，=0.656；當u3替換u2時，。兩次替換中最大的，則u3替換u2，更新G={u1,u3}，Rankmax=0.801。在圖5（c）中u4出隊，依次替換u1、u3，故不更新G。由于I*(u5,q,H,))，故將u5剪枝移出queue。queue為空，返回查詢結(jié)果集{u1,u3}，如圖5（d）所示。

為更好地滿足用戶的查詢需求，DPG 查詢算法提供增量更新算法，以保證在滑動的查詢時間窗口中可以動態(tài)地根據(jù)其他用戶新增和刪除的簽到記錄更新DPG查詢結(jié)果集。增量更新算法首先對在新時間窗口中新增簽到記錄的用戶集U*中的每個用戶u*計算簽到記錄絕對增量A(u*)，A(u*)=|W(u*)′-W(u*)|-|W(u*)-W(u*)′|，若A(u*)>0 則將u*加入增量候選集合U′。其中W(u*)為原時間窗口中的用戶u*在含有DPG 查詢興趣標簽集合q.H的POI 點簽到的簽到記錄集合，W(u*)′為新時間窗口中用戶u*在含有DPG查詢興趣標簽集合q.H的POI 點簽到的簽到記錄集合，|W|為W集合中簽到記錄的條數(shù)。對于每個u′∈U′，根據(jù)距q.l的路網(wǎng)距離升序加入增量候選隊列queue′。將queue′中的用戶依次出隊，執(zhí)行算法DPG查詢算法第14至19行，通過相同的剪枝算法計算用戶是否能替換結(jié)果集G中的用戶，新的用戶結(jié)果集G′即是增量更新的DPG查詢結(jié)果。

4.4 算法復雜度分析

Fig.5 Running example of DPG query algorithm圖5 DPG查詢算法運行示例圖

本文提出的DPG查詢算法的時間復雜度由動態(tài)偏好評分計算開銷和選擇計算開銷兩部分組成。動態(tài)偏好評分計算開銷是由于通過篩選簽到記錄計算動態(tài)偏好評分引起的，選擇計算開銷是由計算DPG查詢評價函數(shù)引起的。假設n為全部候選用戶，α為查詢范圍內(nèi)需要計算動態(tài)偏好評分的用戶占全部候選用戶的比例，m為平均每次查詢遍歷UTC-tree的葉子節(jié)點數(shù)，p為每個葉子節(jié)點索引的簽到記錄數(shù)，k為查詢?nèi)藬?shù)，則DPG查詢算法的動態(tài)偏好評分計算開銷為O(αn×mp)，選擇計算開銷為O(k×αn)。對于增量更新算法，假設β為簽到記錄絕對增量A(u)大于0 的用戶占全部候選用戶的比例，則增量更新。算法的動態(tài)偏好評分開銷為O(βn×mp)，選擇計算開銷為O(k×βn)。由于增量更新算法選擇簽到記錄絕對增量大于0的用戶進行更新計算，故β≤α，可見增量更新算法在動態(tài)偏好評分計算和選擇計算兩方面較重新計算查詢結(jié)果的更新方法節(jié)省了開銷。

5 實驗結(jié)果與分析

實驗環(huán)境為PC 機，操作系統(tǒng)為64 位Microsoft Windows 7 旗艦版SP1，使用MyEclipse 作為開發(fā)工具，使用java編寫完成。實驗數(shù)據(jù)使用來自地理社交網(wǎng)站Gowalla在2009年2月到2010年10月用戶簽到及好友關(guān)系的真實數(shù)據(jù)集[34]。數(shù)據(jù)集中包括195 485個用戶在2009 年1 月至2010 年12 月之間產(chǎn)生的6 442 887條簽到信息，簽到記錄包括用戶id、簽到時間、簽到經(jīng)緯度信息，同時數(shù)據(jù)集中還包含1 900 654條以上用戶的好友關(guān)系信息、好友關(guān)系信息記錄用戶與其好友的id。

在實驗中，用戶簽到記錄相關(guān)的興趣標簽信息為模擬產(chǎn)生，為滿足用戶的興趣分散性，對每條簽到記錄生成1～3個興趣標簽。在以下實驗中，每一組實驗查詢100次，最終求出平均值作為實驗結(jié)果。

5.1 DPG查詢系統(tǒng)實現(xiàn)

根據(jù)DPG 查詢算法實現(xiàn)了一個DPG 查詢系統(tǒng)。DPG 查詢系統(tǒng)由jsp 完成界面設計，java 編寫系統(tǒng)內(nèi)核模塊，使用mySQL1.5 數(shù)據(jù)庫，Strut2 框架，Tomcat8 服務器。DPG 查詢系統(tǒng)包括登錄、立即簽到、發(fā)起活動、好友中心、活動中心等功能，提供用戶個人信息維護、社交關(guān)系維護、活動數(shù)據(jù)維護、DPG查詢等功能。DPG查詢系統(tǒng)主界面如圖6所示。

為了獲取精確的DPG 查詢結(jié)果，DPG 查詢需要實時獲取用戶的精確位置及路網(wǎng)距離以計算DPG查詢評價函數(shù)值Rank(G,q)?，F(xiàn)在市面上已有較多的成熟的地圖開發(fā)工具，DPG 查詢系統(tǒng)使用第三方地圖API、百度地圖API[35]。百度地圖API 可支持GPS、Wi-Fi、基站融合定位，獲取用戶的實時經(jīng)緯度位置。通過經(jīng)緯度位置，快速計算用戶之間的實時路網(wǎng)距離。圖7 為DPG 查詢系統(tǒng)使用百度地圖API 建立的uid為Michelle 的用戶uq的好友地圖。在圖7（a）中，好友地圖中uq所在位置為沒有姓名標簽的跳動紅色標志點，圖中共有6位在uq所在位置附近的好友，以靜止紅色標志點表示，紅色標志點右上角為好友uid。用戶可使用鼠標對地圖顯示范圍和精度進行自由調(diào)節(jié)，同時可更換衛(wèi)星及三維地圖。圖7（b）為uq與Lisa 的路網(wǎng)距離顯示。淡綠色虛線為uq與好友Lisa所在位置之間的路網(wǎng)路線，信息框中為兩人的路網(wǎng)距離。

Fig.6 Main interface of DPG query system圖6 DPG查詢系統(tǒng)主界面

Fig.7 Friends map圖7 好友地圖

5.2 UTC-tree性能分析

本節(jié)將研究UTC-tree 索引與TA-tree 索引在建立時間、生成樹空間大小、對DPG 的查詢時間、I/O代價的影響及增量更新參數(shù)α對誤差率的影響。

對于索引建立方面，使用兩種索引對簽到記錄條數(shù)|R|為20 000、40 000、60 000、80 000、100 000時分別生成UTC-tree 索引以及TA-tree 索引，記錄建立時間與生成樹空間大小，如圖8（a）（b）所示。隨著簽到記錄條數(shù)的增加，TA-tree 與UTC-tree 的建立時間和生成樹空間大小呈線性增加。由于UTC-tree 中的Bloom 計數(shù)過濾器中較TA-tree 還包含了用戶身份表示的索引信息，故在建立時間上與生成樹空間大小上UTC-tree較TA-tree略有增加，但都不超過TA-tree的1/3。

在研究兩種索引對DPG 查詢的影響中，使用20 000、40 000、60 000、80 000、100 000條簽到記錄建立UTC-tree 和TA-tree 索引進行DPG 查詢，其中k=5，q.r=5 km，=<2010-09-01 00:00:00,2010-12-31 23:59:59>，H={“古典音樂”}，記錄查詢時間與查詢中訪問的葉子節(jié)點的個數(shù)C，如圖9（a）（b）所示。在圖9（a）中，使用UTC-tree 索引的查詢時間均小于使用TA-tree 索引的查詢時間，當|R|=100 000時，使用UTC-tree 索引的查詢時間僅為使用TA-tree的查詢時間的1/5。

Fig.8 Effect of UTC-tree and TA-tree indexes on establishment圖8 UTC-tree與TA-tree索引在建立方面的影響

Fig.9 Effect of UTC-tree and TA-tree on DPG group query圖9 UTC-tree與TA-tree索引在DPG查詢方面的影響

圖9（b）為兩種索引對查詢中訪問葉子節(jié)點次數(shù)C的影響。圖中使用TA-tree索引查詢訪問葉子節(jié)點次數(shù)均多于UTC-tree，當|R|=100 000 時，使用UTCtree 索引的查詢訪問葉子節(jié)點次數(shù)較TA-tree 減少了51%。圖9（a）（b）證明了在DPG查詢中，UTC-tree較TA-tree 過濾了更多不符合查詢條件的葉子節(jié)點，有效減少訪問葉子節(jié)點次數(shù)，減少I/O代價。

對于UTC-tree 的增量更新方面，α對Bloom 計數(shù)過濾器的誤差率E的影響如圖10 所示，其中|R|為簽到記錄條數(shù)。隨著α增加，誤差率將逐漸增大。當α>0.5 時，誤差率幾乎全部超過50%。在實際應用中，可按照需要調(diào)節(jié)α，并選取適當?shù)奈粩?shù)組位數(shù)，可保證Bloom計數(shù)過濾器的準確性。

Fig.10 Effect of α on error rate of Bloom counting filter圖10 α 對Bloom計數(shù)過濾器誤差率的影響

5.3 DPG查詢性能分析

5.3.1 查詢半徑q.r分析

本節(jié)將討論查詢范圍q.r對查詢時間和查詢中訪問的葉子節(jié)點的個數(shù)C的影響。在5.3 節(jié)的實驗中，DPG 查詢均使用由200 000 條簽到記錄生成的UTC-tree。如圖11（a）所示，在用戶好友人數(shù)|U|為100、300、500條件下，隨著q.r由1 km增加至10 km，查詢時間均未超過0.8 s。如圖11（b）所示，隨著查詢半徑增長，由于加入查詢隊列queue的用戶數(shù)增加，查詢中訪問葉子節(jié)點次數(shù)C不斷增長，當q.r增長為原來的10 倍時，C不超過原來的4 倍。實驗結(jié)果表示DPG查詢算法對q.r具有良好的擴展性。

5.3.2 查詢用戶數(shù)k分析

圖12（a）（b）測量了不同的k（取值范圍為5 至25）對查詢的影響。如圖12（a）所示，DPG 查詢對不同的k具有均較低的查詢時間。對于k為5至15時，查詢時間低于0.5 s，這是因為當k較小時，DPG查詢算法的結(jié)果集G中元素個數(shù)首次達到k后，queue中待選用戶較多，DPG 查詢算法中的剪枝方法能快速有效地剪除queue中多余的候選用戶。而當k取值大于15 時，結(jié)果集G中元素個數(shù)首次達到k后，queue中只留有較少的待選用戶，降低了剪枝的可能性與有效性，故延長了查詢時間。k的增加也會引起C的增長。如圖12（b）所示，k每增加5 人，C增長率為31%～53%。這是因為當k增大時，算法遍歷更多用戶動態(tài)偏好信息以滿足查詢?nèi)藬?shù)的需求。圖12（a）（b）表明隨著k的增長，查詢時間和空間開銷依然能基本滿足實際應用。

Fig.11 Influnce of q.r圖11 q.r的影響

Fig.12 Influence of k圖12 k的影響

5.3.3 查詢興趣標簽|H|分析

圖13（a）給出了|H|對查詢時間的影響。隨著|H|由1 增長至5 時，查詢時間小幅增加，平均增長小于0.5 s。圖13（b）給出|H|對C的影響。實驗顯示，C隨|H|的增長較為平緩。查詢時間和空間開銷的增長是由于查詢興趣標簽集合中的興趣標簽數(shù)越多，用戶的動態(tài)偏好評分越低，導致DPG 查詢算法在剪枝操作中最低動態(tài)偏好評分降低，影響剪枝算法的效率。兩實驗證明了DPG 查詢算法對|H|具有良好的擴展性。

5.3.4 時間窗口參數(shù)分析

圖14研究了時間窗口大小對查詢時間及C的影響。如圖14（a）所示，在不同大小的時間窗口Δt中，DPG 查詢算法能快速地完成查詢工作，且隨著時間窗口的增加，查詢時間曲線增長平緩，增幅小于0.5 s。圖14（b）為Δt對C影響，隨著Δt由30 天增長至360天，C緩慢增長。Δt直接影響訪問UTC-tree時通過時間關(guān)鍵字t查詢的葉子節(jié)點個數(shù)，故查詢時間和空間開銷都有所增加。實驗表明，DPG 查詢算法可以滿足在不同大小的時間窗口Δt下的DPG查詢。

6 結(jié)束語

Fig.13 Influnce of|H|圖13 |H|的影響

Fig.14 Influence of Δt圖14 Δt 的影響

本文基于當今非常熱門的地理社交網(wǎng)絡，對用戶好友關(guān)系、位置關(guān)系、動態(tài)偏好進行建模，構(gòu)建了一個時序地理社交網(wǎng)絡模型，并提出可滿足社交關(guān)系-空間-動態(tài)偏好三重關(guān)系的基于動態(tài)偏好的組查詢，DPG 查詢。用戶可通過DPG 查詢搜索附近區(qū)域內(nèi)近期具有特定興趣和社交關(guān)系的k個其他用戶。同時，實現(xiàn)了交互良好的DPG 查詢系統(tǒng)并通過實驗驗證了查詢算法的有效性、可靠性與可擴展性。DPG查詢可用于地理社交平臺上的組類活動的構(gòu)建和維護，提高用戶社交活動的多樣性和高效性。未來研究工作將對該類地理社交應用進行更多的查詢語義挖掘，對用戶畫像進行更詳盡的描述，同時將進一步研究該類查詢的高效增量維護算法。