Better Size Estimation for Sparse Matrix Products

Rasmus Resen Amossen; Andrea Campagna; Rasmus Pagh

Better Size Estimation for Sparse Matrix Products

Rasmus Resen Amossen, Andrea Campagna, Rasmus Pagh

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer 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.

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

Emneord

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

Citationsformater

@inproceedings{3fc4f96a1d644cf097ec97a7a6c084c8,

title = "Better Size Estimation for Sparse Matrix Products",

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.",

keywords = "Sparse Matrix Estimation, Boolean Matrix Multiplication, Probabilistic Approximation, Cache-Oblivious Algorithms, Matrix Sketching Techniques, Sparse Matrix Estimation, Boolean Matrix Multiplication, Probabilistic Approximation, Cache-Oblivious Algorithms, Matrix Sketching Techniques",

author = "Amossen, {Rasmus Resen} and Andrea Campagna and Rasmus Pagh",

year = "2010",

month = sep,

day = "1",

language = "English",

isbn = "978-3-642-15368-6",

booktitle = "APPROX 2010 + RANDOM 2010 - Approximation, Randomization, and Combinatorial Oprimization",

publisher = "Springer",

address = "Germany",

note = "Approx 2010 + Random 2010 : 13th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 14th Intl. Workshop on Randomization and Computation , RANDOM APPROX 2010 ; Conference date: 01-09-2010 Through 03-09-2010",

url = "http://cui.unige.ch/tcs/random-approx/2010/",

}

Amossen, RR, Campagna, A & Pagh, R 2010, Better Size Estimation for Sparse Matrix Products. i 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. Springer, Approx 2010 + Random 2010, Barcelona, Spanien, 01/09/2010.

Better Size Estimation for Sparse Matrix Products. / Amossen, Rasmus Resen; Campagna, Andrea; Pagh, Rasmus.
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. Springer, 2010.

Publikation: Konference artikel i Proceeding eller bog/rapport kapitel › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Better Size Estimation for Sparse Matrix Products

AU - Amossen, Rasmus Resen

AU - Campagna, Andrea

AU - Pagh, Rasmus

PY - 2010/9/1

Y1 - 2010/9/1

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

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

KW - Sparse Matrix Estimation

KW - Boolean Matrix Multiplication

KW - Probabilistic Approximation

KW - Cache-Oblivious Algorithms

KW - Matrix Sketching Techniques

KW - Sparse Matrix Estimation

KW - Boolean Matrix Multiplication

KW - Probabilistic Approximation

KW - Cache-Oblivious Algorithms

KW - Matrix Sketching Techniques

M3 - Article in proceedings

SN - 978-3-642-15368-6

BT - APPROX 2010 + RANDOM 2010 - Approximation, Randomization, and Combinatorial Oprimization

PB - Springer

T2 - Approx 2010 + Random 2010

Y2 - 1 September 2010 through 3 September 2010

ER -

Better Size Estimation for Sparse Matrix Products

Abstract

Workshop

Emneord

Fingeraftryk

Citationsformater