[發(fā)明專利]一種分布式環(huán)境下基于社會感知的空間關(guān)鍵字查詢方法

有效

• 申請?zhí)枺?/td>: 201810875808.2
• 申請日: 2018-08-03
• 公開（公告）號: CN108932347B
• 公開（公告）日: 2021-11-16
• 發(fā)明（設(shè)計）人: 趙相國;袁野;孫永佼
• 申請（專利權(quán)）人: 東北大學(xué)
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/14;G06F16/13;G06F16/182
• 代理公司: 北京君泊知識產(chǎn)權(quán)代理有限公司 11496
• 代理人: 王程遠

1.一種分布式環(huán)境下基于社會感知的空間關(guān)鍵字查詢方法，其特征在于，包括：

第一步、加載社會感知的空間分布式并行R樹SDPR樹全局的索引，在SDPR樹全局的索引樹中獲取查詢點集中的查詢點所在的分區(qū)；

第二步、在所獲取的分區(qū)內(nèi)分別指向空間關(guān)鍵字查詢算法SkSK操作，查詢找到距離該查詢點最近的k個空間對象；

第三步、在k個空間對象中得到的預(yù)定個數(shù)最相關(guān)的空間對象，然后進行結(jié)果的排序，獲取最終結(jié)果；

所述SDPR樹全局的索引包括：

1)、獲取空間數(shù)據(jù),所述空間數(shù)據(jù)包括若干空間對象,每個空間對象包括對應(yīng)的空間對象標示、空間對象的地理位置信息、空間中描述對象的關(guān)鍵字、以及空間對象的粉絲群體；

2)、利用空間層次分解的Hilbert編碼方式對空間數(shù)據(jù)進行數(shù)據(jù)劃分，將空間的數(shù)據(jù)劃分到數(shù)據(jù)分區(qū)；

3)、根據(jù)批量加載算法TGS，對數(shù)據(jù)分區(qū)后的每個區(qū)域的數(shù)據(jù)構(gòu)建局部的R樹索引，并對R樹索引進行存儲，R樹索引的存儲結(jié)構(gòu)包括索引樹的結(jié)構(gòu)信息、節(jié)點信息、空間對象的粉絲群體、空間對象數(shù)據(jù)以及空間中描述對象的關(guān)鍵字；

4)、利用STR算法構(gòu)建全局索引，并對全局索引進行存儲，全局索引的存儲結(jié)構(gòu)包括索引樹的結(jié)構(gòu)信息、節(jié)點信息、空間對象的粉絲群體；其中節(jié)點信息存放的是文件路徑；

所述步驟2)具體包括：

2.1、通過Hilbert對空間數(shù)據(jù)進行排序，并對排序后的數(shù)據(jù)進行編碼；

2.2、根據(jù)編碼將空間數(shù)據(jù)放入到存儲節(jié)點中，如果空間數(shù)據(jù)超過節(jié)點所限定大小則停止，然后從上次的斷點處用相同的方法將對象放入存儲節(jié)點中；

所述步驟2.1具體為：根據(jù)MBR進行排序，然后構(gòu)造Hilbert空間曲線，并且分配對象的排序值，獲取V_ii和V_avg并初始化B_j＝0；所述V_i表示第i個空間數(shù)據(jù)的大小，V_avg表示每個節(jié)點平均存儲容量，B_j表示第j個節(jié)點中數(shù)據(jù)大小；

所述步驟2.2具體為：比較B_j與平均的容量，如果小則i和k均自增，否則j自增；若k＝i，則重復(fù)該操作，直到i和k都為n-1并且j＝N-1為止；最后算出B_j，在將每個節(jié)點機的B_j劃分到各個磁盤中；所述k表示空間數(shù)據(jù)個數(shù)，n表示待劃分的空間對象總數(shù)量，N表示各個節(jié)點機的數(shù)量。

2.根據(jù)權(quán)利要求1所述的分布式環(huán)境下基于社會感知的空間關(guān)鍵字查詢方法，其特征在于，所述根據(jù)批量加載算法TGS，對數(shù)據(jù)分區(qū)后的每個區(qū)域的數(shù)據(jù)構(gòu)建局部的R樹索引就具體為：通過坐標軸方向分割數(shù)據(jù)，給定代價函數(shù)cost(r1,r2)：

cost(r1,r2)＝S_r1+S_r2

每個子集中含有多個矩形，所述矩形個數(shù)由每個子樹的最大矩形個數(shù)和小于該節(jié)點的個數(shù)乘積來獲得，該構(gòu)造過程在兩個子集上遞歸地生成整個R樹；其中，所述r1和r2分別是兩個被分割的數(shù)據(jù)的MBR，S為選取的掃描線。

3.根據(jù)權(quán)利要求1所述的分布式環(huán)境下基于社會感知的空間關(guān)鍵字查詢方法，其特征在于，所述索引樹的結(jié)構(gòu)信息包括該索引樹的大小，即整個樹節(jié)點區(qū)域的大小、索引樹的高度、容量、以及空間對象的個數(shù)信息。

4.根據(jù)權(quán)利要求1所述的分布式環(huán)境下基于社會感知的空間關(guān)鍵字查詢方法，其特征在于，所述空間中描述對象的關(guān)鍵字為倒排文件方式存儲。