Better Size Estimation for Sparse Matrix Products

Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh

Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationAPPROX 2010 + RANDOM 2010 - Approximation, Randomization, and Combinatorial Oprimization : Proceedings of the 13th international workshop Approx 2010 and 14th International workshop Random 2010, Barcelona, Spain, September 2010
Number of pages14
Publication date1 Sept 2010
ISBN (Print)978-3-642-15368-6
Publication statusPublished - 1 Sept 2010
EventApprox 2010 + Random 2010: 13th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 14th Intl. Workshop on Randomization and Computation - Barcelona, Spain
Duration: 1 Sept 20103 Sept 2010


WorkshopApprox 2010 + Random 2010
Internet address


Dive into the research topics of 'Better Size Estimation for Sparse Matrix Products'. Together they form a unique fingerprint.

Cite this