Higher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations

Abstract

Sketching is a randomized dimensionality-reduction method that aims to preserve relevant information in large-scale datasets. Count sketch is a simple popular sketch which uses a randomized hash function to achieve compression. In this paper, we propose a novel extension known as Higher-order Count Sketch (HCS). While count sketch uses a single hash function, HCS uses multiple (smaller) hash functions for sketching. HCS reshapes the input (vector) data into a higher-order tensor and employs a tensor product of the random hash functions to compute the sketch. This results in an exponential saving (with respect to the order of the tensor) in the memory requirements of the hash functions, under certain conditions on the input data. Furthermore, when the input data itself has an underlying structure in the form of various tensor representations such as the Tucker decomposition, we obtain significant advantages. We derive efficient (approximate) computation of various tensor operations such

Stats

• citations3
• S2 citations—
• github stars0
• HF likes0
• heat score4.52
• arxiv keyshi2019higher

Related papers

• Weighted Minwise Hashing Beats Linear Sketching For Inner Product Estimation (2023)3.58
• Sketchmate: Deep Hashing For Million-scale Human Sketch Retrieval (2018)15.03
• Making Online Sketching Hashing Even Faster (2020)9.23
• Fast Similarity Sketching (2017)9.41
• Deepsketch: A New Machine Learning-based Reference Search Technique For Post-deduplication Delta Compression (2022)0.00
• Sketch Down The Flops: Towards Efficient Networks For Human Sketch (2025)0.00
• Clustering The Sketch: A Novel Approach To Embedding Table Compression (2022)0.00
• Sketching Without Worrying: Noise-tolerant Sketch-based Image Retrieval (2022)12.74