調査と解説

データ量を削減して CPU 負荷やメモリ負荷を減少させるために，つぎのようなさまざまな方法が使用される [Bab 02]． いずれの方法を使用するかは，データの解析にあたってどのようなデータ・ストリーム・マイニングの技法を使用するかに依存する [Gab 05]．

集約

集約 (aggregation) とは，共通の属性をもつストリーム要素をまとめることをいう． まとめるための代表的な方法としてヒストグラム [Sou 04] がある． すなわち，共通の属性をもつものを計数する方法がある．

負荷間引

負荷間引 (load shedding) [Sob 07] とは，ストリーム要素をまびくことによってデータを削減することをいう． まびくための代表的な方法として 2.3.2 項においてものべたサンプリング [Cla 93] [Duf 04] がある． ネットワーク上の複数の地点でサンプリングをおこなうとき，軌跡サンプリ ング (trajectory sampling) [Duf 01] という方法を使用することによって，各地点において同一のトラフィックを選択することができる．

スケッチまたは概要

ストリーム要素をまとめるための集約より高度な方法として，スケッチ (sketch) 別名は概要 (synopsis) [Gil 01] [Alo 96] [Alo 99] がある． スケッチにおいては，目的とする演算に必要な情報を圧縮されたかたちでもつ概要データ構造を入力データからつくる． すなわち，その演算に必要のない情報を廃棄することによってデータ量の削減をはかる．

ウェイブレット

フーリエ変換が時間によらない正弦波を使用した変換であるのに対して，ウェイブレット変換 (wavelet transformation) は一定範囲の時間だけ 0 でない値をもつ関数 (すなわち wavelet) を使用した類似の変換である． ウェイブレットを使用するデータ削減法 [Hua 01] [Cha 00] においては，入力データを時系列とみなし，それをウェイブレット変換した結果を概要として保存する (ウェイブレットは概要の一種ともみなすことができる)． SQL によって記述されるようなクエリは，この概要に適用することによって近似された解をえることができる．

これらのデータ削減法のおおくはストリーム・データ処理以前に，データベースに関連するさまざまな研究，たとえば OLAP (On-line Analytical Processing，オンライン分析処理)，DSS (Decision Support System，意思決定支援システム) の研究のなかで開発されてきた． なお，これらの方法の うち，サンプリングや概要においては乱数やハッシングが重要なやくわりをはたす． また，データを削減するわけではないが，平均スループットはたかくても入力がバーストする，すなわち一時的にスループットをこえるときには，バッファリングによって入力を平均化する方法もある (Babcock ら [Bab 02] はこの方法を batch processing と呼んでいる)．

参考文献

• [Alo 96] Alon, N., Matias, Y., and Szegedy, M., “The Space Complexity of Approximating the Frequen-cy Moments”, 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 20–29, 1996.
• [Alo 99] Alon, N., Matias, Y., and Szegedy, M., “The Space Complexity of Approximating the Frequen-cy Moments”, Journal of Computer and System Sciences, Vol. 58, No. 1, pp. 137–147, February 1999.
• [Bab 02] Babcock, B., Babu, S., Datar, M., Motwani, R., and Widom, J., “Models and Issues in Data Stream Systems”, 21st ACM Symposium on Principles of Database Systems (PODS 2002), 2002.
• [Cha 00] Chakrabarti, K., Garofalakis, M. N., R., Rastogi, and Shim, K., “Approximate Query Processing Using Wavelets”, 26th Int’l Conference on Very Large Data Bases, pp. 11–122, 2000.
• [Cla 93] Claffy, K. C., Polyzos, G. C., and Braun, H.-W., “Application of Sampling Methodologies to Network Traffic Characterization”, Applications, Technologies, Architectures, and Protocols for Com-puter Communication (SIGCOMM’93), pp. 194–203, 1993.
• [Duf 01] Duffield, N. G. and Grossglauser, M., “Trajectory Sampling for Direct Traffic Observation”, IEEE/ACM Transactions on Networking, Vol. 9, No. 3, pp. 280–292, Jun 2001.
• [Duf 04] Duffield, N., “Sampling for Passive Internet Measurement: A Review”, Statistical Science, Vol. 19, No. 3, pp. 472–498, 2004.
• [Gab 05] Gaber, M. M., Zaslavsky, A., and Krishnaswamy, S., “Mining Data Streams: A Review”, ACM SIGMOD Record, Vol. 34 , No. 2, pp. 18–26, June 2005.
• [Gil 01] Gilbert, A., Kotidis, Y., Muthukrishnan, S., and Strauss, M., “QuickSAND: Quick Summary and Analysis of Network Data”, DIMACS Technical Report, 2001-43, November 2001.
• [Hua 01] Huang, P., Feldmann, A., and Willinger, W., “A Non-instrusive, Wavelet-based Approach to Detecting Network Performance Problems”, 1st ACM SIGCOMM Workshop on Internet Measurement (IMW’01), pp. 213–227, 2001.
• [Sob 07] Søberg, J., Hernes, K. H., Siekkinen, M., Goebel, V., and Plagemann, T., “A Practical Evalua-tion of Load Shedding in Data Stream Management Systems for Network Monitoring”, 1st European Workshop on Data Stream Analysis (WDSA’07), March 2007.
• [Sou 04] Soule, A., Salamatia, K., Taft, N., Emilion, R., and Papagiannaki, K., “Flow Classification by Histograms, or How to Go on Safari in the Internet”, Joint Int’l Conference on Measurement and Modeling of Computer Systems (SIGMETRICS/Performance’04), pp. 49–60, 2004.