数据流上的异常检测
|
摘要
近年来，由于来自实际应用中的需求的推动，数据流上的异常检测技术的研究已经受到了学术界和工业界的越来越多的重视。数据流上的异常检测在金融风险分析、通信网监测、网络流量管理、趋势分析、Web日志分析、网络入侵检测、传感器网络管理等领域具有广泛的应用。例如，为了调节电信网络的性能，需要对电信网中的数据流进行监测，其检测异常的准确性对电信网络的正常运行是至关重要的。同样的应用场景也存在于高速公路上的交通管理，相关趋势的分析和预测，网页点击流的分析，信息系统的入侵检测以及传感器网络的管理等。在这些场景中，有相当一部分应用需要及时地对任务进行处理，以获得尽可能短的响应时间。
然而，传统的数据库技术是用来管理静态数据集的，其很难直接被用于对动态数据的实时监测和挖掘。因此，为了实时地监测数据流，需要采用伸缩性强的异常检测算法在有限的时间内处理大量的数据流。在对数据流的处理中，最大的挑战就是要在有限的内存空间，需要顺序的单遍扫描算法，并且要实时返回精确的结果。本文综述了国际上关于数据流异常检测的研究成果，在分析了现有研究工作的基础上，提出了异常的定义和数据流上异常检测要研究的问题，以及异常检测系统的框架。在对数据流上异常检测的研究过程中，本文的主要贡献有如下三个方面：
1．提出了自适应的突变的定义，自适应的突变更加全面地概括了数据流上的突变信息，并且排除了颠簸数据的干扰。根据该定义，本文又提出了三种突变检测方法，其中包括False Positive，False Negative和综合突变检测算法，这些算法能够保证以高于用户指定的准确率检测数据流上的突变，而且这些算法既能检测单调聚集函数值的突变，又能检测非单调聚集函数值的突变。突变检测算法所依赖的是本文提出的倒置桶序列的直方图(简称IH)。这种新颖的直方图技术具有较小的时间复杂度O(n((log n+log R)/(log(1+δ)))和空间复杂度O(n((log n+log R)/(log(1+δ)))，并能为突变检测提供准确的聚集查询支持，因此与现有直方图技术相比更加适用于数据流上的突变检测。
2．提出了基于单调搜索空间的突变检测算法。首先，提出了数据流上的单调搜索空间的构建算法及改进后的构建算法，从而对实际应用中的近似分形数据进行了分形变换，使得滑动窗口的错排序误差err_(MS)为0。其次，基于单调的搜索空间设计了突变检测算法。该算法能将突变检测处理时间复杂度从O(m)降为O(log m)，m为需要被检测的滑动窗口数目。最后，分析并给出了基于单调搜索空间的突变检测方法的误差界限，使得本文提出的突变检测算法具有理论上的误差上限的保证。
3．提出了基于分段分形模型的无参数异常检测算法。首先，本文提出了最优的分段分形模型以及数据流上的近似最优分段分形模型。利用近似最优的分段分形模型为长为n的数据流建模的时间复杂度为O(n log n)，空间复杂度为O(log n)。第二，提出了基于分段分形模型的突变检测算法，该算法在分段分形模型具有理论误差界限保证的前提下，能够准确地检测数据流上的突变。第三，本文提出了无参数的异常检测算法。该算法能够在最合适尺寸的滑动窗口上检测异常的情况，不需要用户设定任何参数，也不需要使用训练数据。使用该算法在数据流上检测异常的时间复杂度仅为O(n)，空间复杂度仅为O(1)。
综上所述，本文针对现有异常检测中存在的三类问题，分别提出了从问题定义、概要数据结构到异常检测算法的完整方案，并提出了以本文技术为核心的异常检测系统框架。理论分析和实验结果表明，与已有的研究成果相比，本文给出的异常检测方法具有较高的精度和较低的时间、空间复杂度，更加适用于数据流的应用场景：金融风险分析、通信网监测、网络流量管理、趋势分析、Web日志分析、网络入侵检测、传感器网络管理等。
Recently, real-time monitoring and online data mining over data streams have been attracting more and more research attention in database research community because of its wide variety of real world applications. For instance, it is very important to monitor the data streams for telecommunication network performance tuning, highway traffic management, trend-related prediction analysis, web-click streams analysis, information system intrusion detection, and sensor networking, etc. Some of these tasks are mission critical which require fast response.
Conventional database techniques were initially invented to manage static data collections, which can not be applied directly to monitor or mine dynamic data streams. Hence a robust and efficient anomaly detection is needed to process huge amount of information in a constrained time period, in order to online monitor the data stream. The most important constraints or requirements for the data stream processing include limited memory availability, sequentially linear scanning, and online accurate result report over evolving data streams. However, existing methods on anomaly detection suffer several problems. Our major contributions in this paper are as follows.
1. A novel concept of adaptive aggregation burst is introduced for precisely modelling real-life data streams. This burst model empowers users to detect double-side relative bursts dynamically without disturbed by bumps. We propose a framework for accurately detecting such bursts under false positive and false negative constraints. The algorithms are developed based on a space and time efficient histogram, IH, which can be maintained with O(n(logn+logR/log(1+δ))) time and O(logn+logR/log(1+δ)) space. Thus IH is more suitable for burst detection than other popular histograms.
2. A monotonic search space based burst detection method is proposed. Firstly, the monotonic search space building algorithms are proposed for transforming
real life data. With the fractal transforming, the miss sorting error err_(MS) can be guaranteed 0. To construct such a monotonic search space for multi-window burst detection, a novel approach is presented, which could decrease the time overhead of query processing from O(m) to O(logm), where m is the number of windows being monitored.
3. Propose a parameter-free anomaly detection algorithm in this paper. We first introduce the piecewise fractal model (PFM) for data stream processing, which consumes O(n log n) time and O(logn) space to model a n length stream. Based on this model, a burst detection algorithm is proposed which can provide accurate burst detection. A novel PFM based method is proposed for anomaly detection. This algorithm consumes only O(1) memory and O(n) time without involving training process.
This paper give a survey on the state of art anomaly detection over data streams. Based on the analysis of existing research works, a more general definition of anomaly and existing problems are proposed. This paper also propose a system architecture for anomaly detection over data streams which integrates the novel anomaly detection techniques proposed in this paper. Theoretical analysis and experimental results show that this algorithm can achieve higher precision with less space and time complexity as compared with the existing methods, and it could be concluded that the proposed algorithm is suitable for burst detection over data streams.
然而，传统的数据库技术是用来管理静态数据集的，其很难直接被用于对动态数据的实时监测和挖掘。因此，为了实时地监测数据流，需要采用伸缩性强的异常检测算法在有限的时间内处理大量的数据流。在对数据流的处理中，最大的挑战就是要在有限的内存空间，需要顺序的单遍扫描算法，并且要实时返回精确的结果。本文综述了国际上关于数据流异常检测的研究成果，在分析了现有研究工作的基础上，提出了异常的定义和数据流上异常检测要研究的问题，以及异常检测系统的框架。在对数据流上异常检测的研究过程中，本文的主要贡献有如下三个方面：
1．提出了自适应的突变的定义，自适应的突变更加全面地概括了数据流上的突变信息，并且排除了颠簸数据的干扰。根据该定义，本文又提出了三种突变检测方法，其中包括False Positive，False Negative和综合突变检测算法，这些算法能够保证以高于用户指定的准确率检测数据流上的突变，而且这些算法既能检测单调聚集函数值的突变，又能检测非单调聚集函数值的突变。突变检测算法所依赖的是本文提出的倒置桶序列的直方图(简称IH)。这种新颖的直方图技术具有较小的时间复杂度O(n((log n+log R)/(log(1+δ)))和空间复杂度O(n((log n+log R)/(log(1+δ)))，并能为突变检测提供准确的聚集查询支持，因此与现有直方图技术相比更加适用于数据流上的突变检测。
2．提出了基于单调搜索空间的突变检测算法。首先，提出了数据流上的单调搜索空间的构建算法及改进后的构建算法，从而对实际应用中的近似分形数据进行了分形变换，使得滑动窗口的错排序误差err_(MS)为0。其次，基于单调的搜索空间设计了突变检测算法。该算法能将突变检测处理时间复杂度从O(m)降为O(log m)，m为需要被检测的滑动窗口数目。最后，分析并给出了基于单调搜索空间的突变检测方法的误差界限，使得本文提出的突变检测算法具有理论上的误差上限的保证。
3．提出了基于分段分形模型的无参数异常检测算法。首先，本文提出了最优的分段分形模型以及数据流上的近似最优分段分形模型。利用近似最优的分段分形模型为长为n的数据流建模的时间复杂度为O(n log n)，空间复杂度为O(log n)。第二，提出了基于分段分形模型的突变检测算法，该算法在分段分形模型具有理论误差界限保证的前提下，能够准确地检测数据流上的突变。第三，本文提出了无参数的异常检测算法。该算法能够在最合适尺寸的滑动窗口上检测异常的情况，不需要用户设定任何参数，也不需要使用训练数据。使用该算法在数据流上检测异常的时间复杂度仅为O(n)，空间复杂度仅为O(1)。
综上所述，本文针对现有异常检测中存在的三类问题，分别提出了从问题定义、概要数据结构到异常检测算法的完整方案，并提出了以本文技术为核心的异常检测系统框架。理论分析和实验结果表明，与已有的研究成果相比，本文给出的异常检测方法具有较高的精度和较低的时间、空间复杂度，更加适用于数据流的应用场景：金融风险分析、通信网监测、网络流量管理、趋势分析、Web日志分析、网络入侵检测、传感器网络管理等。
Recently, real-time monitoring and online data mining over data streams have been attracting more and more research attention in database research community because of its wide variety of real world applications. For instance, it is very important to monitor the data streams for telecommunication network performance tuning, highway traffic management, trend-related prediction analysis, web-click streams analysis, information system intrusion detection, and sensor networking, etc. Some of these tasks are mission critical which require fast response.
Conventional database techniques were initially invented to manage static data collections, which can not be applied directly to monitor or mine dynamic data streams. Hence a robust and efficient anomaly detection is needed to process huge amount of information in a constrained time period, in order to online monitor the data stream. The most important constraints or requirements for the data stream processing include limited memory availability, sequentially linear scanning, and online accurate result report over evolving data streams. However, existing methods on anomaly detection suffer several problems. Our major contributions in this paper are as follows.
1. A novel concept of adaptive aggregation burst is introduced for precisely modelling real-life data streams. This burst model empowers users to detect double-side relative bursts dynamically without disturbed by bumps. We propose a framework for accurately detecting such bursts under false positive and false negative constraints. The algorithms are developed based on a space and time efficient histogram, IH, which can be maintained with O(n(logn+logR/log(1+δ))) time and O(logn+logR/log(1+δ)) space. Thus IH is more suitable for burst detection than other popular histograms.
2. A monotonic search space based burst detection method is proposed. Firstly, the monotonic search space building algorithms are proposed for transforming
real life data. With the fractal transforming, the miss sorting error err_(MS) can be guaranteed 0. To construct such a monotonic search space for multi-window burst detection, a novel approach is presented, which could decrease the time overhead of query processing from O(m) to O(logm), where m is the number of windows being monitored.
3. Propose a parameter-free anomaly detection algorithm in this paper. We first introduce the piecewise fractal model (PFM) for data stream processing, which consumes O(n log n) time and O(logn) space to model a n length stream. Based on this model, a burst detection algorithm is proposed which can provide accurate burst detection. A novel PFM based method is proposed for anomaly detection. This algorithm consumes only O(1) memory and O(n) time without involving training process.
This paper give a survey on the state of art anomaly detection over data streams. Based on the analysis of existing research works, a more general definition of anomaly and existing problems are proposed. This paper also propose a system architecture for anomaly detection over data streams which integrates the novel anomaly detection techniques proposed in this paper. Theoretical analysis and experimental results show that this algorithm can achieve higher precision with less space and time complexity as compared with the existing methods, and it could be concluded that the proposed algorithm is suitable for burst detection over data streams.
引文
[1] 李建中，郭龙江，张冬冬，王伟平．数据流上的预测聚集查询处理算法．软件学报，16(7)：1252-1261，2005．
[2] 金澈清，钱卫宁，周傲英．流数据分析与管理综述．软件学报，15(8)：1172-1181，2004．
[3] Amazon home page. http://www.amazon.com.
[4] Saidu home page. http://www.baidu.com.
[5] ebay home page. http://www.ebay.com.
[6] Google home page. http://www.google.com.
[7] Internet traffic archive, http://ita.ee.lbl.gov/.
[8] Sprint's ip monitoring project. http://ipmon.sprintlabs.com.
[9] Yahoo home page. http://www.yahoo.com.
[10] R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. In Proc. of FODO, pages 69-84, 1993.
[11] A. Akella, A. Bharambe, M. Reiter, and S. Seshan. Detecting ddos attacks on isp networks. In Proc. of MPDS, 2003.
[12] N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. Tracking join and self-join sizes in limited storage. In Proc. of PODS, 1999.
[13] Noga. Alon, Yosi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proc. of A CM STOC, 1996.
[14] A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, and J. Widom. Stream: The stanford stream data manager. IEEE Data Engineering Bulletin, 26(1):19-26, 2003.
[15] A. Arasu and J. Widom. Resource sharing in continuous sliding-window aggregates. In Proc. of VLDB, 2004.
[16] R. Avnur and J. Hellerstein. Eddies: continuously adaptive query processing. In Proc. of SIGMOD, 2000.
[17] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In Proc. of Twenty-first A CM SIGACT-SIGMODSIGART Symposium on PODS, 2002.
[18] D. Barbara, J. Couto, and J. Lin. Bootstrapping a data mining intrusion detection system. In Proc. of SAC, pages 421-426, 2003.
[19] Daniel Barbará, Rajni Goel, and Sushil Jajodia. Using checksums to detect data corruption. Lecture Notes in Computer Science, 1777:136-138, 2000.
[20] M.F. Barnsley. Fractal functions and interpolation. Constructive Approximation, 2:303-329, 1986.
[21] M. F. Barnsley and S. G. Demko. Iterated function schemes and the global construction of fractals. In Proc. of the Royal Society, 1985.
[22] M. F. Barnsley, J. H. Elton, and D. P. Hardin. Recurrent iterated function systems. In Constructive Approximation, 1989.
[23] M.F. Barnsley. Fractals Everywhere. Academic Press, New York, 1988.
[24] RICHARD J. BARTON and H. VINCENT POOR. Signal detection in fractional gaussian noise. IEEE TRANSACTIONS ON INFORMATION THEORY, 34(5):943-959, SEPTEMBER 1988.
[25] S. Ben-David, J. Gehrke, and D. Kifer. Detecting change in data streams. In Proc. of VLDB, 2004.
[26] J. Bentley, B.Weide, and A. Yao. Optimal expected time algorithms for closest point problems. ACM Trans. on Math. Software, 6:563-580, 1980.
[27] R. Blakely. Google hits back at scare ad clickers. Times online, November 2004.
[28] P. Bonnet, J. Gehrke, and P. Seshadri. Towards sensor database systems. In Proc. of MDM, page 3-14, 2003.
[29] P. Borgnat, P. Flandrin, and P. O. Amblard. Stochastic discrete scale invariance. IEEE Signal Processing Letters, 9(6):181-184, June 2002.
[30] P. Brockwell and R. Davis. Introduction to Time Series and Forecasting. Springer, New York, 1996.
[31] J. Brutlag. Aberrant behavior detection in time series for network monitoring. In Proc. of USENIX LISA ⅩⅣ, December 2000.
[32] A. Bulut and A. K. Singh. A unified framework for monitoring data streams in real time. In Proc. of ICDE, 2005.
[33] Y.D. Cai, D. Clutter, G. Pape, J. Han, M. Welge, and L. Auvil. Maids: Mining alarming incidents from data streams. In Proc. of SIGMOD, 2004.
[34] Georg Cantor. On the Power of Perfect Sets of Points (De la puissance des ensembles parfait de points). Acta Mathematica 2 (1884) English translation reprinted in Classics on Fractals, ed. Gerald A. Edgar, Addison-Wesley, 1993.
[35] D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Monitoring streams -a new class of data management applications. In Proc. of VLDB, 2002.
[36] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat monitoring: application driver for wireless communications technology. In Proc. of SIGCOMM, pages 20-41, 2001.
[37] Kaushik Chakrabarti, Minos Garofalakis, Rajeev Rastogi, and Kyuseok Shim. Approximate query processing using wavelets. VLDB Journal: Very Large Data Bases, 10(2-3):199-223, 2001.
[38] S. Chandrasekaran, A. Deshpande, M. Franklin, J. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. Shah. Telegraphcq: Continuous dataflow processing for an uncertain world. In Proc. of CIDR, 2003.
[39] Mose Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In Proc. of the 29th ICALP, 2002.
[40] Y. Chen, G. Dong, J. Han, J. Pei, B. Wah, and J. Wang. Online analytical processing stream data: Is it feasible? In Proc. of DMKD, 2002.
[41] Y. Chen, G. Dong, J. Han, B. W. Wah, and J. Wang. Multi-dimensional regression analysis of time-series data streams. In Proc. of VLDB, 2002.
[42] Y. Chen, G. Dong, J. Han, B. W. Wah, and J. Wang. Multi-dimensional regression analysis of time-series data stream. In Proc. of VLDB, 2002.
[43] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Diamond in the rough: Finding hierarchical heavy hitters in multi-dimensional data. In Proc. of SIGMOD, June 2004.
[44] G. Cormode and S. Muthukrishnan. What's new: Finding significant differences in network data streams. In Proc. of INFOCOM, 2004.
[45] C. Cortes, K. Fisher, D. Pregibon, and A. Rogers. Hancock: A language for extracting signatures from data streams. In Proc. of KDD, page 9-17, 2000.
[46] C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk. Gigascope: a stream database for network applications. In Proc. of SIGMOD, 2003.
[47] M.E. Crovella, M. S. Taqqu, and A. Bestavros. Heavy-tailed probability distributions in the world wide web. A practical guide to heavy tails: STATISTICAL TECHNIQUES AND APPLICATIONS, pages 3-26, 1998.
[48] D. Dasgupta, J. Gomez, F. Gonzalez, M. Kaniganti, K. Yallapu, and R. Yarramsettii. Mmds: Multilevel monitoring and detection system. In Proc. of 15th Annual Computer Security Incident Handling Conference, pages 1-14, June 2003.
[49] M. Datar, A. Gionis, P. Indyk, and R. Motwani. Maintaining stream statistics over sliding windows. In Proc. of SODA, 2002.
[50] Brian D. Davison. The Design And Evaluation Of Web Prefetching and Caching Techniques. PhD thesis, Department of Computer Science, Rutgers University, October 2002.
[51] K. Delaney. Click fraud: Web outfits have a costly problem, marketers worry about bills inflated by people gaming the search ad-system. Wall Street Journal, April 2005.
[52] A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Modeldriven data acquisition in sensor networks. In Proc. of VLDB, page 321-330, 2004.
[53] A. Deshpande, C. Guestrin, S. Madden, and W. Hong. Exploiting correlated attributes in acquisitional query processing. In Proc. of ICDE, pages 143-154, 2005.
[54] A. Dobra, M. Garofalakis, J. Gehrke, and R. Rastogi. Processing complex aggregate queries over data streams. In Proc. of SIGMOD, pages 61-72, 2002.
[55] P. Domingos and G. Hulten. Mining high-speed data streams. In Knowledge Discovery and Data Mining, pages 71-80, 2000.
[56] D. Eroshenko. Click fraud: The state of the industry. Pay Per Click Analyst, October 2004.
[57] C. Estan, K. Keys, D. Moore, and G. Varghese. Building a better netflow. In Proc. of SIGCOM, 2004.
[58] C. Estan and G. Varghese. Data streaming in computer networks. In Proc. of the 2003 A CM Workshop on Management and Processing of Data Streams, 2000.
[59] A. C. Gilbert et al. Fast, small-space algorithms for approximate histogram maintenance. In Proc. of STOC, 2002.
[60] A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True. Deriving traffic demands for operational ip networks: methodology and experience. IEEE/ACM Transaction on Networking, 9(3):265-280, June 2001.
[61] S. Floyd, M. Handley, J. Padhye, and J. Widmer. Equation-based congestion control for unicast applications. In Proc. o.f A CM SIGCOMM, August 2000.
[62] B. Forte and E. R. Vrscay. Solving the inverse problem for measures using iterated function systems: A new approach. Advances in Applied Probability, 27(3):800-820, Sept. 1995.
[63] Bruno Forte and Edward Vrscay. Theory of generalized fractal transforms. In NATO ASI on Fractal Image Encoding and Analysis, Trondheim, 1995.
[64] C. Fraleigh, S. Moon, C. Diot, B. Lyles, and F. Tobagi. Architecture of a passive momitoring system for backbone ip networks. In Technical Report TROO-ATL-101-801, Sprint Advanced Technology Laboratories, Burlingame, California, October 2000.
[65] Gabriel Pui Cheong Fung, Jeffrey Xu Yu, Philip S. Yu, and Hongjun Lu. Parameter free bursty events detection in text streams. In Proc. of VLDB, pages 181-192, 2003.
[66] D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, and J. Heidemann. An evaluation of multi-resolution storage for sensor networks. In Proc. of Sensys, pages 89-102, 2003.
[67] M. Garofalakis and P. B. Gibbons. Wavelet synopses with error guarantees. In Proc. of SIGMOD, 2003.
[68] P. B. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In Proc. of VLDB, 1997.
[69] A.C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In Proc. of VLDB, 2001.
[70] D. Goldin and P. Kanellakis. On similarity queries for time-series data: Constraint specification and implementation. In Proc. of CP, pages 137-153, 1995.
[71] C. Guestrin, P. Bodi, R. Thibau, M. Paski, and S. Madden. Distributed regression: an efficient framework for modeling sensor network data. In Proc. of IPSN, pages 1-10, 2004.
[72] S. Guha, N. Koudas, and K. Shim. Datastreams and histograms. In Proc. of STOC, 2001.
[73] J. C. Hart. Fractal image compression and the inverse problem of recurrent iterated function systems. In Proc. of SIGGRAPH, 1994.
[74] J.C. Hart. Fractalimage compression and recurrent iterated function systems. IEEE Computer Graphics and Applications, 16(4):25-33, July 1996.
[75] H. Hartenstein, M. Ruhl, D. Sanpe, and E. R. Vrscay. Book chapters: On the inverse problem of fractal compression. Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, pages 617-647, August 2001.
[76] Y. Ioannidis. The history of histograms. In Proc, of VLDB, 2003.
[77] H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In Proc, of VLDB, 1998.
[78] A. Jain, E. Chang, and Y. F. Wang. Adaptive stream resource management using kalman filters. In Proc, of SIGMOD, pages 11-22, 2004.
[79] B. Jawerth and W. Sweldens. An overview of wavelet based multiresolution analyses. SIAM Rev, 36(3):377-412, 1994.
[80] C. Jin, W. Qian, C. Sha, J. X. Yu, and A. Zhou. Dynamically maintaining frequent items over a data stream. In Proc, of CIKM, 2003.
[81] S. S. Kim, A. L. Narasimha Reddy, and Marina Vannucci. Detecting traffic anomalies at the source through aggregate analysis of packet header data. In Proc, of Networking, May 2004.
[82] B. Kitts, P. Laxminarayan, B. LeBlanc, and R. Meech. A formal analysis of search auctions including predictions on click fraud and bidding tactics. June 2005.
[83] J. Kleinberg. Bursty and hierarchical structure in streams. In Proc, of SIGKDD, 2002.
[84] R. P. Kooi. The optimization of queries in relational databases. PhD thesis, Case Western Reserve University, 1980.
[85] T. Kratz, B. Benson, R. Bohanan, P. Ramanathan, and C. Wu. Itr: an intelligent sensor network to detect episodic events and their ecological consequences in lakes (http://www.limnology.wisc.edu). 2003.
[86] B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen. Sketch-based change detection: Methods, evaluation, and applications. In Proc, of IMC, 2003.
[87] S. Madden and M. Franklin. Fjording the stream: an architecture for queries over streaming sensor data. In Proc, of ICDE, 2002.
[88] B. B. Mandlebrot. The fractal geometry of nature. Freeman, New York, 1982.
[89] G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proc, of VLDB, 2002.
[90] D.S. Mazel and M. H. Hayes. Using iterated function systems to model discrete sequences. IEEE Transactions on Signal Processing, 40(7):1724-1734, July 1992.
[91] S. K. Mitra, C.A. Murthy, M. K. Kundu, and B. B. Bhattacharya. Fractal image compression using iterated function system with probabilities. In IEEE International Conference on In.formation Technology: Coding and Computing, April 2001.
[92] D. Moore, G. Voelker, and S. Savage. Inferring internet denial of service activ ity. In Proc. of the 2001 USENIX Security Symposuum, pages 9-22, August 2001.
[93] S. Muthukrishnan, R. Shah, and J. S. Vitter. Mining deviants in time series data streams. In Proc. of SSDBM, 2004.
[94] S. Muthukrishnan and M. Strauss. Rangesum histograms. In Proc. of SODA, 2003.
[95] SM. Ngai and Y. Wang. Hausdorff dimension of self-similar sets with overlaps. London Mathematical Society, pages 655-672, 2001.
[96] S. Papadimitriou, H. Kitagawa, P. Gibbons, and C. Faloutsos. Loci: Fast outlier detection using the local correlation integral. In Proc. of ICDE, pages 315-326, 2003.
[97] G. Piatetsky-Shapiro and C. Connell. Accurate estimation of the number of tuples satisfying a condition. In Proc. of SIGMOD, 1984.
[98] V. Poosala, Y. Ioannidis, P. Haas, and E. Shekita. Improved histograms for selectivity estimation of range predicates. In Proc. of SIGMOD, 1996.
[99] S. Qin, W. Qian, and A. Zhou. Approximately processing multi-granularity aggregate queries over data streams. In Proc. of ICDE, 2006.
[100] Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim. Efficient algorithms for mining outliers from large data sets. pages 427-438, 2000.
[101] C. Faloutsos M. Ranganathan and Y. Manolopoulos. Fast subsequence matching in time-series databases. In Proc. of SIGMOD, pages 419-429, 1994.
[102] Martin Reisslein, Jeremy Lassetter, Sampath Ratnam, Osama Lotfallah, Frank H.P. Fitzek, and Sethuraman Panchanathan. Tra]fic and Quality Characterization of Scalable Encoded Video: A Large-Scale Trace-Based Study-Part 4: Statistical Analysis of Spatial Scalable Encoded Video, 2003.
[103] P. Rousseeuw and A. Leroy. Robust Regression and Outlier Detection. John Wiley and Sons, New York, 1987.
[104] C. Shahabi, X. Tian, and W. Zhao. Tsa-tree: A wavelet-based approach to improve the efficiency of multi-level surprise and tend queries on time-series data. In Proc. of SSDBM, 2000.
[105] M. Sullivan and A. Heybey. Tribeca: A system for mananging large database of network traffic. In USENIX, 1998.
[106] D. B. Terry, D. Goldberg, D. Nichols, and B. M. Oki. Continuous queries over append-only databases. In Proc. of SIGMOD, page 321-330, June 1992.
[107] Axel van de Walle. Merging fractal image compression and wavelet transform methods. Fractals, 5 (Supplementary Issue):3-15, 1997.
[108] M. Vlachos, C. Meek, Z. Vagena, and D. Gunopulos. Identifying similarities, periodicities and bursts for online search queries. In Proc. of SIGMOD, 2004.
[109] H. von Koch. Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire. Arkiv for Matematik 1, pages 681-704, 1904.
[110] E. Vrscay. Mathematical theory of generalized fractal transforms and associated inverse problems. In Proc. of Image Tech 96 Conference on Multimedia Imaging Technology and Applications, pages 17-20, Atlanta, GA, 1996.
[111] N. Wadstromer. An automatization of barnsley's algorithm for the inverse problem of iterated function systems. IEEE Transactions on Image Processing, 12(11):1388-1397, Nov. 2003.
[112] M. Wang, A. Ailamaki, and C. Faloutsos. Capturing the spatiotemporal behavior of real traffic data. In Proc. of IFIP WG 7.3 Symposium on Computer Performance, pages 23-27, Rome, Italy, 2002.
[113] M. Wang, T. Madhyastha, N. Chan, S. Papadimitriou, and C. Faloutsos. Data mining meets performance evaluation: fast algorithm for modeling bursty traffic. In Proc. of ICDE, pages 507-516, 2004.
[114] R. Wannamaker and E. Vrscay. Fractal wavelet compression of audio signals. J. Audio Eng., Soc. 45(nos. 7-8):540-553, 1997.
[115] X. Wu and D. Barbara. Using fractals to compress real data sets: Is it feasible? In Proc, of SIGKDD, 2003.
[116] J. X. Yu, Z. Chong, H. Lu, and A. Zhou. False positive or false negative: Mining frequent itemsets from high speed transactional data streams. In Proc, of VLDB, 2004.
[117] A. Zhou, S. Qin, and W. Qian. Adaptively detecting aggregation bursts in data streams. In Proc, of DASFAA, 2005.
[118] Y. Zhu and D. Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. In Proc, of VLDB, 2002.
[119] Y. Zhu and D. Shasha. Efficient elastic burst detection in data streams. In Proc, of SIGKDD, 2003.
[2] 金澈清，钱卫宁，周傲英．流数据分析与管理综述．软件学报，15(8)：1172-1181，2004．
[3] Amazon home page. http://www.amazon.com.
[4] Saidu home page. http://www.baidu.com.
[5] ebay home page. http://www.ebay.com.
[6] Google home page. http://www.google.com.
[7] Internet traffic archive, http://ita.ee.lbl.gov/.
[8] Sprint's ip monitoring project. http://ipmon.sprintlabs.com.
[9] Yahoo home page. http://www.yahoo.com.
[10] R. Agrawal, C. Faloutsos, and A. Swami. Efficient similarity search in sequence databases. In Proc. of FODO, pages 69-84, 1993.
[11] A. Akella, A. Bharambe, M. Reiter, and S. Seshan. Detecting ddos attacks on isp networks. In Proc. of MPDS, 2003.
[12] N. Alon, P. B. Gibbons, Y. Matias, and M. Szegedy. Tracking join and self-join sizes in limited storage. In Proc. of PODS, 1999.
[13] Noga. Alon, Yosi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proc. of A CM STOC, 1996.
[14] A. Arasu, B. Babcock, S. Babu, M. Datar, K. Ito, I. Nishizawa, J. Rosenstein, and J. Widom. Stream: The stanford stream data manager. IEEE Data Engineering Bulletin, 26(1):19-26, 2003.
[15] A. Arasu and J. Widom. Resource sharing in continuous sliding-window aggregates. In Proc. of VLDB, 2004.
[16] R. Avnur and J. Hellerstein. Eddies: continuously adaptive query processing. In Proc. of SIGMOD, 2000.
[17] B. Babcock, S. Babu, M. Datar, R. Motwani, and J. Widom. Models and issues in data stream systems. In Proc. of Twenty-first A CM SIGACT-SIGMODSIGART Symposium on PODS, 2002.
[18] D. Barbara, J. Couto, and J. Lin. Bootstrapping a data mining intrusion detection system. In Proc. of SAC, pages 421-426, 2003.
[19] Daniel Barbará, Rajni Goel, and Sushil Jajodia. Using checksums to detect data corruption. Lecture Notes in Computer Science, 1777:136-138, 2000.
[20] M.F. Barnsley. Fractal functions and interpolation. Constructive Approximation, 2:303-329, 1986.
[21] M. F. Barnsley and S. G. Demko. Iterated function schemes and the global construction of fractals. In Proc. of the Royal Society, 1985.
[22] M. F. Barnsley, J. H. Elton, and D. P. Hardin. Recurrent iterated function systems. In Constructive Approximation, 1989.
[23] M.F. Barnsley. Fractals Everywhere. Academic Press, New York, 1988.
[24] RICHARD J. BARTON and H. VINCENT POOR. Signal detection in fractional gaussian noise. IEEE TRANSACTIONS ON INFORMATION THEORY, 34(5):943-959, SEPTEMBER 1988.
[25] S. Ben-David, J. Gehrke, and D. Kifer. Detecting change in data streams. In Proc. of VLDB, 2004.
[26] J. Bentley, B.Weide, and A. Yao. Optimal expected time algorithms for closest point problems. ACM Trans. on Math. Software, 6:563-580, 1980.
[27] R. Blakely. Google hits back at scare ad clickers. Times online, November 2004.
[28] P. Bonnet, J. Gehrke, and P. Seshadri. Towards sensor database systems. In Proc. of MDM, page 3-14, 2003.
[29] P. Borgnat, P. Flandrin, and P. O. Amblard. Stochastic discrete scale invariance. IEEE Signal Processing Letters, 9(6):181-184, June 2002.
[30] P. Brockwell and R. Davis. Introduction to Time Series and Forecasting. Springer, New York, 1996.
[31] J. Brutlag. Aberrant behavior detection in time series for network monitoring. In Proc. of USENIX LISA ⅩⅣ, December 2000.
[32] A. Bulut and A. K. Singh. A unified framework for monitoring data streams in real time. In Proc. of ICDE, 2005.
[33] Y.D. Cai, D. Clutter, G. Pape, J. Han, M. Welge, and L. Auvil. Maids: Mining alarming incidents from data streams. In Proc. of SIGMOD, 2004.
[34] Georg Cantor. On the Power of Perfect Sets of Points (De la puissance des ensembles parfait de points). Acta Mathematica 2 (1884) English translation reprinted in Classics on Fractals, ed. Gerald A. Edgar, Addison-Wesley, 1993.
[35] D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, and S. B. Zdonik. Monitoring streams -a new class of data management applications. In Proc. of VLDB, 2002.
[36] A. Cerpa, J. Elson, D. Estrin, L. Girod, M. Hamilton, and J. Zhao. Habitat monitoring: application driver for wireless communications technology. In Proc. of SIGCOMM, pages 20-41, 2001.
[37] Kaushik Chakrabarti, Minos Garofalakis, Rajeev Rastogi, and Kyuseok Shim. Approximate query processing using wavelets. VLDB Journal: Very Large Data Bases, 10(2-3):199-223, 2001.
[38] S. Chandrasekaran, A. Deshpande, M. Franklin, J. Hellerstein, W. Hong, S. Krishnamurthy, S. Madden, V. Raman, F. Reiss, and M. Shah. Telegraphcq: Continuous dataflow processing for an uncertain world. In Proc. of CIDR, 2003.
[39] Mose Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In Proc. of the 29th ICALP, 2002.
[40] Y. Chen, G. Dong, J. Han, J. Pei, B. Wah, and J. Wang. Online analytical processing stream data: Is it feasible? In Proc. of DMKD, 2002.
[41] Y. Chen, G. Dong, J. Han, B. W. Wah, and J. Wang. Multi-dimensional regression analysis of time-series data streams. In Proc. of VLDB, 2002.
[42] Y. Chen, G. Dong, J. Han, B. W. Wah, and J. Wang. Multi-dimensional regression analysis of time-series data stream. In Proc. of VLDB, 2002.
[43] G. Cormode, F. Korn, S. Muthukrishnan, and D. Srivastava. Diamond in the rough: Finding hierarchical heavy hitters in multi-dimensional data. In Proc. of SIGMOD, June 2004.
[44] G. Cormode and S. Muthukrishnan. What's new: Finding significant differences in network data streams. In Proc. of INFOCOM, 2004.
[45] C. Cortes, K. Fisher, D. Pregibon, and A. Rogers. Hancock: A language for extracting signatures from data streams. In Proc. of KDD, page 9-17, 2000.
[46] C. Cranor, T. Johnson, O. Spataschek, and V. Shkapenyuk. Gigascope: a stream database for network applications. In Proc. of SIGMOD, 2003.
[47] M.E. Crovella, M. S. Taqqu, and A. Bestavros. Heavy-tailed probability distributions in the world wide web. A practical guide to heavy tails: STATISTICAL TECHNIQUES AND APPLICATIONS, pages 3-26, 1998.
[48] D. Dasgupta, J. Gomez, F. Gonzalez, M. Kaniganti, K. Yallapu, and R. Yarramsettii. Mmds: Multilevel monitoring and detection system. In Proc. of 15th Annual Computer Security Incident Handling Conference, pages 1-14, June 2003.
[49] M. Datar, A. Gionis, P. Indyk, and R. Motwani. Maintaining stream statistics over sliding windows. In Proc. of SODA, 2002.
[50] Brian D. Davison. The Design And Evaluation Of Web Prefetching and Caching Techniques. PhD thesis, Department of Computer Science, Rutgers University, October 2002.
[51] K. Delaney. Click fraud: Web outfits have a costly problem, marketers worry about bills inflated by people gaming the search ad-system. Wall Street Journal, April 2005.
[52] A. Deshpande, C. Guestrin, S. Madden, J. Hellerstein, and W. Hong. Modeldriven data acquisition in sensor networks. In Proc. of VLDB, page 321-330, 2004.
[53] A. Deshpande, C. Guestrin, S. Madden, and W. Hong. Exploiting correlated attributes in acquisitional query processing. In Proc. of ICDE, pages 143-154, 2005.
[54] A. Dobra, M. Garofalakis, J. Gehrke, and R. Rastogi. Processing complex aggregate queries over data streams. In Proc. of SIGMOD, pages 61-72, 2002.
[55] P. Domingos and G. Hulten. Mining high-speed data streams. In Knowledge Discovery and Data Mining, pages 71-80, 2000.
[56] D. Eroshenko. Click fraud: The state of the industry. Pay Per Click Analyst, October 2004.
[57] C. Estan, K. Keys, D. Moore, and G. Varghese. Building a better netflow. In Proc. of SIGCOM, 2004.
[58] C. Estan and G. Varghese. Data streaming in computer networks. In Proc. of the 2003 A CM Workshop on Management and Processing of Data Streams, 2000.
[59] A. C. Gilbert et al. Fast, small-space algorithms for approximate histogram maintenance. In Proc. of STOC, 2002.
[60] A. Feldmann, A. Greenberg, C. Lund, N. Reingold, J. Rexford, and F. True. Deriving traffic demands for operational ip networks: methodology and experience. IEEE/ACM Transaction on Networking, 9(3):265-280, June 2001.
[61] S. Floyd, M. Handley, J. Padhye, and J. Widmer. Equation-based congestion control for unicast applications. In Proc. o.f A CM SIGCOMM, August 2000.
[62] B. Forte and E. R. Vrscay. Solving the inverse problem for measures using iterated function systems: A new approach. Advances in Applied Probability, 27(3):800-820, Sept. 1995.
[63] Bruno Forte and Edward Vrscay. Theory of generalized fractal transforms. In NATO ASI on Fractal Image Encoding and Analysis, Trondheim, 1995.
[64] C. Fraleigh, S. Moon, C. Diot, B. Lyles, and F. Tobagi. Architecture of a passive momitoring system for backbone ip networks. In Technical Report TROO-ATL-101-801, Sprint Advanced Technology Laboratories, Burlingame, California, October 2000.
[65] Gabriel Pui Cheong Fung, Jeffrey Xu Yu, Philip S. Yu, and Hongjun Lu. Parameter free bursty events detection in text streams. In Proc. of VLDB, pages 181-192, 2003.
[66] D. Ganesan, B. Greenstein, D. Perelyubskiy, D. Estrin, and J. Heidemann. An evaluation of multi-resolution storage for sensor networks. In Proc. of Sensys, pages 89-102, 2003.
[67] M. Garofalakis and P. B. Gibbons. Wavelet synopses with error guarantees. In Proc. of SIGMOD, 2003.
[68] P. B. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In Proc. of VLDB, 1997.
[69] A.C. Gilbert, Y. Kotidis, S. Muthukrishnan, and M. Strauss. Surfing wavelets on streams: One-pass summaries for approximate aggregate queries. In Proc. of VLDB, 2001.
[70] D. Goldin and P. Kanellakis. On similarity queries for time-series data: Constraint specification and implementation. In Proc. of CP, pages 137-153, 1995.
[71] C. Guestrin, P. Bodi, R. Thibau, M. Paski, and S. Madden. Distributed regression: an efficient framework for modeling sensor network data. In Proc. of IPSN, pages 1-10, 2004.
[72] S. Guha, N. Koudas, and K. Shim. Datastreams and histograms. In Proc. of STOC, 2001.
[73] J. C. Hart. Fractal image compression and the inverse problem of recurrent iterated function systems. In Proc. of SIGGRAPH, 1994.
[74] J.C. Hart. Fractalimage compression and recurrent iterated function systems. IEEE Computer Graphics and Applications, 16(4):25-33, July 1996.
[75] H. Hartenstein, M. Ruhl, D. Sanpe, and E. R. Vrscay. Book chapters: On the inverse problem of fractal compression. Ergodic Theory, Analysis, and Efficient Simulation of Dynamical Systems, pages 617-647, August 2001.
[76] Y. Ioannidis. The history of histograms. In Proc, of VLDB, 2003.
[77] H. V. Jagadish, N. Koudas, S. Muthukrishnan, V. Poosala, K. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In Proc, of VLDB, 1998.
[78] A. Jain, E. Chang, and Y. F. Wang. Adaptive stream resource management using kalman filters. In Proc, of SIGMOD, pages 11-22, 2004.
[79] B. Jawerth and W. Sweldens. An overview of wavelet based multiresolution analyses. SIAM Rev, 36(3):377-412, 1994.
[80] C. Jin, W. Qian, C. Sha, J. X. Yu, and A. Zhou. Dynamically maintaining frequent items over a data stream. In Proc, of CIKM, 2003.
[81] S. S. Kim, A. L. Narasimha Reddy, and Marina Vannucci. Detecting traffic anomalies at the source through aggregate analysis of packet header data. In Proc, of Networking, May 2004.
[82] B. Kitts, P. Laxminarayan, B. LeBlanc, and R. Meech. A formal analysis of search auctions including predictions on click fraud and bidding tactics. June 2005.
[83] J. Kleinberg. Bursty and hierarchical structure in streams. In Proc, of SIGKDD, 2002.
[84] R. P. Kooi. The optimization of queries in relational databases. PhD thesis, Case Western Reserve University, 1980.
[85] T. Kratz, B. Benson, R. Bohanan, P. Ramanathan, and C. Wu. Itr: an intelligent sensor network to detect episodic events and their ecological consequences in lakes (http://www.limnology.wisc.edu). 2003.
[86] B. Krishnamurthy, S. Sen, Y. Zhang, and Y. Chen. Sketch-based change detection: Methods, evaluation, and applications. In Proc, of IMC, 2003.
[87] S. Madden and M. Franklin. Fjording the stream: an architecture for queries over streaming sensor data. In Proc, of ICDE, 2002.
[88] B. B. Mandlebrot. The fractal geometry of nature. Freeman, New York, 1982.
[89] G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proc, of VLDB, 2002.
[90] D.S. Mazel and M. H. Hayes. Using iterated function systems to model discrete sequences. IEEE Transactions on Signal Processing, 40(7):1724-1734, July 1992.
[91] S. K. Mitra, C.A. Murthy, M. K. Kundu, and B. B. Bhattacharya. Fractal image compression using iterated function system with probabilities. In IEEE International Conference on In.formation Technology: Coding and Computing, April 2001.
[92] D. Moore, G. Voelker, and S. Savage. Inferring internet denial of service activ ity. In Proc. of the 2001 USENIX Security Symposuum, pages 9-22, August 2001.
[93] S. Muthukrishnan, R. Shah, and J. S. Vitter. Mining deviants in time series data streams. In Proc. of SSDBM, 2004.
[94] S. Muthukrishnan and M. Strauss. Rangesum histograms. In Proc. of SODA, 2003.
[95] SM. Ngai and Y. Wang. Hausdorff dimension of self-similar sets with overlaps. London Mathematical Society, pages 655-672, 2001.
[96] S. Papadimitriou, H. Kitagawa, P. Gibbons, and C. Faloutsos. Loci: Fast outlier detection using the local correlation integral. In Proc. of ICDE, pages 315-326, 2003.
[97] G. Piatetsky-Shapiro and C. Connell. Accurate estimation of the number of tuples satisfying a condition. In Proc. of SIGMOD, 1984.
[98] V. Poosala, Y. Ioannidis, P. Haas, and E. Shekita. Improved histograms for selectivity estimation of range predicates. In Proc. of SIGMOD, 1996.
[99] S. Qin, W. Qian, and A. Zhou. Approximately processing multi-granularity aggregate queries over data streams. In Proc. of ICDE, 2006.
[100] Sridhar Ramaswamy, Rajeev Rastogi, and Kyuseok Shim. Efficient algorithms for mining outliers from large data sets. pages 427-438, 2000.
[101] C. Faloutsos M. Ranganathan and Y. Manolopoulos. Fast subsequence matching in time-series databases. In Proc. of SIGMOD, pages 419-429, 1994.
[102] Martin Reisslein, Jeremy Lassetter, Sampath Ratnam, Osama Lotfallah, Frank H.P. Fitzek, and Sethuraman Panchanathan. Tra]fic and Quality Characterization of Scalable Encoded Video: A Large-Scale Trace-Based Study-Part 4: Statistical Analysis of Spatial Scalable Encoded Video, 2003.
[103] P. Rousseeuw and A. Leroy. Robust Regression and Outlier Detection. John Wiley and Sons, New York, 1987.
[104] C. Shahabi, X. Tian, and W. Zhao. Tsa-tree: A wavelet-based approach to improve the efficiency of multi-level surprise and tend queries on time-series data. In Proc. of SSDBM, 2000.
[105] M. Sullivan and A. Heybey. Tribeca: A system for mananging large database of network traffic. In USENIX, 1998.
[106] D. B. Terry, D. Goldberg, D. Nichols, and B. M. Oki. Continuous queries over append-only databases. In Proc. of SIGMOD, page 321-330, June 1992.
[107] Axel van de Walle. Merging fractal image compression and wavelet transform methods. Fractals, 5 (Supplementary Issue):3-15, 1997.
[108] M. Vlachos, C. Meek, Z. Vagena, and D. Gunopulos. Identifying similarities, periodicities and bursts for online search queries. In Proc. of SIGMOD, 2004.
[109] H. von Koch. Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire. Arkiv for Matematik 1, pages 681-704, 1904.
[110] E. Vrscay. Mathematical theory of generalized fractal transforms and associated inverse problems. In Proc. of Image Tech 96 Conference on Multimedia Imaging Technology and Applications, pages 17-20, Atlanta, GA, 1996.
[111] N. Wadstromer. An automatization of barnsley's algorithm for the inverse problem of iterated function systems. IEEE Transactions on Image Processing, 12(11):1388-1397, Nov. 2003.
[112] M. Wang, A. Ailamaki, and C. Faloutsos. Capturing the spatiotemporal behavior of real traffic data. In Proc. of IFIP WG 7.3 Symposium on Computer Performance, pages 23-27, Rome, Italy, 2002.
[113] M. Wang, T. Madhyastha, N. Chan, S. Papadimitriou, and C. Faloutsos. Data mining meets performance evaluation: fast algorithm for modeling bursty traffic. In Proc. of ICDE, pages 507-516, 2004.
[114] R. Wannamaker and E. Vrscay. Fractal wavelet compression of audio signals. J. Audio Eng., Soc. 45(nos. 7-8):540-553, 1997.
[115] X. Wu and D. Barbara. Using fractals to compress real data sets: Is it feasible? In Proc, of SIGKDD, 2003.
[116] J. X. Yu, Z. Chong, H. Lu, and A. Zhou. False positive or false negative: Mining frequent itemsets from high speed transactional data streams. In Proc, of VLDB, 2004.
[117] A. Zhou, S. Qin, and W. Qian. Adaptively detecting aggregation bursts in data streams. In Proc, of DASFAA, 2005.
[118] Y. Zhu and D. Shasha. Statstream: Statistical monitoring of thousands of data streams in real time. In Proc, of VLDB, 2002.
[119] Y. Zhu and D. Shasha. Efficient elastic burst detection in data streams. In Proc, of SIGKDD, 2003.