Sapprox: Enabling Efficient and Accurate Approximations on Sub-datasets with Distribution-aware Online Sampling
Sapprox: Enabling Efficient and Accurate Approximations on Sub-datasets with Distribution-aware Online Sampling
复制标题
DOI：
10.14778/3021924.3021928
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Xuhong Zhang;Jun Wang;Jiangling Yin;S. Ji
中科院分区：
文献类型：
--
作者：
Xuhong Zhang;Jun Wang;Jiangling Yin;S. Ji
在本文中，我们的目标是对大型数据集的任意子数据集实现高效且准确的近似。由于为每个子数据集缓存离线样本的存储开销过高，现有的基于离线样本的系统只能为有限数量的子数据集（例如流行的子数据集）提供高精度结果。另一方面，当前基于在线样本的近似系统在运行时生成样本，没有考虑子数据集的不均匀存储分布。它们对于子数据集的均匀分布效果很好，但在不均匀分布的子数据集上采样效率较低且估计精度较差。为了解决这个问题，我们开发了一种名为 Sapprox 的分布感知方法。我们的想法是收集分布式系统中数据集（存储分布）的每个逻辑分区上子数据集的出现情况，并充分利用这些信息来方便在线采样。 Sapprox 中有三个推力。首先，我们开发了一个概率图，将记录的子数据集的指数数量减少到线性数量。其次，我们应用不等概率理论的聚类抽样来实现分布感知抽样方法，以实现高效的在线子数据集抽样。第三，我们通过将分布式文件系统中的最佳采样单元大小与近似成本和准确性相关联，定量地推导出分布式文件系统中的最佳采样单元大小。我们已将 Sapprox 作为示例系统实施到 Hadoop 生态系统中，并在 GitHub 上开源。我们全面的实验结果表明，Sapprox 可以比精确执行实现高达 20 倍的加速。
In this paper, we aim to enable both efficient and accurate approximations on arbitrary sub-datasets of a large dataset. Due to the prohibitive storage overhead of caching offline samples for each sub-dataset, existing offline sample based systems provide high accuracy results for only a limited number of sub-datasets, such as the popular ones. On the other hand, current online sample based approximation systems, which generate samples at runtime, do not take into account the uneven storage distribution of a sub-dataset. They work well for uniform distribution of a sub-dataset while suffer low sampling efficiency and poor estimation accuracy on unevenly distributed sub-datasets. To address the problem, we develop a distribution aware method called Sapprox. Our idea is to collect the occurrences of a sub-dataset at each logical partition of a dataset (storage distribution) in the distributed system, and make good use of such information to facilitate online sampling. There are three thrusts in Sapprox. First, we develop a probabilistic map to reduce the exponential number of recorded sub-datasets to a linear one. Second, we apply the cluster sampling with unequal probability theory to implement a distribution-aware sampling method for efficient online sub-dataset sampling. Third, we quantitatively derive the optimal sampling unit size in a distributed file system by associating it with approximation costs and accuracy. We have implemented Sapprox into Hadoop ecosystem as an example system and open sourced it on GitHub. Our comprehensive experimental results show that Sapprox can achieve a speedup by up to 20× over the precise execution.