Bias-Aware Sketches

Summary: Introduces bias-aware linear sketches that account for systematic coordinate bias, avoiding the large tail-mass errors that undermine standard sketches. Proves strictly stronger guarantees and validates practical gains on real and synthetic distributed/streaming workloads. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 11776
Venue: VLDB
Year: 2017
Pagerank: 5.3914428e-05
Overall Rank: 8,653 | 40.64%
DOI: 10.14778/3099622.3099624

Incoming Non-self Citations Over Time

Authors

1. Jiecao Chen (Indiana University)
2. Qin Zhang (Indiana University)

BibTeX Citation

@article{chen_vldb17,
        title = {{Bias-Aware Sketches}},
        author = {Chen, Jiecao and Zhang, Qin},
        journal = {PVLDB},
        series = {{VLDB} '17},
        volume = {10},
        number = {9},
        pages = {961--972},
        doi = {10.14778/3099622.3099624},
        url = {https://doi.org/10.14778/3099622.3099624},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,036	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.7212447e-05
8,204	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4667903e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
51	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.0004291425
1,045	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012440928
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
5,996	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	6.0150613e-05
7,795	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD	5.5429229e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,503	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB
2	4,142	Statistical Analysis of Sketch Estimators	2007	SIGMOD
3	10,427	AeroSketch: Near-Optimal Time Matrix Sketch Framework for Persistent, Sliding Window, and Distributed Streams	2026	SIGMOD
4	1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD
5	11,374	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS
6	8,268	Efficient Matrix Sketching over Distributed Data	2017	PODS
7	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
8	9,027	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD
9	1,146	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS
10	3,445	Sketching Linear Classifiers over Data Streams	2018	SIGMOD