数据流上的突变检测在网络流量监测,金融风险分析,传感器网络等领域都有着十分广泛的应用。传统的突变检测算法只能对流上的聚集函数值进行检测,而在现实应用中,还有相当一部分的突变检测要求能针对非聚集函数进行检测。本文提出了一种新颖的数据流上的突变检测算法,即最窄平行四边形法。该方法用一系列扁平的平行四边形来模拟数据流上具有相同趋势的点,并保证每个点的误差不超过平行四边形宽度的一半。于是,等距到达的数据,便可根据得到的平行四边形还原其中的每一个点,从而实现基于任意类型函数的突变检测。在提出最窄平行四边形基本算法之后,本文又对该算法进行了一系列改进,使其时间复杂度从O(nh)降到了O(h),其中n为平行四边形内包含的点的个数,h为覆盖这些点的凸包的边数。通过对真实数据流上的数据进行实验分析,以及与现有突变检测算法的比较,验证了最窄平行四边形算法在时间和空间上的高效性。针对现有各种基于直方图的突变检测方法在构造数据流模型时存在的空间低效性,本文又对最窄平行四边形法进行了扩展,使其在针对聚集函数的突变检测中能更加节省存储空间,从而在相同的内存容量限制下能检测更大的滑动窗口。最后通过实验验证了该方法对现有基于直方图的突变检测方法的优越性。本文的主要贡献可总结为如下三方面:·基于大部分数据流上数据变化的规律,提出了最窄平行四边形法。通过对流上原始数据进行压缩,支持基于任意函数的突变检测。据我们所知,这是第一次把凸包算法应用到数据流的突变检测上来。·对基本的最窄平行四边形算法进行了改进,使其时间复杂度从O(nh)降到了O(h),从而更加适用于高速的数据流环境。·扩展了最窄平行四边形法,令其作用在原始数据的后缀和上。从而使得在针对基于聚集函数的突变检测上,该算法具有更为经济的时空复杂度,弥补了现有基于直方图算法的缺陷。本文提出的突变检测算法是建立在大量的理论分析之上,并通过对真实数据的实验测试的。该算法能普遍适应多种数据流检测环境,满足用户对功能与效率的需求。