Abstract
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.
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.
| Originalsprog | Engelsk |
|---|---|
| Titel | APPROX 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 sider | 14 |
| Forlag | Springer |
| Publikationsdato | 1 sep. 2010 |
| ISBN (Trykt) | 978-3-642-15368-6 |
| Status | Udgivet - 1 sep. 2010 |
| Begivenhed | Approx 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. 2010 → 3 sep. 2010 http://cui.unige.ch/tcs/random-approx/2010/ |
Workshop
| Workshop | Approx 2010 + Random 2010 |
|---|---|
| Land/Område | Spanien |
| By | Barcelona |
| Periode | 01/09/2010 → 03/09/2010 |
| Internetadresse |