[發(fā)明專利]使用數(shù)據(jù)結(jié)構(gòu)處理搜索查詢

有效

• 申請?zhí)枺?/td>: 201210409001.2
• 申請日: 2012-10-24
• 公開（公告）號(hào): CN102999558A
• 公開（公告）日: 2013-03-27
• 發(fā)明（設(shè)計(jì)）人: K.特雷特賈科夫;L.加西亞-巴呂洛斯;A.阿馬斯-切爾文特斯;J.維洛;M.G.杜馬斯
• 申請（專利權(quán)）人: 斯凱普公司
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 李舒;汪揚(yáng)

1.?一種生成存儲(chǔ)于計(jì)算機(jī)存儲(chǔ)器中用于在互連節(jié)點(diǎn)網(wǎng)絡(luò)中執(zhí)行搜索查詢時(shí)使用的數(shù)據(jù)結(jié)構(gòu)的方法，其中所述方法包括通過以下步驟選擇地標(biāo)節(jié)點(diǎn)并且在所述數(shù)據(jù)結(jié)構(gòu)中示出所選擇的地標(biāo)節(jié)點(diǎn)：

從所述網(wǎng)絡(luò)節(jié)點(diǎn)對頂點(diǎn)對的第一樣本采樣；

計(jì)算用于每個(gè)頂點(diǎn)對的最短路徑，每個(gè)最短路徑包括在所述頂點(diǎn)對中的每個(gè)頂點(diǎn)之間的頂點(diǎn)集；

標(biāo)識(shí)比任何其它頂點(diǎn)更經(jīng)常出現(xiàn)于更多最短路徑中的第一地標(biāo)節(jié)點(diǎn)；

從所述網(wǎng)絡(luò)頂點(diǎn)去除包括所述第一地標(biāo)節(jié)點(diǎn)的最短路徑；并且

標(biāo)識(shí)比任何其它剩余頂點(diǎn)出現(xiàn)于更多剩余最短路徑中的第二地標(biāo)節(jié)點(diǎn)。

2.?根據(jù)權(quán)利要求1所述的方法，包括在所述數(shù)據(jù)結(jié)構(gòu)中與每個(gè)地標(biāo)節(jié)點(diǎn)關(guān)聯(lián)地存儲(chǔ)用于所述網(wǎng)絡(luò)中的每個(gè)頂點(diǎn)的頂點(diǎn)數(shù)據(jù)。

3.?根據(jù)權(quán)利要求2所述的方法，其中所述頂點(diǎn)數(shù)據(jù)包括從每個(gè)頂點(diǎn)到所述地標(biāo)節(jié)點(diǎn)的距離，或者最短路徑樹。

4.?根據(jù)權(quán)利要求3所述的方法，其中所述最短路徑樹是父鏈接集的形式，其中每個(gè)父鏈接標(biāo)識(shí)在所述頂點(diǎn)與所述地標(biāo)節(jié)點(diǎn)之間的所述最短路徑中的鄰近頂點(diǎn)節(jié)點(diǎn)。

5.?一種處理搜索查詢以提供搜索結(jié)果的方法，所述方法包括：

在計(jì)算機(jī)設(shè)備處接收數(shù)字消息形式的搜索查詢，所述查詢標(biāo)識(shí)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)；并且

在所述計(jì)算機(jī)設(shè)備處執(zhí)行用于生成搜索結(jié)果的應(yīng)用，所述應(yīng)用執(zhí)行以下步驟：

訪問根據(jù)權(quán)利要求1-4中任一方法生成的數(shù)據(jù)結(jié)構(gòu)，其中每個(gè)地標(biāo)已經(jīng)隨其存儲(chǔ)了父鏈接集形式的的最短路徑樹，其中每個(gè)父鏈接標(biāo)識(shí)鄰近的頂點(diǎn)節(jié)點(diǎn)；

