[發(fā)明專利]一種基于外存的圖數(shù)據(jù)存儲方法及子圖查詢方法

有效

• 申請?zhí)枺?/td>: 201110202697.7
• 申請日: 2011-07-19
• 公開（公告）號: CN102254012A
• 公開（公告）日: 2011-11-23
• 發(fā)明（設(shè)計(jì)）人: 彭鵬;鄒磊;趙東巖;賈愛霞
• 申請（專利權(quán)）人: 北京大學(xué)
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長江

1.一種基于外存的圖數(shù)據(jù)存儲方法，其步驟為：

1)對圖數(shù)據(jù)格式統(tǒng)一為一種標(biāo)準(zhǔn)圖數(shù)據(jù)格式；其中，所述標(biāo)準(zhǔn)圖數(shù)據(jù)格式為：以“t#NNumberofVertices?NumberofEdges”開始，然后是圖中的點(diǎn)信息v，一個點(diǎn)對應(yīng)于一行，格式為“v?i?LabelofVertices_i”，然后是圖的邊信息e，一條邊對應(yīng)于一行，格式為“e?v_iv_j”；最后以“t#-1”結(jié)束；其中，N為圖的標(biāo)識，NumberofVertices為圖中點(diǎn)的數(shù)量，NumberofEdges為圖中邊的數(shù)量，i是點(diǎn)的標(biāo)識符，LabelofVertices_i是點(diǎn)上的唯一的標(biāo)簽信息，v_i是邊的起點(diǎn)信息，v_j為邊的終點(diǎn)信息；

2)根據(jù)圖數(shù)據(jù)中每條邊的起點(diǎn)和終點(diǎn)的標(biāo)簽信息，對圖中的邊進(jìn)行分類存儲，然后對每類邊建立B+-Tree索引；

3)按照圖數(shù)據(jù)中每個點(diǎn)上的標(biāo)簽信息，將圖中的點(diǎn)劃分為若干域，同一域中每一個點(diǎn)按點(diǎn)的標(biāo)識符順序依次對應(yīng)于一位；然后根據(jù)邊的起點(diǎn)、終點(diǎn)標(biāo)簽信息，為步驟2)中的每一類邊建立一位圖索引；

4)對每一類邊建立一起點(diǎn)信息數(shù)據(jù)直方圖和一終點(diǎn)信息數(shù)據(jù)直方圖，記錄同類邊的統(tǒng)計(jì)信息。

2.如權(quán)利要求1所述的方法，其特征在于按照字典序?yàn)槊款愡吔+-Tree索引。

3.如權(quán)利要求1或2所述的方法，其特征在于為每一類邊建立以位圖索引的方法為：首先根據(jù)邊的起點(diǎn)、終點(diǎn)標(biāo)簽信息建立每一類邊的起點(diǎn)位圖索引和終點(diǎn)位圖索引，然后對于某條邊<v，u>屬于某類<L₁，L₂>，v在所有標(biāo)簽是L₁的點(diǎn)中的第k名，則在<L₁，L₂>對應(yīng)的起點(diǎn)位圖索引第k列取值為1，u在所有標(biāo)簽是L₂的點(diǎn)中的第n名，則在這類邊的終點(diǎn)位圖索引第n列取值為1。

4.如權(quán)利要求3所述的方法，其特征在于每一類邊的起點(diǎn)數(shù)據(jù)直方圖和終點(diǎn)數(shù)據(jù)直方圖的建立方法為：設(shè)有n₁條邊屬于類<L₁，L₂>，且這n₁條邊的起點(diǎn)都為v，同時v為所有標(biāo)簽是L₁的點(diǎn)中的第k名，則在<L₁，L₂>對應(yīng)的起點(diǎn)數(shù)據(jù)直方圖第k列取值為n₁；同理，設(shè)有n₂條邊屬于類<L₁，L₂>，且這n₂條邊的終點(diǎn)都為u，同時u為所有標(biāo)簽是L₂的點(diǎn)中的第m名，則在<L₁，L₂>對應(yīng)的終點(diǎn)數(shù)據(jù)直方圖第m列取值為n₂。

5.如權(quán)利要求1所述的方法，其特征在于當(dāng)刪除一條邊時，首先找到所刪除的邊在B+-Tree中位置，然后在圖數(shù)據(jù)中予以刪除并重新統(tǒng)計(jì)邊的分布信息，用以更新這類邊的數(shù)據(jù)直方圖。

6.如權(quán)利要求5所述的方法，其特征在于當(dāng)從邊的統(tǒng)計(jì)信息中某個點(diǎn)不再含有該類的邊，則將該類邊的位圖索引的對應(yīng)位置變?yōu)?。

7.如權(quán)利要求1所述的方法，其特征在于當(dāng)新增一條邊時，首先找到所新增的邊在B+-Tree中位置，然后在圖數(shù)據(jù)中增加該邊并重新統(tǒng)計(jì)邊的分布信息，用以更新這類邊的數(shù)據(jù)直方圖；如果新增之后發(fā)現(xiàn)某個點(diǎn)從沒有該類的邊變成含有該類邊，則將該類別的位圖索引的對應(yīng)位置變?yōu)?。

8.如權(quán)利要求1所述的方法，其特征在于，當(dāng)更新一個點(diǎn)時，首先遍歷這個點(diǎn)可能在的所有的邊的類，然后更新這個點(diǎn)的所有的相關(guān)邊。