  Over the past a few years, research and development has made significant
progresses on big data analytics. A fundamental issue for big data analytics is
the efficiency. If the optimal solution is unable to attain or not required or
has a price to high to pay, it is reasonable to sacrifice optimality with a
`good' feasible solution that can be computed efficiently. Existing
approximation techniques can be in general classified into approximation
algorithms, approximate query processing for aggregate SQL queries and
approximation computing for multiple layers of the system stack. In this
article, we systematically introduce approximate computation, i.e., query
approximation and data approximation, for efficiency and effectiveness big data
analytics. We first explain the idea and rationale of query approximation, and
show efficiency can be obtained with high effectiveness in practice with three
analytic tasks: graph pattern matching, trajectory compression and dense
subgraph computation. We then explain the idea and rationale of data
approximation, and show efficiency can be obtained even without sacrificing for
effectiveness in practice with three analytic tasks: shortest paths/distances,
network anomaly detection and link prediction.

Databases