  Performance of clustering algorithms is evaluated with the help of accuracy
metrics. There is a great diversity of clustering algorithms, which are key
components of many data analysis and exploration systems. However, there exist
only few metrics for the accuracy measurement of overlapping and
multi-resolution clustering algorithms on large datasets. In this paper, we
first discuss existing metrics, how they satisfy a set of formal constraints,
and how they can be applied to specific cases. Then, we propose several
optimizations and extensions of these metrics. More specifically, we introduce
a new indexing technique to reduce both the runtime and the memory complexity
of the Mean F1 score evaluation. Our technique can be applied on large datasets
and it is faster on a single CPU than state-of-the-art implementations running
on high-performance servers. In addition, we propose several extensions of the
discussed metrics to improve their effectiveness and satisfaction to formal
constraints without affecting their efficiency. All the metrics discussed in
this paper are implemented in C++ and are available for free as open-source
packages that can be used either as stand-alone tools or as part of a
benchmarking system to compare various clustering algorithms.
