Abstract
We consider the problem of doing fast and reliable estimation of the number z of non-zero entries in a sparse boolean matrix product. This problem has applications in databases and computer algebra. Finally, we present experiments on real-world data sets that show the accuracy of both our methods to be significantly better than the worstcase analysis predicts.
| Originalsprog | Engelsk |
|---|---|
| Tidsskrift | Algorithmica |
| Vol/bind | 69 |
| Udgave nummer | 3 |
| Sider (fra-til) | 741-757 |
| ISSN | 0178-4617 |
| Status | Udgivet - jul. 2013 |
Emneord
- Algorithms
- Matrix multiplication
- Relational algebra
- Theory