[發明專利]一種圖數據上的語義關聯搜索的查詢松弛方法

有效

• 申請號: 202010089733.2
• 申請日: 2020-02-13
• 公開（公告）號: CN113254718B
• 公開（公告）日: 2023-08-29
• 發明（設計）人: 李舒馨;程龔
• 申請（專利權）人: 南京大學
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903;G06F40/30
• 代理公司: 南京天翼專利代理有限責任公司 32112
• 代理人: 奚銘

1.一種圖數據上的語義關聯搜索的查詢松弛方法，其特征是將語義關聯看作樹形，樹中的葉子節點都為實體，其中用于搜索的實體為查詢實體，語義關聯的直徑為任意兩個實體間的最大距離，對于給定的實體關聯圖G和直徑約束D，以及非空查詢實體集合Q，計算出Q的最大成功子查詢集合Q_max用于搜索，實現查詢松弛；

計算Q_max時首先分別計算所有查詢實體qe的優先級pr，建立元組qe,qe,pr，將其加入優先隊列中，只要優先隊列不為空，就取出隊首元組，即當前優先隊列中優先級最高的元組，對隊首元組的查詢實體qe進行驗證，以隊首元組的查詢實體qe為驗證點，計算相對于驗證點滿足距離條件的所有查詢實體得到子查詢集合Q_e，作為最優解，如當前元組計算的Q_e大于前一組元組的Q_e，則更新最優解，直至當前實體的優先級已經無法得出更優的解，則終止，得到的最大Q_e即為最大成功子查詢集合Q_max；所述距離條件為：

(1)任意一個子查詢集合中的查詢實體到驗證點的距離不超過

(2)如果直徑約束是奇數，則對于所有到驗證點距離為的查詢實體，驗證點有一個鄰居點，鄰居點到這些查詢實體的距離為

計算Q_max包括以下步驟：

(1)初始時建立一個空的優先隊列pq，該優先隊列為一個最大堆，存儲的元素為元組實體，起始實體，優先級，記為e,sqe,pr，Q_max初始為空集，用于記錄當前最優解，設置一個checked集合用于記錄已經被驗證過的實體，首先對于每個查詢實體qe，計算優先級pr，得到元組qe,qe,pr加入pq，并在實體訪問列表visited_qe中加入qe，對于e，其優先級pr的計算如下：

pr(e)＝|{sqe}∪{qe∈(Q\{sqe}):dist(e,sqe)+dist(e,qe′)≤D}|

其中sqe代表e的起始查詢實體，所有元組中的查詢實體都是由本身開始查詢，即以自身為驗證點，dist表示兩個實體間的距離，qe’為除了e之外的其他查詢實體，|·|表示集合元素數量；

(2)如果pq不為空，執行(3)，否則轉(9)；

(3)從pq中取出第一個元組，也就是當前優先隊列中優先級最高的元組，如果該元組的pr不超過|Q_max|，或者小于2，則轉(9)，否則繼續執行(4)；

(4)如果取出的元組中的e不在checked集合中，即e沒有被驗證過，就繼續執行(5)，否則轉(7)；

(5)對e進行驗證，驗證的結果為Q_e；

(6)將驗證過的e加入到checked集合中，如果Q_e比Q_max包含更多的元素，即|Q_e||Q_max|，就更新Q_max的值為Q_e，繼續執行(7)；

(7)如果e到sqe的距離小于并且pr大于|Q_max|，則對于e的所有鄰居e′，如果e^′不在訪問列表visited_qe中，并且e^′是沿著sqe出發的最短路徑訪問到的，就計算e^′的優先級pr′，并將元組e′,sqe,pr′加入pq中，將e^′加入visited_qe中；

(8)轉步驟(2)；

(9)返回Q_max。

2.根據權利要求1所述的一種圖數據上的語義關聯搜索的查詢松弛方法，其特征是所述步驟(5)具體為：

(5.1)計算到e的距離不超過的查詢實體集合Q¹，以及到e的距離恰好為的查詢實體集合Q²；

(5.2)如果Q¹比Q_max包含更多元素，繼續執行(5.3)，否則轉(5.6)；

(5.3)如果D是偶數，或者Q²包含不超過1個查詢實體，則將Q¹賦給Q_e，轉(5.5)，否則執行(5.4)；

(5.4)對于e的所有鄰居，找出到Q²中的查詢實體距離為的數量最多的鄰居e′，這對應了距離條件中的第(2)條，相應的查詢實體集合為R_e′，并將R_e′∪(Q¹\Q²)賦給Q_e；

(5.5)如果Q_e的大小超過1，則返回Q_e，否則轉(5.6)；

(5.6)返回空集。