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

有效

• 申請號: 201210409001.2
• 申請日: 2012-10-24
• 公開（公告）號: CN102999558A
• 公開（公告）日: 2013-03-27
• 發明（設計）人: 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屆信息和知識管理國際會議的會議錄第867-878頁。在該論文中，在不同地標選擇策略之下評估基于地標的距離估計算法。根據這篇論文，已經表明最高程度和接近中心性技術典型地產生最高精度。

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

本發明的目的是較現有技術而言提高精度，而用于生成在處理搜索查詢時使用的數據結構的計算時間是可接受的。

發明內容

根據本發明的一個方面，提供一種生成存儲于計算機存儲器中用于在互連節點網絡中處理搜索查詢的數據結構的方法，其中該方法包括通過以下步驟選擇地標節點并且在數據結構中存儲所選擇的地標節點：從網絡節點采樣頂點對的第一樣本；計算每個頂點對的最短路徑，每個最短路徑包括在該頂點對中的每個頂點之間的頂點集；標識比任何其它頂點更經常出現于更多最短路徑中的第一地標節點；從網絡頂點去除包括第一地標節點的最短路徑；標識比任何其它剩余頂點出現于更多剩余最短路徑中的第二地標節點。

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