QPAAS:一种在线多数据流自适应分段算法  

QPAAS:An Online Algorithm for Adaptively Segmenting Multiple Data Streams

作　　者：张彬[1] 陈琼[1] 彭勇[1] 

机构地区：[1]衡阳师范学院计算机科学系,湖南衡阳421008

出　　处：《衡阳师范学院学报》2010年第3期80-83,共4页Journal of Hengyang Normal University

基　　金：湖南省教育厅高校科研计划项目(09C176)

摘　　要：数据流分段是数据流处理技术的基本任务,然而,它在多数据流环境下并不是一个小问题。该文提出了一个高效算法(即QPAAS算法),它能实时处理多个数据流分段。该算法利用了PAA技术中的增量计算特性,能快速处理单个数据流分段。为了处理多个数据流,它索引所有数据流的当前分段到一颗B+树中,这样算法即可实时分段多个数据流。在真实的数据流上的多个实验表明,QPAAS算法有效而高效,仅具有线性时间和空间复杂度。而且,它比传统的PAA分段算法快几个数量级。Segmentation of data streams is a basic task of data streams processing technologies. However, the task is not a trivi al problem in the environment of multiple data streams. An efficient algorithm, called QPAAS （namely Quick Piecewise Aggre gate Approximation over multiple data Streams）, which can adaptively segment multiple data streams with real time response, was proposed in the paper. The algorithm takes advantage of the feature of incremental computation of PAA （Piecewise Aggregate Approximation） technology and can quickly process the segmentation of simple data stream. In order to deal with multiple data streams, it indexes all current segments of the data streams into a B-tree index. Thus, it can segment multiple data streams in real time. The experimental results show that QPAAS is effective and efficient, it has only linear time and space complexities. Moreover. it achieves several orders of magnitude performance improvement relative to traditional PAA segmenting approach.

关 键 词：算法 数据流 分段 点对累积近似 增量计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]