  Most data analytics systems that require low-latency execution and efficient
utilization of computing resources, increasingly adopt two computational
paradigms, namely, incremental and approximate computing. 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 for sub-computations that are unaffected by the changed input.
Approximate computing relies on representative sampling of the entire dataset
to compute over a subset of data items.
  In this thesis, we make the observation that these two computing paradigms
are complementary, and can be married together! The high level idea is to:
design a sampling algorithm that biases the sample selection to the memoized
data items from previous runs. To concretize 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 IncAppox based on Apache Spark
Streaming. Our evaluation of the system shows that IncApprox achieves the
benefits of both incremental and approximate computing.
