Cover Image

Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bessa, Aline, Daliri, Majid, Freire, Juliana, Musco, Cameron, Musco, Christopher, Santos, Aécio, Zhang, Haoxiang
Format:	Preprint
Published:	2023
Subjects:	Databases Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sampling Methods for Inner Product Sketching
by: Daliri, Majid, et al.
Published: (2023)

Simple Analysis of Priority Sampling
by: Daliri, Majid, et al.
Published: (2023)

Correlation Sketches for Approximate Join-Correlation Queries
by: Santos, Aécio, et al.
Published: (2021)

Matrix Product Sketching via Coordinated Sampling
by: Daliri, Majid, et al.
Published: (2025)

Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
by: Diwan, Haya, et al.
Published: (2024)

Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
by: Al-Jazzazi, Yousef, et al.
Published: (2025)

Coupling without Communication and Drafter-Invariant Speculative Decoding
by: Daliri, Majid, et al.
Published: (2024)

Stability of the Lanczos Method for Matrix Function Approximation
by: Musco, Cameron, et al.
Published: (2017)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

QSketch: An Efficient Sketch for Weighted Cardinality Estimation in Streams
by: Qi, Yiyan, et al.
Published: (2024)

A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
by: Doney, Kyle, et al.
Published: (2025)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
by: Musco, Cameron, et al.
Published: (2024)

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
by: Dereziński, Michał, et al.
Published: (2024)

Near-optimal hierarchical matrix approximation from matrix-vector products
by: Chen, Tyler, et al.
Published: (2024)

Fixed-sparsity matrix approximation from matrix-vector products
by: Amsel, Noah, et al.
Published: (2024)

TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate
by: Zandieh, Amir, et al.
Published: (2025)

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Efficiently Constructing Sparse Navigable Graphs
by: Conway, Alex, et al.
Published: (2025)

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs
by: De Man, Quinten, et al.
Published: (2026)

PHast -- Perfect Hashing made fast
by: Beling, Piotr, et al.
Published: (2025)

Approaching 100% Confidence in Stream Summary through ReliableSketch
by: Wu, Yuhan, et al.
Published: (2024)

Diversity-Aware $k$-Maximum Inner Product Search Revisited
by: Huang, Qiang, et al.
Published: (2024)

SplineSketch: Even More Accurate Quantiles with Error Guarantees
by: Łukasiewicz, Aleksander, et al.
Published: (2025)

Query Efficient Structured Matrix Learning
by: Amsel, Noah, et al.
Published: (2025)

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
by: Jin, Yujia, et al.
Published: (2024)

An Exact Algorithm for the Unanimous Vote Problem
by: Keles, Feyza Duman, et al.
Published: (2025)

Sampling Space-Saving Set Sketches
by: Lee, Homin K., et al.
Published: (2024)

Weighted Set Multi-Cover on Bounded Universe and Applications in Package Recommendation
by: Shahbazi, Nima, et al.
Published: (2026)

Improved Spectral Density Estimation via Explicit and Implicit Deflation
by: Bhattacharjee, Rajarshi, et al.
Published: (2024)

Optimal Matrix Sketching over Sliding Windows
by: Yin, Hanyan, et al.
Published: (2024)

Accelerating Graph Similarity Search through Integer Linear Programming
by: D'Ascenzo, Andrea, et al.
Published: (2025)

Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
by: Im, Sungjin, et al.
Published: (2025)

Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries
by: Lebeda, Christian Janos, et al.
Published: (2025)

Harmonic Decomposition in Data Sketches
by: Wang, Dingyu
Published: (2024)

MUVERA: Multi-Vector Retrieval via Fixed Dimensional Encodings
by: Dhulipala, Laxman, et al.
Published: (2024)

Quantum Sketches, Hashing, and Approximate Nearest Neighbors
by: Hashemian, Sajjad
Published: (2026)

JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets
by: Ertl, Otmar
Published: (2024)

On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
by: Stoian, Mihail, et al.
Published: (2022)

Fine-Grained Dichotomies for Conjunctive Queries with Minimum or Maximum
by: Carmeli, Nofar, et al.
Published: (2025)

Improved Approximation Algorithms for Relational Clustering
by: Esmailpour, Aryan, et al.
Published: (2024)