  Correlation clustering is perhaps the most natural formulation of clustering.
Given $n$ objects and a pairwise similarity measure, the goal is to cluster the
objects so that, to the best possible extent, similar objects are put in the
same cluster and dissimilar objects are put in different clusters. Despite its
theoretical appeal, the practical relevance of correlation clustering still
remains largely unexplored, mainly due to the fact that correlation clustering
requires the $\Theta(n^2)$ pairwise similarities as input.
  In this paper we initiate the investigation into \emph{local} algorithms for
correlation clustering. In \emph{local correlation clustering} we are given the
identifier of a single object and we want to return the cluster to which it
belongs in some globally consistent near-optimal clustering, using a small
number of similarity queries. Local algorithms for correlation clustering open
the door to \emph{sublinear-time} algorithms, which are particularly useful
when the similarity between items is costly to compute, as it is often the case
in many practical application domains. They also imply $(i)$ distributed and
streaming clustering algorithms, $(ii)$ constant-time estimators and testers
for cluster edit distance, and $(iii)$ property-preserving parallel
reconstruction algorithms for clusterability.
  Specifically, we devise a local clustering algorithm attaining a $(3,
\varepsilon)$-approximation in time $O(1/\varepsilon^2)$ independently of the
dataset size. An explicit approximate clustering for all objects can be
produced in time $O(n/\varepsilon)$ (which is provably optimal). We also
provide a fully additive $(1,\varepsilon)$-approximation with local query
complexity $poly(1/\varepsilon)$ and time complexity $2^{poly(1/\varepsilon)}$.
The latter yields the fastest polynomial-time approximation scheme for
correlation clustering known to date.
