[發明專利]使用數據結構處理搜索查詢

有效

• 申請號: 201210408971.0
• 申請日: 2012-10-24
• 公開（公告）號: CN103064872A
• 公開（公告）日: 2013-04-24
• 發明（設計）人: K.特雷特賈科夫;L.加西亞-巴呂洛斯;A.阿馬斯-切爾文特斯;J.維洛;M.G.杜馬斯
• 申請（專利權）人: 斯凱普公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 李舒;汪揚

技術領域

本發明涉及處理搜索查詢，特別是在互連節點的網絡中處理搜索查詢。

背景技術

存在計算機網絡典型地包括很大數目的互連節點的許多情形。例如Skype的通信網絡代表用于對等通信的大型社交網絡。圖1是典型計算機網絡的一小部分的示意圖。示出的網絡包括多個節點Ni。每個節點可以如圖所示與一個或者多個物理計算機設備關聯，例如在節點Ni的情況下示出了該節點與移動設備2、PC?4和平板電腦6關聯。每個節點與單個用戶關聯，該用戶在這一情況下可以使用這些計算機設備中的任何一個來向特定網絡注冊或者登錄。示出了節點由連接Ci互連。在物理網絡的背景中，可以用任何已知的有線或者無線方式實施連接Ci。在與節點關聯的用戶的背景中，連接未必涉及網絡中的單個物理連接，但是代表與在連接的任一端處的節點關聯的用戶之間的關系。作為例子，在Skype的情況下，兩個用戶在他們處于彼此的聯系人列表中的情況下被視為連接。對這樣的網絡的常見挑戰是允許用戶例如按照姓名搜尋另一用戶并且看見搜索的結果，這些結果以它們到他的最短路徑距離的順序排列。類似地，用戶可能希望知道什么聯系人鏈允許他到達網絡中的另一用戶。對解決該問題的嘗試已經使用分析技術以便找到在圖形中的給定一對節點之間的最短路徑。

存在有解決這一問題的許多方法。現有方法可以廣義地分類為精確的和近似的。對于在具有數以億計的頂點的圖形上執行在線查詢，精確方法（如基于Dijkstra遍歷的方法）極其緩慢，該頂點數目是現代社交網絡的典型大小。在近似方法之中，用于這一問題的可擴展的算法系列是所謂的基于地標（或者基于略圖）的方法。在這一技術系列中，選擇地標節點的固定集并且預先計算從每個頂點到一些或者所有地標的距離。關于到地標的距離的知識連同三角不等式一起典型地允許人們在O(k)時間、O(kn)空間內計算任何兩個頂點之間的近似距離，其中k是地標數目并且n是網絡中的頂點數目。然后可以原樣使用那些估計或者進一步利用它們作為圖形遍歷或者路由策略的組成部分（component）以便獲得精確的最短路徑。

參考Potamias等人的標題為“Fast?Shortest?Path?Distance?Estimation?in?Large?networks”的論文，該論文發表于CIKM?’09：2009年美國紐約第18界關于IKM會議的會議錄第867-878頁。在該論文中，在不同地標選擇策略之下評估基于地標的距離估計算法。該算法依賴于存儲每個地標節點到圖形中的每個其它頂點的距離。與其它基于地標的算法一樣，近似質量特別在網絡隨時間升級時可能較差。

在Gubichev等人的標題為“Fast?and?accurate?estimates?of?shortest?paths?in?large?graphs”的另一篇論文中，該論文發表于CKM’10：2010年AEM的第19界AEM?IKM會議的會議錄第499-508頁。與用于每個頂點的不同地標集一起存儲從每個頂點到每個地標的完整路徑。這顯著提高存儲器要求并且增加了用于處理查詢的執行時間。

雖然基于地標的算法未提供關于近似質量的強理論保障，但是已經表明它們在實踐中表現良好從而升級至具有數以百萬或者甚至數十億計的邊的圖形，而精度是可接受的并且響應時間在每個查詢一秒以下。

本發明的目的是較現有技術而言提高精度，而用于返回搜索查詢的結果的計算時間和存儲器要求是可接受的。

發明內容

根據本發明的一個方面，提供一種處理搜索查詢以提供搜索結果的計算機實施的方法，該方法包括：在計算機設備處接收數字消息形式的搜索查詢，該查詢標識源節點和目標節點；并且在計算機設備處執行用于生成搜索結果的應用，該應用執行以下步驟：訪問保持多個地標節點的數據結構，其中每個地標節點已經隨其存儲了父鏈接集形式的最短路徑樹，其中每個父鏈接標識在數據結構中的每個節點與地標節點之間的最短路徑中的鄰近的頂點節點；對于每個地標節點，標識源節點和目標節點在通向地標節點的最短路徑樹中的位置；對于每個地標節點，使用標識的目標節點和源節點的位置生成源節點與目標節點之間的距離的度量；確定具有最短距離的地標節點；并且提供與該地標節點的最短路徑樹有關的搜索結果。

本發明也提供一種計算機程序產品，該計算機程序產品包括記錄于介質上的程序代碼裝置，該程序代碼裝置在由計算機執行時執行上文限定的方法的步驟。

本發明在不同實施例中提供三種技術。