唐 达， 刘 畅， 岳 前 进， 张 建 英

（1.大连理工大学 计算机科学与技术学院，辽宁 大连 116024；2.大连理工大学 工程力学系，辽宁 大连 116024）

0 引 言

深海平台监测系统通过分析传感器网络上采集到的数据，来确定不同的因素对该平台的影响.从传感器上采集到的数据是随时间不断变化的，具有连续、无界两个特点，即为流数据[1].深海平台监测系统需要管理这类流数据，以便用户查询.对流数据的查询通常是连续的，当新数据到达时增量式地返回结果.在深海平台监测系统中，用户查询仅仅需要一个近似结果，并不需要获得精确的查询值，由于存储容量的有限性，将所有流数据都保存起来不现实，也没有必要.为实现对流数据的存储，需要设计一个保存原始流数据的特征，规模上远小于原流数据的概要数据结构（synopsis data structure）[2].本文对此进行研究.

1 概要数据构建技术

概要数据构建技术主要有直方图（histogram）技术[3]、小波（wavelet）技术[4]和抽样（sampling）技术.直方图技术只能反映数据的大致轮廓和分布特征，小波技术是从数据集中抽取小部分数据样本，并根据样本近似恢复数据集，相对复杂，两种构建技术构建的概要数据均不能满足流数据快速、连续查询的要求.抽样技术生成概要数据的效率高，能满足流数据快速、连续查询的要求，可以很好地应用到深海平台监测系统上.现有抽样算法主要有均匀抽样（uniform sampling）、偏倚抽样（biased sampling）和权值抽样.

均匀抽样：各元组被抽取到的概率是相等的.Vitter[5]提出水库抽样方……