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: h6d7a19c1c98747a3
Venue: VLDB
Year: 2017
Pagerank: 5.2708103e-05
Overall Rank: 8,815 | 40.74%
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,180	On-Off Sketch: A Fast and Accurate Sketch on Persistence	2021	VLDB	5.5928753e-05
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-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
49	Dremel: Interactive Analysis of Web-Scale Datasets	2010	VLDB	0.00043160717
1,066	Sketching Streams Through the Net: Distributed Approximate Query Tracking	2005	VLDB	0.00012192801
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
6,121	The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication	2015	PODS	5.8800995e-05
7,955	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD	5.4185826e-05

Semantically Similar Papers

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