Better Size Estimation for Sparse Matrix Products

Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer 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.
TitelAPPROX 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
Antal sider14
Publikationsdato1 sep. 2010
ISBN (Trykt)978-3-642-15368-6
StatusUdgivet - 1 sep. 2010
BegivenhedApprox 2010 + Random 2010: 13th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 14th Intl. Workshop on Randomization and Computation - Barcelona, Spanien
Varighed: 1 sep. 20103 sep. 2010


WorkshopApprox 2010 + Random 2010


Dyk ned i forskningsemnerne om 'Better Size Estimation for Sparse Matrix Products'. Sammen danner de et unikt fingeraftryk.