[發明專利]一種道路網絡下多用戶空間關鍵詞查詢方法

有效

• 申請號: 201810480584.5
• 申請日: 2018-05-18
• 公開（公告）號: CN108733803B
• 公開（公告）日: 2022-04-29
• 發明（設計）人: 王勇;郝玉潔;林劼;張譯權;楊曉東
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537
• 代理公司: 成都金英專利代理事務所(普通合伙) 51218
• 代理人: 袁英

1.一種基于道路網絡的多用戶空間關鍵詞查詢方法，其特征在于，包括以下步驟：基于道路網絡的空間關鍵詞數據處理步驟S1、構造道路網絡索引步驟S2、構造查詢請求步驟S3、查詢初始化步驟S4、數據查詢步驟S5；

S1.基于道路網絡的空間關鍵詞數據處理步驟：將道路網絡建模為無向圖，用頂點表示道路網絡中的路口，用邊表示道路網絡中的一段道路；將度大于三的頂點記為交叉點；將攜帶關鍵詞的空間地點數據視為興趣點p，均分布于道路網絡G上；

S2.構造道路網絡索引：給定無向圖G＝{V,E}，以交叉點為核心構造Snode，以Snode為核心抽象無向圖G，并在此基礎上為道路網絡G構造層級索引結構HI，為基于道路網絡的多用戶空間關鍵詞查詢提供有效的索引結構；

定義如下概念：

Snode：給定無向圖G＝{V,E}，定義Sn是無向圖G的一個Snode當且僅當滿足如下兩個條件：(1)圖Sn是無向圖G的子圖；(2)圖Sn中僅存在一個度大于等于三的頂點；圖Sn可表示為Sn＝{Sn.V,Sn.E,Sn.ψ,Sn.λ}，其中，Sn.V是圖Sn的頂點集且Sn.E是圖Sn的邊集且Sn.ψ為位于圖Sn上的所有興趣點的關鍵詞集合的并集，即Sn.ψ＝{∪p.ψ|p位于邊e上且e∈Sn.E}；Sn.λ是圖Sn中唯一度大于等于三的頂點的位置信息；

鄰居點集合：給定頂點和無向圖G＝{V,E}，頂點的鄰居點集合Ne_i可表示為且該集合中每個頂點需要滿足以下三個條件：(1)頂點在無向圖G中且與頂點相鄰，即且(2)頂點的度小于三，即(3)頂點未被其他Snode包含覆蓋；

S3.構造查詢請求：給定四元數組Q＝{U,k,Ω,G}，k代表查詢結束后返回的興趣點個數，U代表一組查詢用戶，Ω為興趣點集合，G代表已被抽象化為無向圖的道路網絡；

S4.查詢初始化：定義查詢結果集R，并將其初始化為空；計算層級索引結構HI中頂點的價值Val；

S5.數據查詢：層級標識位j標識此時遍歷的無向圖所在的層級，將HI.height賦值給層級標識位j，即j←HI.height；無向圖G被初始化為G^j，表示遍歷將從層級索引結構HI所存儲的最頂層無向圖G^HI.height開始；維持一個根據興趣點價值大小排序的最小堆TE來保存待遍歷的興趣點，依次遍歷無向圖G中所有興趣點，分別計算他們的價值并將這些興趣點加入最小堆TE，判斷以下兩個停止條件是否被滿足：(1)結果集R中興趣點數量未達到用戶所要求的k個；(2)層級標識位j大于等于零；只有這兩個條件都滿足才會繼續執行查詢；最小堆TE彈出價值最小的興趣點current，并根據其狀態對其進行處理；當查詢不再繼續進行時，將結果集R返回給查詢用戶。

2.根據權利要求1所述的一種基于道路網絡的多用戶空間關鍵詞查詢方法，其特征在于，所述步驟S1包括以下子步驟：

S11.道路網絡建模：將道路網絡建模為無向圖G＝(V,E)，V表示G的頂點集，E表示G的邊集；頂點集的頂點v代表道路網絡中的路口或者道路中點，邊集中的邊e_(v,v')表示道路網絡中的一段道路；每一條邊都有相應的非負權重w_e，代表從一個端點到另一個端點的代價；將度大于三的頂點記為交叉點；

S12.興趣點構造：將攜帶關鍵詞的空間地點數據視為興趣點p，均分布于道路網絡G上；每一個興趣點p同樣可表示為id,λ,ψ,p.id是p的唯一標識，p.ψ為一組描述興趣點p的關鍵詞，p.λ＝(e,||p,v||)為興趣點p的位置信息，表示興趣點p位于道路網絡G的邊e上，其距離邊e的端點v的長度為||p,v||。