A more efficient algorithm to compute the Rand Index for change-point problems

Abstract

We provide a more efficient algorithm for computing the Rand Index when the data clusters come from a change-point detection problem. Given the number of data points $N$ and two change-point sets of size $r$ and $s$, the algorithm runs on $O(r+s)$ time complexity and $O(1)$ memory complexity. The Rand Index computation for the general clustering problem, in contrast, requires the $N$ cluster memberships and has a $O(N)$ complexity in both time and memory.