宋雨萌，陳 默，于 戈

東北大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110169

1 引言

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

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

2 相關(guān)工作

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

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

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

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

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

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

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

3 問(wèn)題定義

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

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

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

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

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

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

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

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

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

定義1（動(dòng)態(tài)偏好值）用戶u在時(shí)間窗口內(nèi)對(duì)某興趣標(biāo)簽h的動(dòng)態(tài)偏好值I(u,h,)為：

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

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

Table 1 Example of u1's dynamic preference vector in<2018-05-01 00:00:00,2018-05-07 23:59:59>表1 用戶u1在時(shí)間窗口<2018-05-01 00:00:00,2018-05-07 23:59:59>的動(dòng)態(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ù)

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

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

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

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

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

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

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

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

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

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

4 DPG查詢

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

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

4.2 UTC-tree索引

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 DPG查詢算法

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

算法3DPG查詢算法

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

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

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

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

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

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

4.4 算法復(fù)雜度分析

Fig.5 Running example of DPG query algorithm圖5 DPG查詢算法運(yùn)行示例圖

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

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

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

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

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

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

為了獲取精確的DPG 查詢結(jié)果，DPG 查詢需要實(shí)時(shí)獲取用戶的精確位置及路網(wǎng)距離以計(jì)算DPG查詢?cè)u(píng)價(jià)函數(shù)值Rank(G,q)?，F(xiàn)在市面上已有較多的成熟的地圖開(kāi)發(fā)工具，DPG 查詢系統(tǒng)使用第三方地圖API、百度地圖API[35]。百度地圖API 可支持GPS、Wi-Fi、基站融合定位，獲取用戶的實(shí)時(shí)經(jīng)緯度位置。通過(guò)經(jīng)緯度位置，快速計(jì)算用戶之間的實(shí)時(shí)路網(wǎng)距離。圖7 為DPG 查詢系統(tǒng)使用百度地圖API 建立的uid為Michelle 的用戶uq的好友地圖。在圖7（a）中，好友地圖中uq所在位置為沒(méi)有姓名標(biāo)簽的跳動(dòng)紅色標(biāo)志點(diǎn)，圖中共有6位在uq所在位置附近的好友，以靜止紅色標(biāo)志點(diǎn)表示，紅色標(biāo)志點(diǎn)右上角為好友uid。用戶可使用鼠標(biāo)對(duì)地圖顯示范圍和精度進(jìn)行自由調(diào)節(jié)，同時(shí)可更換衛(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 索引在建立時(shí)間、生成樹(shù)空間大小、對(duì)DPG 的查詢時(shí)間、I/O代價(jià)的影響及增量更新參數(shù)α對(duì)誤差率的影響。

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

在研究?jī)煞N索引對(duì)DPG 查詢的影響中，使用20 000、40 000、60 000、80 000、100 000條簽到記錄建立UTC-tree 和TA-tree 索引進(jìn)行DPG 查詢，其中k=5，q.r=5 km，=<2010-09-01 00:00:00,2010-12-31 23:59:59>，H={“古典音樂(lè)”}，記錄查詢時(shí)間與查詢中訪問(wèn)的葉子節(jié)點(diǎn)的個(gè)數(shù)C，如圖9（a）（b）所示。在圖9（a）中，使用UTC-tree 索引的查詢時(shí)間均小于使用TA-tree 索引的查詢時(shí)間，當(dāng)|R|=100 000時(shí)，使用UTC-tree 索引的查詢時(shí)間僅為使用TA-tree的查詢時(shí)間的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）為兩種索引對(duì)查詢中訪問(wèn)葉子節(jié)點(diǎn)次數(shù)C的影響。圖中使用TA-tree索引查詢?cè)L問(wèn)葉子節(jié)點(diǎn)次數(shù)均多于UTC-tree，當(dāng)|R|=100 000 時(shí)，使用UTCtree 索引的查詢?cè)L問(wèn)葉子節(jié)點(diǎn)次數(shù)較TA-tree 減少了51%。圖9（a）（b）證明了在DPG查詢中，UTC-tree較TA-tree 過(guò)濾了更多不符合查詢條件的葉子節(jié)點(diǎn)，有效減少訪問(wèn)葉子節(jié)點(diǎn)次數(shù)，減少I(mǎi)/O代價(jià)。

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

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

5.3 DPG查詢性能分析

5.3.1 查詢半徑q.r分析

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

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

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

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

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

5.3.3 查詢興趣標(biāo)簽|H|分析

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

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

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

6 結(jié)束語(yǔ)

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

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

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