IncApprox: A Data Analytics System for Incremental Approximate Computing
IncApprox: A Data Analytics System for Incremental Approximate Computing
复制标题
DOI：
10.1145/2872427.2883026
复制
发表时间：
2016-04
期刊：
影响因子：
--
通讯作者：
Dhanya R. Krishnan;D. Quoc;Pramod Bhatotia;C. Fetzer;R. Rodrigues
中科院分区：
文献类型：
--
作者：
Dhanya R. Krishnan;D. Quoc;Pramod Bhatotia;C. Fetzer;R. Rodrigues
越来越多地采用了增量和近似计算，以实现低延迟执行和计算资源的有效利用。增量计算会逐步更新输出，而不是从头开始重新计算所有内容，以连续运行输入更改。近似计算返回作业的近似输出，而不是确切的输出。这两个范式都依赖于在数据项的一个子集上计算，而不是在整个数据集上计算计算，但是它们在跳过计算部分的手段上有所不同。增量计算取决于子计算中间结果的记忆，并在工作中重复了这些记忆的结果。近似计算依赖于整个数据集的代表性采样来计算数据项的子集。在本文中，我们观察到这两个范式是互补的，可以一起结婚！我们的想法非常简单：设计一种抽样算法，该算法将样本选择偏向于先前运行中的记忆数据项。为了实现这一想法，我们设计了一种在线分层采样算法，该算法使用自调整计算来产生具有有界误差的增量更新的近似输出。我们在基于Apache Spark流的名为Incapprox的数据分析系统中实现了算法。我们使用微基准和现实世界的案例研究的评估表明，Incapprox可以实现增量和近似计算的好处。
Incremental and approximate computations are increasingly being adopted for data analytics to achieve low-latency execution and efficient utilization of computing resources. Incremental computation updates the output incrementally instead of re-computing everything from scratch for successive runs of a job with input changes. Approximate computation returns an approximate output for a job instead of the exact output. Both paradigms rely on computing over a subset of data items instead of computing over the entire dataset, but they differ in their means for skipping parts of the computation. Incremental computing relies on the memoization of intermediate results of sub-computations, and reusing these memoized results across jobs. Approximate computing relies on representative sampling of the entire dataset to compute over a subset of data items. In this paper, we observe that these two paradigms are complementary, and can be married together! Our idea is quite simple: design a sampling algorithm that biases the sample selection to the memoized data items from previous runs. To realize this idea, we designed an online stratified sampling algorithm that uses self-adjusting computation to produce an incrementally updated approximate output with bounded error. We implemented our algorithm in a data analytics system called IncApprox based on Apache Spark Streaming. Our evaluation using micro-benchmarks and real-world case-studies shows that IncApprox achieves the benefits of both incremental and approximate computing.