數據流管理系統(tǒng)中的概要數據結構算法的研究和實現(xiàn).pdf

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

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

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