Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform
Summary: Survey of hashing-based sketching primitives that enable single-pass, sublinear-space approximation of counts and heavy hitters in data streams. Explores how these hash-sketch variants unify and propel algorithmic advances in compressive sensing, dimensionality reduction, and sparse FFT. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Piotr Indyk
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,901 | Streaming Algorithms with Few State Changes | 2024 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 597 | Computing Iceberg Queries Efficiently | 1998 | VLDB | 0.00019475592 |
| 781 | Spectral Bloom Filters | 2003 | SIGMOD | 0.00016741046 |
| 865 | What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically | 2003 | PODS | 0.00015808172 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,034 | SieveSketch: A Fine-grained and Adaptive Sketch Framework for Accurate Frequency Estimation | 2026 | SIGMOD | 4.1945683e-05 |
| 8,635 | Bidirectionally Densifying LSH Sketches with Empty Bins | 2021 | SIGMOD | 4.4801584e-05 |
| 344 | Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries | 2001 | VLDB | 0.00026702512 |
| 3,056 | DSH: Data Sensitive Hashing for High-Dimensional k-NN Search | 2014 | SIGMOD | 7.6432146e-05 |
| 605 | Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting | 2012 | SIGMOD | 0.000193396 |
| 8,720 | Entropy-Learned Hashing: Constant Time Hashing with Controllable Uniformity | 2022 | SIGMOD | 4.4609699e-05 |
| 1,040 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS | 0.00014488943 |
| 34 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00076637636 |
| 5,224 | Neighbor-Sensitive Hashing | 2016 | VLDB | 5.6197981e-05 |
| 11,168 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS | 4.1945683e-05 |