[發(fā)明專(zhuān)利]有向無(wú)環(huán)圖中的節(jié)點(diǎn)

在審

• 申請(qǐng)?zhí)枺?/td>: 201710881282.4
• 申請(qǐng)日: 2017-09-26
• 公開(kāi)（公告）號(hào): CN108228697A
• 公開(kāi)（公告）日: 2018-06-29
• 發(fā)明（設(shè)計(jì)）人: 阿比納夫·坎德沃爾;迪亞內(nèi)什·達(dá)瑪尼亞;拉克希特·阿羅拉;莫希特·阿加爾瓦爾;卡爾希克·庫(kù)馬爾
• 申請(qǐng)（專(zhuān)利權(quán)）人: 谷歌有限責(zé)任公司
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 中原信達(dá)知識(shí)產(chǎn)權(quán)代理有限責(zé)任公司 11219
• 代理人: 陸弋;周亞榮

本申請(qǐng)涉及有向無(wú)環(huán)圖中的節(jié)點(diǎn)，其中，障礙節(jié)點(diǎn)聚集方法包括：在每個(gè)節(jié)點(diǎn)被定義為障礙節(jié)點(diǎn)或非障礙節(jié)點(diǎn)的有向無(wú)環(huán)圖中，針對(duì)第一障礙節(jié)點(diǎn)標(biāo)識(shí)作為第一障礙節(jié)點(diǎn)的后續(xù)障礙節(jié)點(diǎn)的每個(gè)后代節(jié)點(diǎn)；并在第一障礙節(jié)點(diǎn)處聚集作為第一障礙節(jié)點(diǎn)的后代且不通過(guò)任何所標(biāo)識(shí)的后續(xù)障礙節(jié)點(diǎn)而與第一障礙節(jié)點(diǎn)分離的每個(gè)非障礙節(jié)點(diǎn)的信息。非障礙節(jié)點(diǎn)傳播方法包括：在每個(gè)節(jié)點(diǎn)被定義為障礙節(jié)點(diǎn)或非障礙節(jié)點(diǎn)的有向無(wú)環(huán)圖中，針對(duì)第一非障礙節(jié)點(diǎn)標(biāo)識(shí)作為第一非障礙節(jié)點(diǎn)的先前障礙節(jié)點(diǎn)的每個(gè)祖先節(jié)點(diǎn)；并將第一非障礙節(jié)點(diǎn)的信息傳播到每個(gè)所標(biāo)識(shí)的先前障礙節(jié)點(diǎn)以及在第一非障礙節(jié)點(diǎn)與所標(biāo)識(shí)的先前障礙節(jié)點(diǎn)之間的每個(gè)非障礙節(jié)點(diǎn)。

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

本申請(qǐng)要求2016年12月22日提交的發(fā)明名稱(chēng)為“NODES IN DIRECTED ACYCLICGRAPH(有向無(wú)環(huán)圖中的節(jié)點(diǎn))”的美國(guó)專(zhuān)利申請(qǐng)No.15/388,288的優(yōu)先權(quán)，該美國(guó)專(zhuān)利申請(qǐng)的內(nèi)容通過(guò)引用的方式并入本文。

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

本文獻(xiàn)總體上涉及有向無(wú)環(huán)圖中的節(jié)點(diǎn)。

背景技術(shù)

圖形被用在計(jì)算機(jī)系統(tǒng)中，以便組織項(xiàng)或其它實(shí)體的集合，例如在磁盤(pán)上或以另一種形式的存儲(chǔ)裝置。這樣的組織有時(shí)被實(shí)現(xiàn)為節(jié)點(diǎn)的層次結(jié)構(gòu)，其中，諸如文件的項(xiàng)被布置成具有定義的祖先和后代。有時(shí)，在這樣的系統(tǒng)中執(zhí)行聚集，例如從根到葉，或者從葉到根。文件系統(tǒng)層次結(jié)構(gòu)上的聚集的示例包含將文件的計(jì)數(shù)和層次結(jié)構(gòu)中的文件夾的計(jì)數(shù)聚集。這樣的系統(tǒng)能夠允許用戶查詢(xún)比如說(shuō)存儲(chǔ)在層次結(jié)構(gòu)中的節(jié)點(diǎn)下面的圖像的數(shù)目或由磁盤(pán)上的特定子層次結(jié)構(gòu)使用的字節(jié)的數(shù)目。

