[發明專利]基于圖數據的集合關鍵字查詢方法

有效

• 申請號: 201410746565.4
• 申請日: 2014-12-08
• 公開（公告）號: CN105740246B
• 公開（公告）日: 2019-08-06
• 發明（設計）人: 程祥;蘇森;趙森;雙鍇;徐鵬;王玉龍;張忠寶;楊放春
• 申請（專利權）人: 北京郵電大學
• 主分類號: G06F16/29
• 分類號: G06F16/29
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 李相雨

1.一種基于圖數據的集合關鍵字查詢方法，其特征在于，包括：

S1，解析目標圖，以確定目標圖中的節點，確定每個節點所能提供的服務，并查詢對每個節點提供服務的評分，計算每兩個節點之間的距離和相應開銷；

S2，解析查詢指令，確定起始節點、n個服務關鍵字、開銷約束和半徑約束，查詢到起始節點的距離滿足開銷約束且分別具有每個服務關鍵字的節點集合，將節點集合中每個節點之間的距離滿足半徑約束的集合作為備選集合；

S3，根據所述半徑約束對備選集合進行減少冗余計算，得到初步處理集合；

S4，根據初步處理集合中每個節點提供服務的評分對初步處理集合進行剪枝計算，得到目標集合；

S5，在目標圖中標記查詢到的目標集合進行顯示；

其中，所述步驟S1還包括：判斷目標圖中的節點數目是否超過預設值，若超過，則根據預設子圖節點數目和子圖半徑約束對所述目標圖進行劃分得到多個子圖，計算每個子圖中每兩個節點之間的距離和相應開銷，計算兩個子圖公共邊上的每個節點的分離得分為α|e|+β|s|，其中|e|為與節點相連的公共邊的數目，|s|為節點所屬子圖的數目，且α+β＝1，將公共邊上分離得分最高的節點作為樞紐點，通過樞紐點在子圖之間查詢節點；

其中，所述步驟S3包括：

定義點集RNS(i，j)_σ，其中j<i，表示該點集中的節點都是帶有關鍵字t_i的節點，并且這些節點與已選取的帶有關鍵字t₁，t₂，…，t_j的點的距離都小于半徑約束σ，確定關鍵字t₁，t₂，…，t_j分別對應的節點集合V_t1，V_t2，…，V_tj，在V_t1中選取一個包含t₁的節點A_t1，在V_t2中選取一個包含t₂的節點，判斷上述兩個節點的距離是否小于半徑約束σ，若不小于，則在V_t2中選取另一個包含t₂的節點，直至找到與A_t1的距離小于半徑約束σ的包含t₂的節點A_t2、A_t2’、A_t2”…，存儲RNS(2，1)_σ＝{A_t2、A_t2’、A_t2”…}，創建中間結果集合V_S＝{}循環上述步驟，在V_t3中查詢一個包含t₃且與V_t1的距離小于半徑約束σ的節點A_t3，存儲RNS(3，1)_σ＝{A_t3、A_t3’、A_t3”…}，…，在V_tj中查詢一個包含t₃且與V_t1的距離小于半徑約束σ的節點A_tj，存儲RNS(j，1)_σ＝{A_tj、A_tj’、A_tj”…}，當V_t2到V_tj中存在節點集合V_tg，其中的節點A_tg、A_tg’、A_tg”…到V_t1的距離均不小于半徑約束σ，則在RNS(g+1，1)_σ中查詢到節點A_tg的距離小于半徑約束σ節點，與A_t1和在RNS(2，1)_σ、RNS(3，1)_σ…RNS(j，1)_σ中分別選取的節點構成初步處理集合。