大規(guī)模數(shù)據(jù)圖的壓縮算法及圖操作算法研究.pdf

1、很多實(shí)際應(yīng)用問題中包含的信息可以抽象成圖，將實(shí)體抽象成點(diǎn)，實(shí)體間的相應(yīng)關(guān)系抽象成邊，解決好圖問題就可以很好地解決好與之對應(yīng)的實(shí)際問題。但是隨著數(shù)據(jù)量的累積，相應(yīng)的圖模型的規(guī)模也在逐漸變大，這就導(dǎo)致了很多傳統(tǒng)的算法在時(shí)間復(fù)雜度和空間復(fù)雜度方面都不能很好地解決這些問題。針對這個(gè)問題，圖壓縮應(yīng)運(yùn)而生，通過將圖的點(diǎn)或者邊進(jìn)行合并來降低圖的規(guī)模，在壓縮后的圖上進(jìn)行操作，進(jìn)而減少時(shí)間和空間消耗。基于以上觀點(diǎn)，本文提出點(diǎn)的樸素相似的概念，并運(yùn)用這個(gè)概

2、念來壓縮圖，通過邊編碼來記錄點(diǎn)與點(diǎn)之間的鄰接關(guān)系，保證壓縮過程為無損壓縮，即可以由壓縮圖還原出原始圖。同時(shí)，我們的壓縮方法保證得到的壓縮圖可以支持大部分的圖操作。
　　割點(diǎn)求解操作是圖的一個(gè)傳統(tǒng)操作，割點(diǎn)的存在與否決定著圖的連通性的好壞。本文將給出壓縮圖上的割點(diǎn)求解算法，即改進(jìn)的深度優(yōu)先搜索樹算法，通過在壓縮圖上運(yùn)行該算法，可以快速確定原圖中是否存在割點(diǎn)，若存在割點(diǎn)則快速、準(zhǔn)確地返回全部割點(diǎn)。三角列舉操作同樣被人們研究了好久，該操

3、作給出圖的全部大小為3的團(tuán)，即三角形，有助于更好地分析圖的內(nèi)部結(jié)構(gòu)。我們將給出壓縮圖上的三角列舉算法，通過在壓縮圖上運(yùn)行算法，可以快速、準(zhǔn)確地返回原圖中的全部的三角形。
　　當(dāng)今數(shù)據(jù)最大的特點(diǎn)是數(shù)據(jù)規(guī)模巨大和數(shù)據(jù)更新迅速，應(yīng)對好這兩個(gè)特點(diǎn)將會使相應(yīng)的問題得以很好地解決。壓縮算法的提出解決了數(shù)據(jù)規(guī)模巨大的問題，使得傳統(tǒng)的內(nèi)存算法在其上面運(yùn)行成為可能，但很多傳統(tǒng)的算法不能夠應(yīng)對數(shù)據(jù)更新迅速的特點(diǎn)，針對每次的更新傳統(tǒng)算法必須重新計(jì)算，這