發(fā)布時(shí)間：2017-12-24 04:03

  本文關(guān)鍵詞：支持查詢的大規(guī)模圖數(shù)據(jù)無損壓縮　出處：《華東師范大學(xué)》2017年博士論文　論文類型：學(xué)位論文

  更多相關(guān)文章： 圖數(shù)據(jù) 圖數(shù)據(jù)流 無損壓縮 圖數(shù)據(jù)查詢 三角形列表

【摘要】：圖數(shù)據(jù)模型,簡(jiǎn)稱圖數(shù)據(jù),是表示實(shí)體和實(shí)體間聯(lián)系的數(shù)據(jù)模型。和結(jié)構(gòu)化的關(guān)系模型數(shù)據(jù)以及非結(jié)構(gòu)化數(shù)據(jù)相比,圖數(shù)據(jù)表達(dá)形式多樣、靈活,且易于實(shí)現(xiàn)。隨著互聯(lián)網(wǎng)技術(shù)和各種數(shù)據(jù)收集和傳輸技術(shù)的發(fā)展,越來越多的數(shù)據(jù)以圖的形式建模,以表示互聯(lián)網(wǎng)中不同結(jié)點(diǎn)、不同用戶、不同實(shí)體之間的聯(lián)系。同時(shí),搜索引擎、社交網(wǎng)絡(luò)服務(wù)、科學(xué)數(shù)據(jù)分析、知識(shí)圖譜分析等應(yīng)用中所需要管理的圖數(shù)據(jù)規(guī)模也越來越大。而目前大部分圖數(shù)據(jù)處理算法往往需要將整個(gè)數(shù)據(jù)集存放在內(nèi)存進(jìn)行分析。所以,如何減少圖數(shù)據(jù)處理的所需要存儲(chǔ)空間容量是圖數(shù)據(jù)管理的重要問題,而圖數(shù)據(jù)壓縮是解決這一問題的主要手段之一。圖數(shù)據(jù)壓縮不僅需要考慮壓縮率,即壓縮后數(shù)據(jù)與原始數(shù)據(jù)規(guī)模的比值,還需要考慮壓縮方法的運(yùn)行效率。另一方面,在對(duì)壓縮后的數(shù)據(jù)進(jìn)行處理時(shí),如何避免不必要的解壓縮操作,支持各類圖數(shù)據(jù)查詢,提升圖數(shù)據(jù)處理效率,也至關(guān)重要。針對(duì)以上問題,本文研究支持查詢的大規(guī)模圖數(shù)據(jù)的無損壓縮方法。具體而言,本文的貢獻(xiàn)包括以下三點(diǎn):·提出了一種基于三角形列表的靜態(tài)圖數(shù)據(jù)無損壓縮方法,bound-tri方法。此方法利用圖數(shù)據(jù)中大量存在的三角形子圖,合并這些三角形子圖中的公共結(jié)點(diǎn),對(duì)圖數(shù)據(jù)進(jìn)行無損壓縮。bound-tri方法在三角形列表的過程中過濾了圖數(shù)據(jù)中度較高的一批結(jié)點(diǎn),使得需要壓縮的圖數(shù)據(jù)的規(guī)模減少,從而降低圖數(shù)據(jù)的壓縮時(shí)間。同時(shí),bound-tri方法還確保了在三角形列表的結(jié)果中只冗余較少的邊,并得到一個(gè)壓縮率較高的壓縮結(jié)果。bound-tri方法還允許用戶在壓縮時(shí)設(shè)置不同的結(jié)點(diǎn)度過濾參數(shù)來平衡圖數(shù)據(jù)壓縮的壓縮率、壓縮時(shí)間,以及壓縮結(jié)果對(duì)反饋圖數(shù)據(jù)查詢的效率。本文所介紹的bound-tri方法可以對(duì)大規(guī)模圖數(shù)據(jù),尤其是社交網(wǎng)絡(luò)圖,實(shí)現(xiàn)高效率的無損壓縮。此方法相較大部分已有的圖數(shù)據(jù)無損壓縮方法有著較高的壓縮率和較短的壓縮時(shí)間�！ぬ岢隽艘环N針對(duì)圖數(shù)據(jù)流形式逐步生成的圖數(shù)據(jù)的無損壓縮方法,STT方法。STT方法利用圖數(shù)據(jù)流中在短時(shí)間內(nèi)多次輸人的結(jié)點(diǎn)以及連接這些結(jié)點(diǎn)的邊,對(duì)圖數(shù)據(jù)流進(jìn)行無損壓縮。STT方法在限定大小的緩存中盡可能地使高熱度結(jié)點(diǎn)以及包含有這些結(jié)點(diǎn)的邊或三角形集合存活,并在緩存中利用三角形列表算法盡可能多地將圖數(shù)據(jù)流中的三角形子圖組成三角形集合,實(shí)現(xiàn)了較高的壓縮率以及較高的數(shù)據(jù)流吞吐量。同時(shí),在圖數(shù)據(jù)流的壓縮結(jié)果中存在一定數(shù)量的三角形集合,這可以滿足對(duì)圖數(shù)據(jù)查詢的無解壓快速反饋需求。并使相鄰時(shí)間段內(nèi)輸入的結(jié)點(diǎn)盡可能地被包含在一個(gè)或極少數(shù)個(gè)不同的三角形集合中。STT方法在壓縮時(shí)無需輸入完整的圖數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)或全部圖數(shù)據(jù)內(nèi)容信息。同樣地,用戶可以通過參數(shù)調(diào)整緩存更新的更新效率,對(duì)不同速率的圖數(shù)據(jù)流進(jìn)行壓縮,或是通過降低一部分的圖數(shù)據(jù)的壓縮率,提高圖數(shù)據(jù)流壓縮的吞吐量。STT方法相較目前的靜態(tài)圖數(shù)據(jù)壓縮方法,可以得到與RVE、Re-Pair和VNM等經(jīng)典的圖數(shù)據(jù)壓縮方法近似壓縮率的圖數(shù)據(jù)壓縮結(jié)果,卻可以在圖數(shù)據(jù)逐步到達(dá)時(shí)即開始?jí)嚎s操作,極大地提升了壓縮效率�！ぬ岢隽嗽谝褖嚎s圖數(shù)據(jù)結(jié)果中執(zhí)行鄰接結(jié)點(diǎn)查詢、k-距離結(jié)點(diǎn)查詢、共同鄰接結(jié)點(diǎn)查詢這三類基本查詢的處理算法。這些算法都保證了不需要對(duì)基于三角形子圖進(jìn)行壓縮的圖數(shù)據(jù)進(jìn)行解壓縮即可返回查詢結(jié)果。經(jīng)bound-tri方法和STT方法壓縮得到的圖數(shù)據(jù)中包含大量的三角形子圖,且這些子圖可以被直接地提取出來,利用這些三角形子圖中相互連接的結(jié)點(diǎn)以及結(jié)點(diǎn)間的邊,能實(shí)現(xiàn)無需解壓的查詢反饋。從而在獲得容量較小的圖數(shù)據(jù)壓縮結(jié)果的同時(shí),避免了昂貴的解壓縮操作�；谶@些算法,可以實(shí)現(xiàn)社交網(wǎng)絡(luò)數(shù)據(jù)抽樣、用戶推薦、謠言傳播分析等圖數(shù)據(jù)分析任務(wù)。目前,經(jīng)大部分圖數(shù)據(jù)壓縮方法壓縮得到的圖數(shù)據(jù),如SLAHSHBURN、BV框架及κκ2-partitioned等方法,均需要在反饋查詢時(shí)部分或完全地解壓圖數(shù)據(jù)。綜上所述,本文從圖數(shù)據(jù)壓縮問題出發(fā),在靜態(tài)圖數(shù)據(jù)及圖數(shù)據(jù)流這兩類環(huán)境中分別對(duì)大規(guī)模圖數(shù)據(jù)中進(jìn)行無損壓縮的問題進(jìn)行了研究分析。本文圖數(shù)據(jù)中大量存在的三角形子圖并利用結(jié)點(diǎn)合并的方法,實(shí)現(xiàn)高效的圖數(shù)據(jù)壓縮。在靜態(tài)圖數(shù)據(jù)環(huán)境中,在壓縮過程中過濾度較高的結(jié)點(diǎn)并對(duì)其余結(jié)點(diǎn)進(jìn)行了三角形列表計(jì)算,實(shí)現(xiàn)了較高的壓縮率以及較短的壓縮時(shí)間。在圖數(shù)據(jù)流的環(huán)境中,則在數(shù)據(jù)流緩存中保持高熱度結(jié)點(diǎn)的存活時(shí)間,從圖數(shù)據(jù)流中列出更多的三角形子圖,在圖數(shù)據(jù)存儲(chǔ)到本地存儲(chǔ)空間前,實(shí)現(xiàn)對(duì)圖數(shù)據(jù)的壓縮。另外,本文還研究了在已壓縮的圖數(shù)據(jù)中的查詢處理算法,證明了基于三角形子圖壓縮的圖數(shù)據(jù),如經(jīng)bound-tri方法和STT方法壓縮的圖數(shù)據(jù),可以在無需解壓縮的情況下對(duì)幾類常用的圖數(shù)據(jù)查詢快速返回查詢結(jié)果。對(duì)多個(gè)真實(shí)的大規(guī)模圖數(shù)據(jù)集的壓縮實(shí)驗(yàn)以及和同類方法的對(duì)比表明,本文所提出的方法在壓縮率、壓縮效率(壓縮時(shí)間或數(shù)據(jù)流壓縮吞吐量),查詢支持這三個(gè)方面,具有整體性優(yōu)勢(shì)。
【學(xué)位授予單位】：華東師范大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 吳國(guó)清;陳虹;;一種科學(xué)數(shù)據(jù)無損壓縮方法[J];計(jì)算機(jī)工程與應(yīng)用;2006年05期

