## 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.

Original language | English |
---|---|

Title of host publication | 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 |

Number of pages | 14 |

Publisher | Springer |

Publication date | 1 Sept 2010 |

ISBN (Print) | 978-3-642-15368-6 |

Publication status | Published - 1 Sept 2010 |

Event | Approx 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 2010 → 3 Sept 2010 http://cui.unige.ch/tcs/random-approx/2010/ |

### Workshop

Workshop | Approx 2010 + Random 2010 |
---|---|

Country/Territory | Spain |

City | Barcelona |

Period | 01/09/2010 → 03/09/2010 |

Internet address |

## Keywords

- Sparse Matrix Estimation
- Boolean Matrix Multiplication
- Probabilistic Approximation
- Cache-Oblivious Algorithms
- Matrix Sketching Techniques