在一些現(xiàn)有系統(tǒng)中，每個(gè)節(jié)點(diǎn)維護(hù)一個(gè)祖先列表，該祖先列表針對(duì)該節(jié)點(diǎn)指定層次結(jié)構(gòu)中的節(jié)點(diǎn)上面的所有其它節(jié)點(diǎn)的名字。在這樣的系統(tǒng)中，然后能夠通過(guò)搜索具有其祖先列表中的特定節(jié)點(diǎn)的任何節(jié)點(diǎn)來(lái)執(zhí)行位于特定節(jié)點(diǎn)處或下面的信息的查詢(xún)。這可以認(rèn)為是一種預(yù)計(jì)算方法，因?yàn)殛P(guān)系是通過(guò)隨著層次結(jié)構(gòu)改變必須保持最新的祖先列表來(lái)維護(hù)的。當(dāng)層次結(jié)構(gòu)變深、具有高扇出度時(shí)或者簡(jiǎn)單地當(dāng)層次結(jié)構(gòu)頻繁改變時(shí)，該方法可能變得低效，甚至是不切實(shí)際的。例如，當(dāng)層次結(jié)構(gòu)被更新時(shí)(例如，當(dāng)內(nèi)容改變時(shí))，完全基于預(yù)計(jì)算的系統(tǒng)可能存在延時(shí)的問(wèn)題。另一方面，僅使用查詢(xún)時(shí)間聚集的方法對(duì)于大型的復(fù)雜層次結(jié)構(gòu)不起作用。

發(fā)明內(nèi)容

在第一方面，一種由有向無(wú)環(huán)圖中的障礙節(jié)點(diǎn)(barrier node)進(jìn)行的聚集的方法包括：在每個(gè)節(jié)點(diǎn)被定義為障礙節(jié)點(diǎn)或非障礙節(jié)點(diǎn)(non-barrier node)的有向無(wú)環(huán)圖中，針對(duì)第一障礙節(jié)點(diǎn)標(biāo)識(shí)作為第一障礙節(jié)點(diǎn)的后續(xù)障礙節(jié)點(diǎn)的每個(gè)后代節(jié)點(diǎn)；以及，在第一障礙節(jié)點(diǎn)處聚集作為第一障礙節(jié)點(diǎn)的后代并且不通過(guò)任何所標(biāo)識(shí)的后續(xù)障礙節(jié)點(diǎn)而與第一障礙節(jié)點(diǎn)分離的每個(gè)非障礙節(jié)點(diǎn)的信息。

實(shí)施方式能夠包括以下特征中的任一個(gè)或全部。所述方法還包括：為第一障礙節(jié)點(diǎn)創(chuàng)建第一列表，該第一列表標(biāo)識(shí)了第一障礙節(jié)點(diǎn)的作為障礙節(jié)點(diǎn)的所有后代節(jié)點(diǎn)。所述方法還包括：使第一列表是累積的，使得：如果第一障礙節(jié)點(diǎn)的第一列表標(biāo)識(shí)了特定障礙節(jié)點(diǎn)，那么，在第一障礙節(jié)點(diǎn)上面的障礙節(jié)點(diǎn)的包含了第一障礙節(jié)點(diǎn)的相應(yīng)第一列表也將包含所述特定障礙節(jié)點(diǎn)。所述方法還包括：檢測(cè)新關(guān)系將被引入到有向無(wú)環(huán)圖中；使用所述第一列表確定該新關(guān)系是否是有環(huán)的；以及，一旦確定該新關(guān)系是有環(huán)的，就在所述有向無(wú)環(huán)圖中阻止該新關(guān)系。所述方法還包括：將第一列表存儲(chǔ)在第一障礙節(jié)點(diǎn)處。所述方法還包括：為第一障礙節(jié)點(diǎn)創(chuàng)建第二列表，該第二列表標(biāo)識(shí)了第一障礙節(jié)點(diǎn)的作為障礙節(jié)點(diǎn)的所有祖先節(jié)點(diǎn)。第二列表指示了哪些節(jié)點(diǎn)將第一障礙節(jié)點(diǎn)標(biāo)識(shí)在其相應(yīng)的第一列表中。

在第二方面，由有向無(wú)環(huán)圖中的非障礙節(jié)點(diǎn)進(jìn)行的傳播的方法包括：在每個(gè)節(jié)點(diǎn)被定義為障礙節(jié)點(diǎn)或非障礙節(jié)點(diǎn)的有向無(wú)環(huán)圖中，針對(duì)第一非障礙節(jié)點(diǎn)標(biāo)識(shí)作為第一非障礙節(jié)點(diǎn)的先前障礙節(jié)點(diǎn)的每個(gè)祖先節(jié)點(diǎn)；以及，將第一非障礙節(jié)點(diǎn)的信息傳播到每個(gè)所標(biāo)識(shí)的先前障礙節(jié)點(diǎn)以及在第一非障礙節(jié)點(diǎn)與所標(biāo)識(shí)的先前障礙節(jié)點(diǎn)之間的每個(gè)非障礙節(jié)點(diǎn)。