2 沈蘭蓀,魏海;圖像的無損壓縮研究[J];數(shù)據(jù)采集與處理;1999年04期

3 毋清明;;迎戰(zhàn)!無損壓縮挑戰(zhàn)極限![J];電腦愛好者;2006年11期

4 李平,李偉光;醫(yī)學(xué)圖像視覺無損壓縮的研究[J];長(zhǎng)春理工大學(xué)學(xué)報(bào);2005年03期

5 黃祥林;楊麗芳;;一種提高圖像無損壓縮效率的方法[J];電路與系統(tǒng)學(xué)報(bào);2007年03期

6 劉方;一種數(shù)據(jù)無損壓縮技術(shù)的研究[J];南京航空航天大學(xué)學(xué)報(bào);1995年06期

7 王軍;;基于譜間和幀內(nèi)差分脈沖編碼調(diào)制的超光譜圖像無損壓縮[J];中國(guó)光學(xué);2013年06期

8 api;纖塵去盡還本真——無損壓縮音頻格式巡禮(下)[J];電腦;2004年11期

9 孫自廣;古天龍;;一種基于代數(shù)決策圖的多值圖像無損壓縮方法[J];桂林電子工業(yè)學(xué)院學(xué)報(bào);2006年02期

10 李龍;周頑;;數(shù)字圖像無損壓縮[J];軟件導(dǎo)刊;2007年07期

