Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation

Aline Bessa, Majid Daliri, Juliana Freire, Cameron Musco, Christopher Musco, Aecio Santos, Haoxiang Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationPODS 2023 - Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherAssociation for Computing Machinery
Pages169-181
Number of pages13
ISBN (Electronic)9798400701276
DOIs
StatePublished - Jun 18 2023
Event42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023 - Seattle, United States
Duration: Jun 18 2023Jun 23 2023

Publication series

NameProceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems

Conference

Conference42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2023
Country/TerritoryUnited States
CitySeattle
Period6/18/236/23/23

Keywords

  • inner product estimation
  • join-size estimation
  • vector sketching

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation'. Together they form a unique fingerprint.

Cite this