Sampling Methods for Inner Product Sketching

Summary: Introduce two linear-time sampling-based inner-product sketches (threshold and priority sampling) that are far cheaper than Bessa et al.'s coordinated weighted sampling and empirically outperform JL/CountSketch. Provide new approximation guarantees and state-of-the-art accuracy for tasks like estimating column correlations in unjoined tables. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13638
Venue: VLDB
Year: 2024
Pagerank: 5.4574671e-05
Overall Rank: 8,252 | 43.39%
DOI: 10.14778/3665844.3665850

Incoming Non-self Citations Over Time

Authors

1. Majid Daliri (New York University)
2. Juliana Freire (New York University)
3. Christopher Musco (New York University)
4. Aécio Santos (New York University)
5. Haoxiang Zhang (New York University)

BibTeX Citation

@article{daliri_vldb24,
        title = {{Sampling Methods for Inner Product Sketching}},
        author = {Daliri, Majid and Freire, Juliana and Musco, Christopher and Santos, Aécio and Zhang, Haoxiang},
        journal = {PVLDB},
        series = {{VLDB} '24},
        volume = {17},
        number = {9},
        pages = {2185--2197},
        doi = {10.14778/3665844.3665850},
        url = {https://doi.org/10.14778/3665844.3665850},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,293	Magneto: Combining Small and Large Language Models for Schema Matching	2025	VLDB	6.279939e-05
10,162	On Sketching Trimmed Statistics	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
689	On Synopses for Distinct-Value Estimation Under Multiset Operations	2007	SIGMOD	0.00014940023
737	Join Size Estimation Subject to Filter Conditions	2015	VLDB	0.00014490983
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
1,121	ARDA: Automatic Relational Data Augmentation for Machine Learning	2020	VLDB	0.00012093059
1,495	LSH Ensemble: Internet-Scale Domain Search	2016	VLDB	0.00010571481
1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	0.00010070362
3,228	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	7.6215176e-05
3,795	Is Min-Wise Hashing Optimal for Summarizing Set Intersection?	2014	PODS	7.1200458e-05
4,761	Estimating arbitrary subset sums with few probes	2005	PODS	6.5196044e-05
5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB	6.0155431e-05
8,379	Sampling Big Ideas in Query Optimization	2023	PODS	5.4378437e-05
11,374	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,379	Sampling Big Ideas in Query Optimization	2023	PODS
2	10,186	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD
3	2,878	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD
4	10,168	Tight Lower Bounds for l2 Sampling	2026	PODS
5	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
6	737	Join Size Estimation Subject to Filter Conditions	2015	VLDB
7	5,995	Coordinated Weighted Sampling for Estimating Aggregates Over Multiple Weight Assignments	2009	VLDB
8	3,215	Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates	2019	CIDR
9	9,027	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD
10	11,374	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS