Incremental Approximate Computing

Approximate computing is increasingly used for speeding up computations and efficiently utilizing the computing resources. The idea behind approximate computing is to return an approximate answer instead of the exact answer for user queries. The trick is to choose a representative sample of the data for computing instead of using the entire data. As a result, it allows users to trade-off query accuracy for response time, enabling interactive queries over massive data by running queries on data samples and presenting results annotated with meaningful error bars. At the same time, another technique called incremental computing tries to achieve the same goals as approximate computing, i.e., speeding up job execution and utilizing resource efficiently. Incremental computing relies on the memoization of intermediate results of sub-computations, and reusing these memoized results across jobs.

This work makes the observation that these two computing paradigms are complementary, and can be married together! The 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, an online stratified sampling algorithm is designed.

The algorithm uses self-adjusting computation to produce an incrementally updated approximate output with bounded error. The algorithm is implemented in a data analytics system called INCAPPROX.