大数据时代,数据量迅速膨胀,给大数据的计算、查询和分析带来了巨大挑战。传统的数据计算技术难于应对不断增长的数据量。为此,研究者们在准确性、存储代价、以及效率之间做权衡,提出了从大数据中获取数据概要并利用数据概要来解决大数据近似计算问题的方法。数据概要是从大数据中获取的具有总结性的信息,包括样本、草图、直方图、数据方块、小波等。基于数据概要的近似计算技术能够大幅度的降低待处理的数据量,有效的提高效率,满足快速响应的需求。通常,数据概要中存储的信息越多,最终估计结果的准确性越高,即,选取更多的样本、在直方图中存储更多的桶将带来更为准确的估计结果。这意味着这些方法需要以增大存储空间作为代价来提高准确性。为应对当今时代不断膨胀的数据量,我们希望在提高准确性的同时,维持轻量级的数据概要。为此,我们针对大数据计算中频率估计、选择性估计、近似聚集查询处理、近似分组查询处理这四个重要问题,分别提出了新的数据概要及方法。本文提出的这些方法较基于传统数据概要的方法更为准确,同时占用更小的存储空间。本文主要研究内容概括如下。1.本文研究了大数据频率估计问题。频率估计广泛应用于网络流量分析、网络监控、异常检测、频繁元素查找等多种领域。庞大的数据量使准确存储并查询数据频率面临昂贵的代价,基于亚线性草图进行频率估计能够大幅降低存储代价。而传统Count-Min草图中,其通过哈希函数将数据映射到亚线性空间的存储特性也使它面临着由哈希冲突造成的巨大的估计误差。为此,本文提出了两种学习草图,根据历史数据建立频率模型,并将高频数据和低频数据分开处理。本文提出的方法利用模型代替高频数据频数的存储,用传统Count-Min草图处理低频数据,从而避免了高频数据和低频数据存储冲突造成的巨大误差。同时,轻量级的模型代替大量数据频数的存储能够有效降低空间代价。本文在真实和虚拟数据集上进行了实验,验证了本文提出的两种学习草图相比于传统草图能够以更轻量级的存储代价提供更为准确的频率估计结果。2.本文研究了大数据多维查询选择性估计问题。查询选择性指满足查询谓词的元组占全部数据元组的比例,查询选择性估计的准确性决定了查询优化的结果。数据库系统中通常采用一维直方图来估计查询选择性。但是,基于各属性独立的假设来估计多维范围查询的选择性通常是不准确的。多维直方图是这一问题的一种解决途径,但它同时也面临着包括构建困难以及巨大的空间代价在内的一些挑战。等高直方图,V-optimal直方图的划分方法随着维度的升高而变得多样化,难以抉择出最优划分的方法;易于划分的等宽直方图难于应对数据分布偏斜的情况。现有的直方图通常以增大桶数为代价来提升准确性,而随着维度的增高,增加桶数将增加额外的空间代价。为了在提高准确性的同时并避免增加直方图的存储成本,本文提出了一种方法,该方法使用从密集区域中的大量桶中学习到的密度模型来替代这些桶的存储。它将密度模型与直方图中的一些桶结合在一起估计查询选择性。本文在真实和模拟数据集上进行了实验,验证了在同等存储代价下,本文提出的算法优于现存的多种有代表性的多维直方图。3.本文研究了大数据近似聚集查询处理问题。在大数据上计算准确的聚集查询结果无疑会花费昂贵的代价,且难以满足快速响应的需求。为解决这一问题,近似聚集查询处理应运而生,它能够快速提供聚集查询的近似结果。基于抽样的方法根据样本上的查询结果估计整体数据上的查询结果。基于抽样的方法的准确性和样本量相关,少量的样本难以代表整体的数据分布,尤其难以代表偏斜数据的分布情况。基于预聚集的方法根据存储的预聚集结果来估计当前查询。然而,若当前查询的范围和预查询不相交,那么就不能够从预查询中获取帮助。基于机器学习的方法通过历史查询训练回归模型,并利用模型估计查询结果,然而,这种方法并不能提供误差界限。本文提出了一种新的方法,将抽样、预聚集与机器学习模型相结合,综合利用各方法的优势。该方法根据预聚集和小样本训练误差模型,并根据当前查询的预测误差从预查询中选取最优的查询作为基准来估计当前查询。本文在真实和模拟数据集上进行了实验,验证了本文提出的算法相比于分别基于抽样、预聚集、机器学习方法的优越性。4.本文研究了大数据近似分组查询处理问题。抽样是近似查询处理的主要手段之一,然而基于抽样的近似查询处理方法并不能很好的估计分组查询。分组查询的结果包含多个值,不同分组的数据分布不同。通过均匀采样难以为稀疏组获取足够多的样本;分层采样能够提升准确性,但为一些查询获取的分层样本不能适用于其他查询;线上采样能够根据查询获取样本,但查询时采样无疑会增加响应延迟。为此,我们提出了基于条件生成模型的样本生成方法,能够在不接触原始数据的情况下获取样本,且能够为给定组生成任意数量的目标样本。它可以灵活地和多种分层抽样方法相结合,从而在降低响应延迟的同时提升准确性。此外,本文还提出了针对低选择性的分组查询的样本生成方法,能够针对查询谓词生成高质量的分层样本。本文在真实和模拟数据集上进行了实验,验证了本文提出的算法的高效和准确。