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

有效

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

1.一種路網下地理社交關鍵字反最近鄰查詢處理方法，其特征在于：該方法包括如下步驟：

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

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

步驟（3）：利用剪枝算法對步驟（1）收集到的用戶與興趣點進行過濾；

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

2.根據(jù)權利要求1所述的路網下地理社交關鍵字反最近鄰查詢處理方法，其特征在于：所述的步驟（2）中最小相似性計數(shù)表與最大相似性計數(shù)表的計算方法如下：

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

3.根據(jù)權利要求2所述的路網下地理社交關鍵字反最近鄰查詢處理方法，其特征在于：所述的步驟（3）中剪枝算法具體如下：

給定一個查詢點，根據(jù)步驟（2）的計算方法，得到查詢點與用戶相似性的最小值和最大值，再結合步驟（2）得到的最小相似性計數(shù)表和最大相似性計數(shù)表對用戶進行剪枝，其中：

1）若查詢點與用戶集合相似性的最大值比最小相似性計數(shù)表的下界值小，則丟棄這組用戶；

2）若查詢點與用戶集合相似性的最小值比最大相似性計數(shù)表的上界值大，將這組用戶插入到最終結果集合。

4.根據(jù)權利要求3所述的路網下地理社交關鍵字反最近鄰查詢處理方法，其特征在于：所述的步驟（3）中的過濾過程如下：

（3.1）初始化一個用戶隊列和一個興趣點隊列，將GIM樹索引根節(jié)點的用戶集合放入到用戶隊列中，將興趣點集合放入到興趣點隊列中；

（3.2）初始化一個候選用戶集合和一個最終結果集合，并分別保存當前訪問過的GIM樹索引節(jié)點中未被剪枝的用戶和被確認為最終結果的用戶；

（3.3）若用戶隊列為空，返回候選用戶集合和最終結果集合；否則取出用戶隊列的第一個元素，并對該元素在GIM樹索引結構的子節(jié)點利用步驟（3）中的剪枝算法進行剪枝，如果能滿足條件，那么將其插入到最終結果集合；若未被剪枝，則將其插入到候選用戶集合。

5.根據(jù)權利要求4所述的路網下地理社交關鍵字反最近鄰查詢處理方法，其特征在于：所述的步驟（4）中的精煉算法具體步驟如下：

（4.1）取出步驟（3）中候選用戶集合的每一個用戶；

（4.2）以空間距離順序找出該用戶的路網下地理社交關鍵字查詢結果集合；

（4.3）若查詢點在上述結果集合中，則將該用戶插入到最終結果集合；否則丟棄該用戶；

（4.4）返回最終結果集合。