Dimension Independent Similarity Computation
This work addresses a critical bottleneck for large-scale data analysis in social networks by enabling efficient similarity computations without dimension constraints, though it is incremental as it builds on existing similarity measures and frameworks like MapReduce.
The authors tackled the problem of computing pairwise similarities between very high-dimensional sparse vectors efficiently, introducing DISCO algorithms that are provably dimension-independent and achieving practical deployment at Twitter with empirical validation at large scale.
We present a suite of algorithms for Dimension Independent Similarity Computation (DISCO) to compute all pairwise similarities between very high dimensional sparse vectors. All of our results are provably independent of dimension, meaning apart from the initial cost of trivially reading in the data, all subsequent operations are independent of the dimension, thus the dimension can be very large. We study Cosine, Dice, Overlap, and the Jaccard similarity measures. For Jaccard similiarity we include an improved version of MinHash. Our results are geared toward the MapReduce framework. We empirically validate our theorems at large scale using data from the social networking site Twitter. At time of writing, our algorithms are live in production at twitter.com.