海量數(shù)據(jù)壓縮、操作和查詢處理方法的研究.pdf

1、隨著信息技術(shù)的發(fā)展及其在金融、交通、軍事、生態(tài)環(huán)境檢測(cè)、Web等領(lǐng)域的應(yīng)用日益深入，海量數(shù)據(jù)大量涌現(xiàn)，向數(shù)據(jù)庫(kù)研究者提出了新的挑戰(zhàn)。存儲(chǔ)介質(zhì)的價(jià)格/容量比的迅速下降以及數(shù)據(jù)壓縮方法的使用使得海量數(shù)據(jù)的存儲(chǔ)本身并不是問(wèn)題。問(wèn)題是：在有效存儲(chǔ)海量數(shù)據(jù)的同時(shí)如何有效地處理海量數(shù)據(jù)上查詢以及更新、刪除等操作。為此，研究者們開(kāi)始使用數(shù)據(jù)壓縮技術(shù)和數(shù)據(jù)庫(kù)技術(shù)來(lái)研究海量數(shù)據(jù)的管理問(wèn)題，產(chǎn)生了壓縮數(shù)據(jù)庫(kù)技術(shù)新研究領(lǐng)域。
　　本文以現(xiàn)有關(guān)系數(shù)據(jù)庫(kù)為

2、基礎(chǔ)，研究適于數(shù)據(jù)庫(kù)數(shù)據(jù)隨機(jī)存取方式的數(shù)據(jù)壓縮方法（包括索引壓縮方法、海量關(guān)系壓縮方法和適于特定數(shù)據(jù)庫(kù)應(yīng)用的海量關(guān)系壓縮方法）、適于壓縮數(shù)據(jù)庫(kù)的數(shù)據(jù)操作算法、適于壓縮數(shù)據(jù)庫(kù)的查詢優(yōu)化方法等。本文的主要研究結(jié)果如下：
　　提出了海量多屬性關(guān)系的拆分壓縮算法。證明了在海量關(guān)系中識(shí)別頻繁屬性組合是一個(gè)NP完全問(wèn)題，給出了識(shí)別頻繁屬性組合的貪心算法和遺傳算法，證明了拆分壓縮方法的完備性，給出了基于拆分壓縮的海量關(guān)系上的查詢處理方法。實(shí)驗(yàn)結(jié)

3、果表明拆分壓縮方法能夠有效地壓縮海量關(guān)系，并有效地提高數(shù)據(jù)庫(kù)的整體查詢性能。
　　提出了頻率向量索引結(jié)構(gòu)的一種壓縮方法，并為其設(shè)計(jì)了一種有效的存儲(chǔ)結(jié)構(gòu)，并對(duì)其壓縮比進(jìn)行了理論分析。理論分析和實(shí)驗(yàn)結(jié)果表明，這種壓縮的索引結(jié)構(gòu)能夠保證查詢結(jié)果的完備性并能有效地提高頻率向量的存儲(chǔ)和查詢效率。
　　針對(duì)數(shù)據(jù)庫(kù)中海量關(guān)系的離線存儲(chǔ)特點(diǎn)，給出了海量離線關(guān)系的壓縮技術(shù)并設(shè)計(jì)了相應(yīng)的數(shù)據(jù)操作算法，給出了這種壓縮技術(shù)在查詢處理時(shí)性能提高的理論

4、下界。理論分析和實(shí)驗(yàn)結(jié)果表明，這種壓縮技術(shù)能有效提高查詢海量離線數(shù)據(jù)的速度。
　　給出了一個(gè) DNA序列的壓縮方法并設(shè)計(jì)實(shí)現(xiàn)了適于該壓縮方法的存儲(chǔ)結(jié)構(gòu)。該方法能夠有效地壓縮DNA序列且其解壓縮時(shí)間是線性的，能夠節(jié)省DNA序列的存儲(chǔ)空間以及下載、傳播DNA序列時(shí)所需的網(wǎng)絡(luò)帶寬。
　　給出了壓縮多維數(shù)據(jù)倉(cāng)庫(kù)中兩個(gè)基于BUC思想的IceBerg Cube算法。這兩個(gè)算法可以在無(wú)需解壓縮地有效計(jì)算Iceberg Cube。算法利用h

5、aving條件中聚集函數(shù)的反單調(diào)性避免了大量不必要的計(jì)算。算法的輸入數(shù)據(jù)和中間臨時(shí)數(shù)據(jù)均以壓縮形式存在，計(jì)算過(guò)程中無(wú)需數(shù)據(jù)解壓縮，而且在計(jì)算過(guò)程中數(shù)據(jù)量迅速減小。實(shí)驗(yàn)結(jié)果表明，該算法的性能優(yōu)于先計(jì)算完整 Cube再利用having條件過(guò)濾產(chǎn)生Iceberg Cube的方法，且having條件中聚集函數(shù)能夠有效剪裁掉一些cuboid的計(jì)算。
　　提出通過(guò)對(duì)查詢緩沖池內(nèi)的查詢進(jìn)行調(diào)度，根據(jù)查詢反饋結(jié)果來(lái)建立和維護(hù)自適應(yīng)直方圖，有效跟蹤