相關(guān)會(huì)議論文 前6條

1 陳虹;宋磊;吳國(guó)清;;大規(guī)模數(shù)值模擬數(shù)據(jù)的無損壓縮[A];中國(guó)工程物理研究院科技年報(bào)（2005）[C];2005年

2 趙國(guó)毅;楊曉春;王斌;;面向相似數(shù)據(jù)的無損壓縮技術(shù)[A];NDBC2010第27屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集A輯二[C];2010年

3 陳蘊(yùn)智;舒忠;;報(bào)業(yè)網(wǎng)絡(luò)版數(shù)據(jù)無損壓縮安全傳輸系統(tǒng)[A];第十三屆全國(guó)包裝工程學(xué)術(shù)會(huì)議論文集[C];2010年

4 王振海;;基于DSP的高速數(shù)據(jù)流無損壓縮方法的研究[A];2007通信理論與技術(shù)新發(fā)展——第十二屆全國(guó)青年通信學(xué)術(shù)會(huì)議論文集（下冊(cè)）[C];2007年

5 顏彥;郭興明;李立策;王景燦;;基于LZ77壓縮算法的ECG信號(hào)無損壓縮在DSP上的實(shí)現(xiàn)[A];中國(guó)生物醫(yī)學(xué)工程進(jìn)展——2007中國(guó)生物醫(yī)學(xué)工程聯(lián)合學(xué)術(shù)年會(huì)論文集（上冊(cè)）[C];2007年

6 蔣宏;潘登;劉荻;孫志明;劉爾梅;;哈爾濱醫(yī)科大學(xué)第一臨床醫(yī)學(xué)院PACC系統(tǒng)一期工程總結(jié)[A];首屆中國(guó)IT與醫(yī)藥衛(wèi)生高層論壇論文集[C];2004年

相關(guān)重要報(bào)紙文章 前4條

1 湖南 古銅;無損壓縮CD之APE[N];電腦報(bào);2003年

2 李劍峰;影音不分家，無損音頻知多少?[N];電腦報(bào);2014年

3 通訊員聶小清;電話線就能當(dāng)寬帶用[N];科技日?qǐng)?bào);2002年

4 李霞;加快多媒體系統(tǒng)的研究與發(fā)展[N];甘肅日?qǐng)?bào);2003年

相關(guān)博士學(xué)位論文 前2條

1 張O，

本文編號(hào)：1326772