基于草圖的分布式數(shù)據(jù)流聚集查詢的研究

摘要：討論了基于草圖的復雜聚集查詢的近似處理算法。利用隨機技術，在數(shù)據(jù)流過時實時計算數(shù)據(jù)的草圖概要；同時采用了新穎的草圖分割技術，有效地提高近似應答的精度。合成數(shù)據(jù)的查詢實驗表明草圖技術能有效地降低估算誤差。

關鍵詞：草圖概要；近似應答；聚集查詢；草圖分割

中圖分類號：TP391文獻標志碼：A

文章編號：1001－3695(2007)05－0041－03

近年來，在傳感器網(wǎng)絡、網(wǎng)絡監(jiān)控、通信數(shù)據(jù)管理、股票分析等應用領域中出現(xiàn)的數(shù)據(jù)流是大量的、連續(xù)的、隨時間變化的、無限制的數(shù)據(jù)序列，如關系元組、網(wǎng)絡性能參數(shù)、電話記錄、傳感器讀入值等。它們連續(xù)到達，需要連續(xù)處理。由于流數(shù)據(jù)量大且到達速度快，傳統(tǒng)數(shù)據(jù)庫技術難以實現(xiàn)及時處理。數(shù)據(jù)流是無限的，許多歷史數(shù)據(jù)已被丟棄，而傳統(tǒng)的關系系統(tǒng)中的聚集查詢操作（Count、Sum、Avg等）等需要訪問關系的全部數(shù)據(jù)才能輸出結果。如何對數(shù)據(jù)流的復雜聚集操作作近似應答成為目前數(shù)據(jù)流領域研究的難點問題。

目前解決聚集操作的一個常用方法是在數(shù)據(jù)流上定義時間窗口，將無限的數(shù)據(jù)流限制在一個有限的范圍內。然而，時間窗口只關注最近通過的數(shù)據(jù)流，并且當數(shù)據(jù)流流速發(fā)生變化時，如何改變時間窗口的大小來適應流速的變化始終是尚未解決的問題。Alon等人[1]介紹了隨機草圖的概念，F(xiàn)lajolet 和Martin介紹了用草圖技術估算數(shù)據(jù)項不同值的數(shù)量F0的方法。但這些算法需要非常強的獨立屬性的顯式哈希函數(shù)族。 

本文討論了基于草圖的復雜聚集查詢的近似處理算法，利用隨機技術在數(shù)據(jù)流過時實時計算數(shù)據(jù)的草圖概要。同時采用了新穎的草圖分割技術，通過以下兩個方面有效地提高近似應答的精度：①屬性值域的智能分割，使分割后的自連接規(guī)模最小；②為分割后的獨立草圖公平地分配存儲空間。

1分布式數(shù)據(jù)流處理模型

3實驗 

實驗利用文獻［3］的合成數(shù)據(jù)發(fā)生器來生成帶有三個屬性的關系，所產(chǎn)生的元組沿區(qū)間分布。將基于草圖方法和傳統(tǒng)的基于直方圖的方法作比較驗證本文算法的有效性，尤其是檢驗草圖分割對計算近似查詢的影響。對聚集查詢值用相對誤差(|actual-approx|/actual)來作為近似查詢應答精度的度量標準。圖2描述了草圖和直方圖在自連接查詢中，隨可用存儲空間數(shù)量增加所得的誤差。可觀察到草圖的相對誤差幾乎比直方圖要少一個數(shù)量級。圖2的自連接查詢是基于單個關系、單個屬性自連接的查詢，其值域大小為102 400，包含有10 000個區(qū)間。直方圖的結果很差，因為在如此大而稀疏的多區(qū)間值域中，一些桶無法準確地捕捉到數(shù)據(jù)的分布特性。圖3給出了草圖分割的鏈連接查詢估算精度。它由三個二維關系組成，中心關系的兩個屬性與其他兩個關系的一個屬性連接。圖3說明了兩個趨勢：①隨著草圖分區(qū)數(shù)量的增加，聚集查詢估算的相對誤差減小；②當桶數(shù)量增加，直方圖更精確時，根據(jù)減少的誤差來計算草圖分割就更有效。

4小結

利用草圖技術解決復雜的分布式數(shù)據(jù)流的近似查詢是個正在探索的新領域。本文討論了分布式流處理模型、隨機草圖概要及基于草圖的聚集查詢的近似算法，并采用新穎的草圖分解技術來獲得更好的查詢精度。

參考文獻：

［1］ALON N，MATIAS Y，SZEGEDY M. The space complexity of approxi－mating the frequency moments:proceedings of the 28th ACM STOC Symposium on the Theory of Computing[C].[S.l.]:[s.n.]，1996:20－29. 

[2]DOBRA A，GAROFALAKIS M，GEHRKE J，et al. Processing complex aggregate queries over data streams:ACM SIGMOD International on Mogement of Data[C].New York:ACM Press，2002:61－72. 

[3]VITTER J S，WANG Min. Approximate computation of multidimensional aggregates of sparse data using wavelets:proceedings of the ACM SIGMOD International Conference on Management of Data[C].New York:ACM Press，1999:193－204.

[4]GEHRKE J，KORN F，SRIVASATAVA D. On computing correlated aggregates over continual data streams:proc. of the ACM SIGMOD Intermational Conference on Management of Data[C].New York:ACM Press，2001:13－24.

[5]CHAUDHURI S，DAYAL U.An overview of data warehousing and OLAP technology[J].ACM SIGMOD Record，1997，26(1):65－74.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”