Better Size Estimation for Sparse Matrix Products

We consider the problem of doing fast and reliable estimation of the number of non-zero entries in a sparse Boolean matrix product. Let n denote the total number of non-zero entries in the input matrices. We show how to compute a 1 ± ε approximation (with small probability of error) in expected time O(n) for any ε > 4*(n^(-1/4)). The previously best estimation algorithm, due to Cohen (JCSS 1997), uses time O(n/ε^2). We also present a variant using O(sort(n)) I/Os in expectation in the cache-oblivious model.
We also describe how sampling can be used to maintain (independent) sketches of matrices that allow estimation to be performed in time o(n) if z is sufficiently large. This gives a simpler alternative to the sketching technique of Ganguly et al. (PODS 2005), and matches a space lower bound shown in that paper.