A more efficient algorithm to compute the Rand Index for change-point problems
In this paper we provide a more efficient algorithm to compute the Rand Index when the data cluster comes from change-point detection problems. Given N data points and two clusters of size r and s, the algorithm runs on O(r+s) time complexity and O(1) memory complexity. The traditional algorithm, in contrast, runs on O(rs+N) time complexity and O(rs) memory complexity.
READ FULL TEXT