1.1.2 常用近似查询技术
近似查询为大规模数据的复杂查询问题提供了新的思路,其可以平衡数据查询或处理所花费的时间与其结果的精度,以灵活的方式处理查询。同时,用户可以指定时间或精度的量化约束,选择一个快速的粗略结果或迟缓的更精确结果。近似查询的主要方法包括数据采样(Data Sampling)、随机化算法(Randomized Algorithm)、数据概要(Data Synopsis)、在线聚集(Online Aggregation)等。
(1)基于采样的近似查询处理方法,需对原始数据预处理,得到能够代表原始数据且数据量小的样本集,此方法不需要访问原始数据,只需要对样本集查询即可,存取速度较快,并且查询结果的误差在预计算阶段已经计算完成。
(2)基于在线聚合的近似查询处理方法,实时地返回结果并允许用户直接观察执行情况的方式。首先对原始数据抽样形成聚集分组,对各组数据进项查询计算,进而将查询结果、置信区间域精确度等信息快速地反馈给用户,随着读取数据量的增大,近似结果逐渐逼近精确结果。该方法缺点在于查询类型有限,因需实时反馈对计算机内存和性能要求较高,查询代价较大,同时处理的查询类型限制在几类其统计特性已被完整分析的数据操作中,如平均值与求和等。
(3)随机化算法主要应用场景是对于统计推断理论基础已相当完善的数据统计量的近似处理,例如聚集函数中的求均值与求和等类型统计量。通过随机化处理,对不断增多的样本集进行计算即可取得有统计性保证的结果值。然而对于空间数据值,这些前提条件都无法满足,因此随机化算法不易应用于空间近似查询的处理。
(4)基于数据概要的查询方法预先收集数据的一些统计信息,并基于独立性等简单假设,是近似查询的主流技术。较有代表性的方法包括直方图、小波分解、窗口和抽样技术等。(https://www.daowen.com)
①直方图技术是采用分箱的方式简单快速地记录数据分布状态,主要是将数据集S的值域[a,b],分成多个不重叠的区域,划分的小区域称为桶,分布于每个桶的数据采用平均值代替。直方图类型包括等宽直方图、等高直方图和压缩直方图等,压缩直方图是等高和等宽直方图的改进与优化,采用数值对(v i,f i)的方式对出现次数较多的数值记录,节省了存储空间,适用于数据分布均匀的数据集。针对多维数据时,由于数据量较大、存储空间膨胀的问题,允许直方图划分的桶之间可以互相覆盖,从而获取不同的频率区域,应对多维数据摘要的构建。
②小波分解技术是按照层次对函数展开分解的技术,主要由粗略的总体近似和影响函数的细节系数组成,其原则在于通过低分辨率的阵列重建原始数据阵列的值。哈尔小波(Haar wavelet)是简单且计算速度很快的一种小波技术,包括一维Haar波和多维Haar波,在信号处理、数据压缩等方面广泛应用。一维Haar波是将一维向量V中的数据成对地完成差分与平均的交叉计算,最终结果为包含相同数据个数的一维向量V*。多维Haar波是一维Haar波的扩展,多维Haar波是针对一维Haar波的扩展,经过小波分解后得到多维的系数矩阵,根据矩阵可以恢复原始数据。
③窗口查询技术在多种近似查询技术中属于比较常用的一种技术。由于数据流的无限性特性,数据流系统中通常无须在整个历史数据中进行查询计算,而是在窗口限定的最近一段时间内的数据集上进行查询。窗口查询在近似查询技术方面主要拥有以下两个优势:第一,使用简单并且容易理解,查询时所需要关注的数据较为明确,无须对位于窗口之外的数据进行操作;第二,查询过程中主要关注最新数据,相对忽略旧数据对于查询的影响,符合海量数据查询的实时性要求。
④抽样技术是根据一定的方法从大量数据集中抽取少量样本数据作为原始数据的索引,是简单且应用较早的方法,包括随机采样和分层采样两种方法。随机采样是在原始数据分布比较均匀的情况下,随机的抽取样本的过程,适用于数据集均匀的情况,存在两个缺点:第一,选择的样本可能不足以代表原始数据;第二,忽略了数据分布情况。分层抽样是按照某种特征或属性划分为若干次级的总体层,对每一层进行取样的过程,因此相对于均匀抽样来说,分层抽样更优化,由于在不同层级间取样减少了误差,从而增加了准确度。更重要的是,对于稀疏数据集而言,分层采样可以非常有效地减少样本的数量,同时又能利用霍夫丁不等式(Hoeffding's inequality)来保证所取样本在回答均值、求和等统计量时的置信区间与置信度。
