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

    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.
    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
    PublisherSpringer
    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
    http://cui.unige.ch/tcs/random-approx/2010/

    Workshop

    WorkshopApprox 2010 + Random 2010
    Country/TerritorySpain
    CityBarcelona
    Period01/09/201003/09/2010
    Internet address

    Keywords

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

    Fingerprint

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

    Cite this