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

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

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

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