[發(fā)明專利]針對演進(jìn)圖形分配全局邊緣ID

有效

• 申請?zhí)枺?/td>: 201580063517.8
• 申請日: 2015-10-12
• 公開（公告）號: CN107004011B
• 公開（公告）日: 2021-08-03
• 發(fā)明（設(shè)計(jì)）人: X·朱;T·L·維爾克;B·凱勒;S-C·陳;K·達(dá)塔
• 申請（專利權(quán)）人: 英特爾公司
• 主分類號: G06F16/901
• 分類號: G06F16/901
• 代理公司: 永新專利商標(biāo)代理有限公司 72002
• 代理人: 劉瑜;王英

本文描述了用于針對演進(jìn)圖形分配全局邊緣ID的方法、計(jì)算系統(tǒng)、以及計(jì)算機(jī)可讀介質(zhì)。該方法包括針對演進(jìn)圖形選擇塊大小，并且當(dāng)將新的頂點(diǎn)被添加到演進(jìn)圖形時，針對演進(jìn)圖形計(jì)算塊ID。計(jì)算塊ID包括創(chuàng)建表示演進(jìn)圖形的表，并且當(dāng)新的頂點(diǎn)被添加到演進(jìn)圖形時，在針對表的新行中的單元格計(jì)算塊ID之前針對表的新列中的單元格計(jì)算塊ID。該方法還包括針對演進(jìn)圖形基于源頂點(diǎn)ID、目標(biāo)頂點(diǎn)ID、以及每個邊緣所位于的塊的塊ID來計(jì)算全局邊緣ID。該方法還可以包括針對演進(jìn)圖形計(jì)算增量頁面排序。

相關(guān)申請的交叉引用

本申請要求享有于2014年12月23日提交的美國專利申請No.14/581,112的提交日的權(quán)益，其通過引用并入本文中。

技術(shù)領(lǐng)域

本技術(shù)總體上涉及管理圖形處理平臺的演進(jìn)圖形。更具體地，本技術(shù)涉及針對演進(jìn)圖形分配全局邊緣ID。

背景技術(shù)

在“大數(shù)據(jù)”時代，許多應(yīng)用(舉例來說，例如，與電子商務(wù)、社交網(wǎng)絡(luò)、以及在線服務(wù)有關(guān)的應(yīng)用)使用快速增長的龐大的圖形。在許多情況下，這些應(yīng)用每天必須處理數(shù)百萬到數(shù)十億的新事件。例如，平均每天在Twitter上產(chǎn)生5.6億個推文，并且平均每天在Facebook上產(chǎn)生45億個“喜歡”。作為另一個示例，亞馬遜在2013年圣誕季期間每天銷售2.82億件商品。新事件產(chǎn)生新關(guān)系，例如用戶與產(chǎn)品的關(guān)系、朋友關(guān)系、以及用戶與廣告的關(guān)系。應(yīng)用使用以這些新關(guān)系為基礎(chǔ)的關(guān)系數(shù)據(jù)以用于各種目的。例如，這樣的關(guān)系數(shù)據(jù)可以用于做出智能商業(yè)決策或者向用戶提供快速且準(zhǔn)確的建議。

為了使應(yīng)用能夠使用這種關(guān)系數(shù)據(jù)，使用圖形分析來處理數(shù)據(jù)以創(chuàng)建大的圖形。這樣的圖形由大量的頂點(diǎn)和邊緣組成。頂點(diǎn)是表示例如不同用戶的節(jié)點(diǎn)，而邊緣是表示將不同用戶彼此連接的關(guān)系數(shù)據(jù)的線。在大數(shù)據(jù)時代，隨著數(shù)據(jù)量增加，這些圖形非常快速地增長。然而，用于處理這些類型的圖形的當(dāng)前技術(shù)一般涉及具有固定數(shù)量的頂點(diǎn)和邊緣的靜態(tài)圖形。當(dāng)前技術(shù)不能提供高效方法以隨著新的頂點(diǎn)和邊緣隨時間被添加到圖形而對這些圖形進(jìn)行更新。

附圖說明

圖1是根據(jù)一個實(shí)施例的示意圖，其示出了用于處理關(guān)系數(shù)據(jù)的圖；

圖2是根據(jù)一個實(shí)施例的過程流程圖，其示出了用于計(jì)算全局邊緣ID的方法；

圖3是根據(jù)一個實(shí)施例的表，其示出了用于在將塊ID分配給增加的行之前將塊ID分配給增加的列的技術(shù)；

圖4是根據(jù)一個實(shí)施例的表，其示出了用于在將塊ID分配給增加的列之前將塊ID分配給增加的行的技術(shù)；

圖5是根據(jù)一個實(shí)施例的過程流程圖，其示出了用于以遞歸函數(shù)計(jì)算塊ID的方法；

圖6A是根據(jù)一個實(shí)施例的表，其示出了用于基于最后的對角線單元格和源塊ID將塊ID分配給新添加的列中的單元格的技術(shù)；

圖6B是具有新添加的行的圖6的表；

圖7是根據(jù)一個實(shí)施例的表，其示出了基于本文所描述的計(jì)算順序來進(jìn)行高速緩存的關(guān)鍵塊ID；

圖8是根據(jù)一個實(shí)施例的過程流程圖，其示出了用于針對演進(jìn)圖形增量地計(jì)算頁面排序的方法；

圖9是表示本文所描述的用于針對演進(jìn)圖形計(jì)算增量頁面排序的技術(shù)的一個實(shí)施例的偽代碼的屏幕截圖；

圖10是表示本文所描述的用于針對演進(jìn)圖形計(jì)算增量頁面排序的技術(shù)的另一個實(shí)施例的偽代碼的屏幕截圖；

圖11是示出根據(jù)本文所描述的實(shí)施例的被配置為針對演進(jìn)圖形提供全局邊緣ID分配和/或增量頁面排序計(jì)算的計(jì)算設(shè)備的框圖；以及

圖12是示出根據(jù)本文所描述的實(shí)施例的被配置為針對演進(jìn)圖形提供全局邊緣ID分配和/或增量頁面排序計(jì)算的計(jì)算機(jī)可讀介質(zhì)的框圖。