一种海量数据近似聚集查询中的离群分治取样方法

摘要

本发明公开了一种海量数据近似聚集查询中的离群分治取样方法，将高偏斜关系R离群分离成两个子集R_o和R_{n_o}；近似聚集查询Q可以看成两个子查询的并，第一个子查询运行在离群值子集R_o上，第二个子查询则运行在R_{n_o}的均匀取样集上；具体来说，海量数据近似聚集查询中的离群分治取样方法包括两个步骤:离群分离+查询处理；从以上方法实现框架得出:查询误差只归结于非离群值子集R_{n_o}上的近似查询误差。本发明在海量数据集的聚集属性内部存在高方差分布时能克服随机均匀取样的不足，显著降低近似查询误差，适用于云计算环境，离群分治取样方法的离群分离步骤只需单遍扫描数据集、无需对整个聚集属性集进行排序，能自然的扩展应用于数据流的近似聚集查询。

主权项

一种海量数据近似聚集查询中的离群分治取样方法，其特征在于：包括离群分离步骤和查询处理步骤，其中:步骤1，离群分离：步骤1‑1，分离R中的离群值并生成离群值子集R_o：步骤1‑1‑1，定义输入参数:海量数据集的元组数N；均匀取样率f；离群值比率l，l>0，且离群点数lN<<n'，n'是取样集T的样本数，n'＝f*(N‑lN)，|T|＝n'，l值借助工作负载信息或历史数据分布信息获取；步骤1‑1‑2，将关系R的数据集划分为m个窗口，m＝clN，即要求窗口数超过离群点数；公式中的c为正整数常数，2≤c≤1/l，如果离群值分散或均匀分布，c取下界值，否则取上界值；步骤1‑1‑3，每个窗口的元组数步骤1‑1‑4，对每个窗口i,i从1起算到第m个窗口止均重复以下的计算过程：步骤1‑1‑4‑1，从第i个窗口中顺序取出w个元组的{C₁,…,C_N}，并定义为{C₁′,…,C_w′}，C是查询Q的聚集属性列{C₁,…,C_N}；步骤1‑1‑4‑2，如果从最后一个窗口中取出的元组数w’少于w，则直接取w的值为w’；步骤1‑1‑4‑3，对每个窗口i中的每个元组j均实施以下的计算过程：步骤1‑1‑4‑3‑1，计算除元组j之外的标准差值E(j)，E(j)＝S({C₁′,…C_j‑1′,C_j+1′,…,C_w′}),S是C的子集的标准差,C₁′是低界值,C_w′是高界值；步骤1‑1‑4‑3‑2，设E(j)取最小值时的j为j′，C_j′是候选离群点，将含C_j′的元组插入离群值子集R_o；步骤1‑1‑5，合并与排序离群值子集R_o，只保留头lN个元组，lN是离群点数目；步骤1‑1‑6，Rn_o＝R‑Ro，非离群子集Rn_o为数据集R与离群值子集Ro的差集；步骤1‑2，根据取样率f对R中余下的非离群值Rn_o进行均匀取样，生成取样集T；步骤2，查询处理：步骤2‑1，聚集离群值:在离群值子集Ro上运行聚集查询；步骤2‑2，聚集非离群值:在非离群值子集Rn_o的均匀取样集T上运行聚集查询并乘以取样率的倒数，从而推算出Rn_o的近似查询值；步骤2‑3，结合聚集值:结合Ro上的准确聚集值和Rn_o上的近似聚集值来得到R的近似聚集值。