TY - GEN
T1 - Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
AU - Bessa, Aline
AU - Daliri, Majid
AU - Freire, Juliana
AU - Musco, Cameron
AU - Musco, Christopher
AU - Santos, Aecio
AU - Zhang, Haoxiang
N1 - Publisher Copyright:
© 2023 ACM.
PY - 2023/6/18
Y1 - 2023/6/18
N2 - We present a new approach for independently computing compact sketches that can be used to approximate the inner product between pairs of high-dimensional vectors. Based on the Weighted MinHash algorithm, our approach admits strong accuracy guarantees that improve on the guarantees of popular linear sketching approaches for inner product estimation, such as CountSketch and Johnson-Lindenstrauss projection. Specifically, while our method exactly matches linear sketching for dense vectors, it yields significantly lower error for sparse vectors with limited overlap between non-zero entries. Such vectors arise in many applications involving sparse data, as well as in increasingly popular dataset search applications, where inner products are used to estimate data covariance, conditional means, and other quantities involving columns in unjoined tables. We complement our theoretical results by showing that our approach empirically outperforms existing linear sketches and unweighted hashing-based sketches for sparse vectors.
AB - We present a new approach for independently computing compact sketches that can be used to approximate the inner product between pairs of high-dimensional vectors. Based on the Weighted MinHash algorithm, our approach admits strong accuracy guarantees that improve on the guarantees of popular linear sketching approaches for inner product estimation, such as CountSketch and Johnson-Lindenstrauss projection. Specifically, while our method exactly matches linear sketching for dense vectors, it yields significantly lower error for sparse vectors with limited overlap between non-zero entries. Such vectors arise in many applications involving sparse data, as well as in increasingly popular dataset search applications, where inner products are used to estimate data covariance, conditional means, and other quantities involving columns in unjoined tables. We complement our theoretical results by showing that our approach empirically outperforms existing linear sketches and unweighted hashing-based sketches for sparse vectors.
KW - inner product estimation
KW - join-size estimation
KW - vector sketching
UR - http://www.scopus.com/inward/record.url?scp=85164256649&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85164256649&partnerID=8YFLogxK
U2 - 10.1145/3584372.3588679
DO - 10.1145/3584372.3588679
M3 - Conference contribution
AN - SCOPUS:85164256649
T3 - Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems
SP - 169
EP - 181
BT - PODS 2023 - Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PB - Association for Computing Machinery
T2 - 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023
Y2 - 18 June 2023 through 23 June 2023
ER -