Better size estimation for sparse matrix products

Details Better size estimation for sparse matrix products Better size estimation for sparse matrix products

2010-06-21

arxiv.org/abs/1006.4173v2

Computer Science

Data Structures and Algorithms

Corrected a number of mistakes and typos in the first version (also present in the version published at RANDOM 2010). Most imp

Scientific paper

We consider the problem of doing fast and reliable estimation of the number of non-zero entries in a sparse boolean matrix product. This problem has applications in databases and computer algebra. Let n denote the total number of non-zero entries in the input matrices. We show how to compute a 1 +- epsilon approximation (with small probability of error) in expected time O(n) for any epsilon > 4/\sqrt[4]{z}. The previously best estimation algorithm, due to Cohen (JCSS 1997), uses time O(n/epsilon^2). We also present a variant using O(sort(n)) I/Os in expectation in the cache-oblivious model. In contrast to these results, the currently best algorithms for computing a sparse boolean matrix product use time omega(n^{4/3}) (resp. omega(n^{4/3}/B) I/Os), even if the result matrix has only z=O(n) nonzero entries. Our algorithm combines the size estimation technique of Bar-Yossef et al. (RANDOM 2002) with a particular class of pairwise independent hash functions that allows the sketch of a set of the form A x C to be computed in expected time O(|A|+|C|) and O(sort(|A|+|C|)) I/Os. We then 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. Finally, we present experiments on real-world data sets that show the accuracy of both our methods to be significantly better than the worst-case analysis predicts.

Affiliated with

Also associated with

No associations

Rating

Better size estimation for sparse matrix products does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Better size estimation for sparse matrix products, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Better size estimation for sparse matrix products will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107261