Many applications need to quantify the similarity between two clusterings of a data set. For example, one good way to assess the quality of a clustering method is to compare its output to a known ground truth. This paper considers scenarios where it is desirable or even necessary to estimate the similarity between two clusterings. Dozens of clustering similarity measures have been invented, yet most of them are based on pair counting or on concepts of information theory. We investigate how to estimate both kinds of measures accurately and quickly, given a random sample of data point pairs or of individual data points. One of our main contributions is the mathematical analysis of the bias and variance of these estimators, in terms of the sample size t. They either are unbiased or have a bias of \(\mathcal {O}(1/t)\) , and have a variance of \(\mathcal {O}(1/t)\) . Our results cover virtually every known pair-counting index, and some of the most popular information-theoretic measures. Regarding computational complexity, the estimates can be obtained in \(\mathcal {O}(t)\) time and space by using appropriate data structures. Sometimes these costs include an additional term of order \(c\cdot c'\) , where \(c\) and \(c'\) are the respective number of clusters in the two clusterings being compared. Preliminary experimental results agree well with our theoretical findings.