Efficient Active Algorithms for Hierarchical Clustering
  Advances in sensing technologies and the growth of the internet have resulted
in an explosion in the size of modern datasets, while storage and processing
power continue to lag behind. This motivates the need for algorithms that are
efficient, both in terms of the number of measurements needed and running time.
To combat the challenges associated with large datasets, we propose a general
framework for active hierarchical clustering that repeatedly runs an
off-the-shelf clustering algorithm on small subsets of the data and comes with
guarantees on performance, measurement complexity and runtime complexity. We
instantiate this framework with a simple spectral clustering algorithm and
provide concrete results on its performance, showing that, under some
assumptions, this algorithm recovers all clusters of size ?(log n) using O(n
log^2 n) similarities and runs in O(n log^3 n) time for a dataset of n objects.
Through extensive experimentation we also demonstrate that this framework is
practically alluring.
