數(shù)據(jù)流管理系統(tǒng)中的概要數(shù)據(jù)結(jié)構(gòu)算法的研究和實現(xiàn).pdf

1、近年來，在金融服務(wù)、網(wǎng)絡(luò)監(jiān)控、電信數(shù)據(jù)管理及傳感器檢測等領(lǐng)域中，出現(xiàn)了一類新的數(shù)據(jù)密集型應(yīng)用。這類應(yīng)用的特征是：數(shù)據(jù)以大量、快速、時變的數(shù)據(jù)流形式持續(xù)到達(dá)，所以數(shù)據(jù)不宜用持久穩(wěn)定關(guān)系建模，而適合用數(shù)據(jù)流建模。論文在研究目前國際上最新的數(shù)據(jù)流管理技術(shù)的基礎(chǔ)上，介紹了東南大學(xué)自行開發(fā)的基于硬件預(yù)處理器的數(shù)據(jù)流管理系統(tǒng)原型SEIJSTREAM的體系結(jié)構(gòu)和一種可以支持對數(shù)據(jù)流上進(jìn)行持續(xù)查詢的查詢語言X-SQL。 在很多實際應(yīng)用中，例

2、如決策支持系統(tǒng)、查詢優(yōu)化等，用戶并不需要獲得確切值，而僅需要一個近似值。因此，設(shè)計單遍掃描算法(one-pass algorithm)，實時地給出近似查詢結(jié)果就成為數(shù)據(jù)流模型下數(shù)據(jù)處理的目標(biāo)。算法的關(guān)鍵在于設(shè)計一個遠(yuǎn)小于數(shù)據(jù)集規(guī)模的結(jié)構(gòu)，從而可以在內(nèi)存中處理數(shù)據(jù)。相對于數(shù)據(jù)流的規(guī)模而言，這種名為概要數(shù)據(jù)結(jié)構(gòu)(synopsis data structure)的規(guī)模至少是次線性的。 小波變換大綱作為高效的數(shù)據(jù)壓縮還原技術(shù)引起了數(shù)

3、據(jù)流領(lǐng)域的高度關(guān)注。論文詳細(xì)介紹了哈爾小波的變換過程，并且引入了誤差樹的概念對這個變換過程進(jìn)行了詳細(xì)的分析。在此基礎(chǔ)上實現(xiàn)了用哈爾小波方法生成概要數(shù)據(jù)結(jié)構(gòu)的算法，選用了不同的固定閾值并進(jìn)行了性能測試，實驗表明不同的壓縮率導(dǎo)致了重構(gòu)數(shù)據(jù)與原始數(shù)據(jù)存在一定的誤差。同時基于測試結(jié)果分析了固定閾值方案的不足之處，數(shù)據(jù)重建的質(zhì)量變化很大，并且對于單獨(dú)的近似解答缺少特別的質(zhì)量保證。在此基礎(chǔ)上提出并實現(xiàn)了基于概率的可變閾值的小波變換，比較好地解決了這