圖的處理方法、裝置以及柵格化表示及存儲方法

基本信息

申請?zhí)?/td> CN201510347734.1 申請日 -
公開（公告）號 CN104952032A 公開（公告）日 2015-09-30
申請公布號 CN104952032A 申請公布日 2015-09-30
分類號 G06T1/00(2006.01)I;G06T1/60(2006.01)I 分類 計算；推算；計數(shù);
發(fā)明人 朱曉偉;韓文弢;陳文光 申請（專利權(quán)）人 深圳神圖科技有限公司
代理機(jī)構(gòu) 北京睿邦知識產(chǎn)權(quán)代理事務(wù)所（普通合伙） 代理人 清華大學(xué);北京費(fèi)馬科技有限公司;深圳神圖科技有限公司
地址 100084 北京市海淀區(qū)清華大學(xué)
法律狀態(tài) -

摘要

摘要 提供了圖的處理方法、裝置以及柵格化表示及存儲方法。圖的處理方法包括：將原始圖處理為柵格式結(jié)構(gòu)；以及流式處理各個邊分組，其中對于每個邊分組，按照預(yù)定的處理函數(shù)逐個對邊分組中的邊進(jìn)行處理，其中，從慢速存儲設(shè)備將該邊分組的數(shù)據(jù)讀入快速存儲設(shè)備中，以及將起始頂點(diǎn)分組的數(shù)據(jù)和目標(biāo)頂點(diǎn)分組的數(shù)據(jù)讀入快速存儲設(shè)備中。還可以針對“高速緩存－內(nèi)存－磁盤”的三層存儲器結(jié)構(gòu)，預(yù)處理時根據(jù)高速緩存大小執(zhí)行首次劃分，執(zhí)行時根據(jù)內(nèi)存大小以合并柵格的方式執(zhí)行虛擬的二次劃分。本發(fā)明的對圖的柵格化表示中對邊的順序沒有要求，計算開銷小，在流式處理中，能夠?qū)⑾嚓P(guān)的頂點(diǎn)分組載入快速存儲設(shè)備，保證了頂點(diǎn)的讀寫局部性。