[發明專利]一種基于圖的多點路徑查詢方法和裝置

在審

• 申請號: 201910132053.1
• 申請日: 2019-02-22
• 公開（公告）號: CN111611442A
• 公開（公告）日: 2020-09-01
• 發明（設計）人: 郝彤
• 申請（專利權）人: 京東數字科技控股有限公司
• 主分類號: G06F16/901
• 分類號: G06F16/901;G06F16/903
• 代理公司: 北京德琦知識產權代理有限公司 11018
• 代理人: 杜志敏;宋志強

本申請提供了一種基于圖的多點路徑查詢方法，接收到查詢請求時，針對V中的每個起始頂點擴展M層，將每個起始頂點分別記錄到一個數組中；將V中的兩兩起始頂點對應的擴展信息求交集之后，再將所有交集內的擴展信息求并集；并獲取并集中前N條擴展信息作為初步擴展信息；根據緩存中的鄰接表將初步擴展信息對應的每個頂點再擴展L?M層，并獲取對應的擴展信息作為二次擴展信息；合并初步擴展信息和二次擴展信息，過濾掉非起始頂點對應的擴展信息作為待返回擴展信息；獲取待返回擴展信息中的前N條擴展信息，并將所述獲取的前N條擴展信息中的路徑信息響應給發送查詢請求的設備。該方法能夠提高查詢效率。

技術領域

本發明涉及信息處理技術領域，特別涉及一種基于圖的多點路徑查詢方法和裝置。

背景技術

圖(Graph)是用來表示物件與物件之間的關系的對象，是圖論的基本研究對象。圖是一個有序二元組(V,E)，其中V稱為頂點集，E稱為邊集。E的元素用(x,y)表示，其中x,y∈V。

計算圖中多個頂點之間的關系是非常有意義的，例如：計算兩個人在網絡上的人脈關系，計算多家公司的之間的投資關系等。

傳統計算方法為：以一個節點為中心向外層擴展，直到擴展到目的節點或者達到限定的層次為止。

由一個頂點向外層擴展時，隨著擴展計算層次的增加，計算的節點會形成指數級的增加，所以該計算方式不僅效率低，而且對內存消耗比較大。

如：假設圖中的每個頂點與100個頂點存在直接關系，如果要遍歷該頂點的2層關系，就涉及到100的2次方，也就是10000個頂點數據的加載。如果計算6層關系，就會加載1萬億個頂點數據。

發明內容

有鑒于此，本申請提供一種基于圖的多點路徑查詢方法和裝置，能夠提高查詢效率。

為解決上述技術問題，本申請的技術方案是這樣實現的：

一種基于圖的多點路徑查詢方法，該方法包括：

接收到查詢請求時，獲取該請求攜帶的起始頂點的集合V、擴展的層次數L和返回的路徑數量N；

針對V中的每個起始頂點擴展M層，將每個起始頂點對應的擴展信息分別記錄到一個數組中；并將擴展過程中經過的頂點和邊使用鄰接表進行緩存；其中，M小于L；

將V中的兩兩起始頂點對應的擴展信息求交集之后，再將所有交集內的擴展信息求并集；

將并集中的擴展信息按照預設規則進行排列；并獲取并集中前N條擴展信息作為初步擴展信息；

根據緩存中的鄰接表將初步擴展信息對應的每個頂點再擴展L-M層，并獲取對應的擴展信息作為二次擴展信息；

合并初步擴展信息和二次擴展信息，過濾掉非起始頂點對應的擴展信息，并按照預設規則排列，作為待返回擴展信息；

獲取待返回擴展信息中的前N條擴展信息，并將所述獲取的前N條擴展信息中的路徑信息響應給發送查詢請求的設備。

一種基于圖的多點路徑查詢裝置，該裝置包括：接收單元、獲取單元、第一擴展單元、第二擴展單元和響應單元；

所述接收單元，用于接收查詢請求；

所述獲取單元，用于當所述接收單元接收到查詢請求時，獲取該請求攜帶的起始頂點的集合V、擴展的層次數L和返回的路徑數量N；

所述第一擴展單元，用于針對獲取單元中的V中的每個起始頂點擴展M層，將每個起始頂點對應的擴展信息分別記錄到一個數組中；并將擴展過程中經過的頂點和邊使用鄰接表進行緩存；將V中的兩兩起始頂點對應的擴展信息求交集之后，再將所有交集內的擴展信息求并集；將并集中的擴展信息按照預設規則進行排列；并獲取并集中前N條擴展信息作為初步擴展信息；其中，M小于L；