[發(fā)明專利]一種路網(wǎng)下地理社交關(guān)鍵字反最近鄰查詢處理方法

有效

• 申請?zhí)枺?/td>: 201710244072.4
• 申請日: 2017-04-14
• 公開（公告）號: CN107145526B
• 公開（公告）日: 2020-06-05
• 發(fā)明（設(shè)計）人: 高云君;趙靖文;陳剛
• 申請（專利權(quán)）人: 浙江大學(xué)
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/909
• 代理公司: 杭州求是專利事務(wù)所有限公司 33200
• 代理人: 邱啟旺

本發(fā)明公開了一種路網(wǎng)下地理社交關(guān)鍵字反最近鄰查詢處理方法，利用GIM樹對空間路網(wǎng)，文本，社交數(shù)據(jù)進(jìn)行存儲，并利用分支界限方法遍歷索引；在遍歷索引時本發(fā)明首先計算索引節(jié)點的最小相似性計數(shù)表與最大相似性計數(shù)表，而后利用上述最小相似性計數(shù)表和最大相似性計數(shù)表進(jìn)行剪枝，并利用過濾、精煉算法以加速查詢執(zhí)行。本發(fā)明結(jié)合了空間數(shù)據(jù)庫的現(xiàn)有技術(shù)，降低了地理社交文本相似性計算次數(shù)，從而提高了查詢性能。

技術(shù)領(lǐng)域

本發(fā)明涉及空間數(shù)據(jù)庫的索引與查詢技術(shù)，是一種用于處理路網(wǎng)下地理社交關(guān)鍵字反最近鄰查詢的方法。

背景技術(shù)

空間數(shù)據(jù)是指地理信息系統(tǒng)在計算機物理存儲介質(zhì)上存儲的與應(yīng)用相關(guān)的地理空間數(shù)據(jù)的總和，其目的是為了存儲、管理和檢索各種地理空間數(shù)據(jù)。其中，路網(wǎng)空間數(shù)據(jù)作為空間數(shù)據(jù)庫的重要組成部分，得到了越來越多的關(guān)注。為了快速、有效地訪問路網(wǎng)空間數(shù)據(jù)，專家學(xué)者們提出了許多路網(wǎng)空間數(shù)據(jù)索引方法。目前，G樹索引方法是最有效的路網(wǎng)空間數(shù)據(jù)索引方法。它將路網(wǎng)劃分成多個子圖，并預(yù)先計算各邊界點的路網(wǎng)距離，從而達(dá)到降低最短路徑計算代價的目的。

反最近鄰查詢由于其在決策支持和發(fā)現(xiàn)潛在用戶等方面的重要應(yīng)用而受到了學(xué)術(shù)界的廣泛關(guān)注。在反最近鄰查詢的相關(guān)研究中，路網(wǎng)下空間關(guān)鍵字反最近鄰查詢被人們用來發(fā)現(xiàn)興趣集。其中，興趣集是指對某個興趣點感興趣的一群人。然而，路網(wǎng)下空間關(guān)鍵字反最近鄰查詢只考慮了文本和空間信息，并查找那些最有可能成為潛在用戶的人群。

隨著社交網(wǎng)絡(luò)的發(fā)展，社交網(wǎng)絡(luò)數(shù)據(jù)的體量越來越大。在社交網(wǎng)絡(luò)中，有社交聯(lián)系的用戶可能具有相似的興趣愛好，因而這類數(shù)據(jù)可以為預(yù)測和推薦提供支持?；诖?，人們研究了地理社交關(guān)鍵字查詢。給定一個地理社交關(guān)鍵字查詢和提交該查詢的用戶，此查詢返回空間距離最近，文本相似性最高的興趣點，并且該用戶的朋友訪問該興趣點的次數(shù)最多。

目前，針對路網(wǎng)下空間關(guān)鍵字反最近鄰查詢和地理社交關(guān)鍵字查詢已有成熟的解決方案。但是在某些應(yīng)用場景中，反最近鄰查詢不僅要考慮空間和文本信息，而且也要考慮用戶之間的社交信息以及用戶對興趣點的簽到信息。然而，現(xiàn)有的查詢處理方法還不能有效地解決上述查詢問題。

發(fā)明內(nèi)容

本發(fā)明克服了現(xiàn)有技術(shù)不能有效地處理路網(wǎng)下地理社交關(guān)鍵字反最近鄰查詢問題，提供了一種路網(wǎng)下地理社交關(guān)鍵字反最近鄰查詢處理方法。

本發(fā)明解決其技術(shù)問題所采用的技術(shù)方案步驟如下：一種路網(wǎng)下地理社交關(guān)鍵字反最近鄰查詢處理方法，該方法包括如下步驟：

步驟(1)：收集用戶與興趣點，對其構(gòu)建GIM樹索引結(jié)構(gòu)；

步驟(2)：計算每個GIM樹索引結(jié)構(gòu)的節(jié)點的地理社交關(guān)鍵字的最小相似性計數(shù)表與最大相似性計數(shù)表；

步驟(3)：利用剪枝算法對步驟(1)收集到的用戶與興趣點進(jìn)行過濾；

步驟(4)：根據(jù)步驟(3)中過濾的結(jié)果，通過精煉算法剔除不符合要求的用戶，以得到最終結(jié)果集合。

進(jìn)一步的，所述的步驟(1)中GIM樹索引結(jié)構(gòu)的構(gòu)建步驟如下：將整個路網(wǎng)劃分成多個子圖，并將屬于多個子圖的路網(wǎng)節(jié)點定義為邊界點；預(yù)先計算所有邊界點之間的路網(wǎng)距離；每個GIM樹索引結(jié)構(gòu)節(jié)點包含一個路網(wǎng)子圖、一個交并倒排文件和兩個矩陣；交并倒排文件描述的是用戶與興趣點之間的文本信息；兩個矩陣為用戶簽到矩陣和用戶社交關(guān)系矩陣，用戶簽到矩陣存儲用戶對各興趣點的簽到次數(shù)，用戶社交關(guān)系矩陣存儲用戶之間的社交關(guān)系。

進(jìn)一步的，所述的步驟(2)中最小相似性計數(shù)表與最大相似性計數(shù)表的計算方法如下：

給定一組用戶和一組興趣點，利用步驟(1)中用戶簽到矩陣和用戶社交關(guān)系矩陣這兩個矩陣相乘計算用戶和興趣點之間地理社交關(guān)鍵字相似性的最小值和最大值；利用上述最小值和最大值構(gòu)建用戶的最小相似性計數(shù)表和最大相似性計數(shù)表。

進(jìn)一步的，所述的步驟(3)中剪枝算法具體如下：