對于每個(gè)地標(biāo)，標(biāo)識(shí)所述源節(jié)點(diǎn)和所述目標(biāo)節(jié)點(diǎn)在通向所述地標(biāo)節(jié)點(diǎn)的所述最短路徑樹中的位置；

對于每個(gè)地標(biāo)節(jié)點(diǎn)，使用所標(biāo)識(shí)的所述目標(biāo)節(jié)點(diǎn)和所述源節(jié)點(diǎn)的位置生成所述源節(jié)點(diǎn)與所述目標(biāo)節(jié)點(diǎn)之間的距離的度量；

確定具有最短距離的所述地標(biāo)；以及

提供與該地標(biāo)的所述最短路徑樹有關(guān)的搜索結(jié)果。

6.?根據(jù)權(quán)利要求5所述的方法，其中通過以下操作生成所述距離度量：

(a)?計(jì)算在所述源節(jié)點(diǎn)與所述地標(biāo)節(jié)點(diǎn)之間的最短路徑上的第一距離；

計(jì)算在所述地標(biāo)節(jié)點(diǎn)與所述目標(biāo)節(jié)點(diǎn)之間的最短路徑上的第二距離；以及

將所述第一與第二距離求和；或者

(b)?標(biāo)識(shí)在從所述源節(jié)點(diǎn)和所述目標(biāo)節(jié)點(diǎn)到所述地標(biāo)節(jié)點(diǎn)的所述最短路徑樹中的共同祖先節(jié)點(diǎn)，以及將從所述源節(jié)點(diǎn)到所述共同祖先節(jié)點(diǎn)的第一距離與從所述共同祖先節(jié)點(diǎn)到所述目標(biāo)節(jié)點(diǎn)的第二距離求和以生成所述距離度量；或者

(c)?標(biāo)識(shí)在從所述源節(jié)點(diǎn)和所述目標(biāo)節(jié)點(diǎn)到所述地標(biāo)節(jié)點(diǎn)的所述最短路徑樹中的共同祖先節(jié)點(diǎn)；

標(biāo)識(shí)在所述源節(jié)點(diǎn)與所述共同祖先節(jié)點(diǎn)之間的第一路徑和在所述共同祖先節(jié)點(diǎn)與所述目標(biāo)節(jié)點(diǎn)之間的第二路徑中的所有節(jié)點(diǎn)對；

對所述對中的作為邊的任何對定位；

標(biāo)識(shí)最短距離的所述邊；并且

使用所述邊確定在所述源節(jié)點(diǎn)與所述目標(biāo)節(jié)點(diǎn)之間的距離度量；或者

(d)?對于每個(gè)地標(biāo)，記錄在從所述源節(jié)點(diǎn)和所述目標(biāo)節(jié)點(diǎn)到所述地標(biāo)節(jié)點(diǎn)的所述最短路徑樹之間共同的節(jié)點(diǎn)；

從所述源節(jié)點(diǎn)執(zhí)行圖形遍歷，僅遍歷共同記錄的節(jié)點(diǎn)，以更新從所述源節(jié)點(diǎn)到所述目標(biāo)節(jié)點(diǎn)的最短路徑；以及

使用所述更新的最短路徑確定所述距離度量；或者

(e)?按照使用更新的最短路徑的(b),?(c)或(d)的方法。

7.?根據(jù)權(quán)利要求5或6所述的方法，其中提供搜索結(jié)果的步驟包括向用戶顯示所述搜索結(jié)果；或者向搜索功能提供所述搜索結(jié)果，所述搜索功能生成在多個(gè)搜索結(jié)果之間的比較以按照排列順序提供輸出集。

8.?根據(jù)權(quán)利要求5、6或7所述的方法，其中所述搜索結(jié)果包括具有最短距離的所述地標(biāo)的所述最短路徑樹中的節(jié)點(diǎn)標(biāo)識(shí)符列表；或者針對最短距離的所述地標(biāo)的所述最短路徑樹中的節(jié)點(diǎn)數(shù)目。