Same-Cluster Querying for Overlapping Clusters
  Overlapping clusters are common in models of many practical data-segmentation
applications. Suppose we are given $n$ elements to be clustered into $k$
possibly overlapping clusters, and an oracle that can interactively answer
queries of the form "do elements $u$ and $v$ belong to the same cluster?" The
goal is to recover the clusters with minimum number of such queries. This
problem has been of recent interest for the case of disjoint clusters. In this
paper, we look at the more practical scenario of overlapping clusters, and
provide upper bounds (with algorithms) on the sufficient number of queries. We
provide algorithmic results under both arbitrary (worst-case) and statistical
modeling assumptions. Our algorithms are parameter free, efficient, and work in
the presence of random noise. We also derive information-theoretic lower bounds
on the number of queries needed, proving that our algorithms are order optimal.
Finally, we test our algorithms over both synthetic and real-world data,
showing their practicality and effectiveness.
