Sketching Linear Classifiers over Data Streams

Summary: Weight-Median Sketch: sub-linear space for learning compressed linear classifiers over data streams, enabling recovery of large weights under memory limits. Unlike frequency-based sketches, it targets discriminative features via gradient-based updates with recovery guarantees, yielding improved memory-accuracy over count-sketches and feature hashing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5576
Venue: SIGMOD
Year: 2018
Pagerank: 7.226439e-05
Overall Rank: 3,319 | 76.92%
DOI: 10.1145/3183713.3196930

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,643	Camel: Managing Data for Efficient Stream Learning	2022	SIGMOD	8.384956e-05
3,751	BurstSketch: Finding Bursts in Data Streams	2021	SIGMOD	6.7888099e-05
6,593	Out of Many We are One: Measuring Item Batch with Clock-Sketch	2021	SIGMOD	4.9999287e-05
6,738	Agile and Accurate CTR Prediction Model Training for Massive-Scale Online Advertising Systems	2021	SIGMOD	4.9452647e-05
7,732	Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items	2023	SIGMOD	4.6657123e-05
10,601	Less is More: Efficient Time Series Dataset Condensation via Two-fold Modal Matching	2025	VLDB	4.1945683e-05
10,939	Relative Keys: Putting Feature Explanation into Context	2024	SIGMOD	4.1945683e-05
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
166	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00039361552
214	Scorpion: Explaining Away Outliers in Aggregate Queries	2013	VLDB	0.0003363692
761	Materialization Optimizations for Feature Selection Workloads	2014	SIGMOD	0.00017053783
835	Finding Frequent Items in Data Streams	2008	VLDB	0.00016109621
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
1,794	Summingbird: A Framework for Integrating Batch and Online MapReduce Computations	2014	VLDB	0.00010532024
2,126	MacroBase: Prioritizing Attention in Fast Data	2017	SIGMOD	9.4887794e-05
2,402	Causality and Explanations in Databases	2014	VLDB	8.8928361e-05
3,860	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.6902516e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,271	Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation	2018	SIGMOD	7.2968732e-05
11,304	Bayesian Sketches for Volume Estimation in Data Streams	2023	VLDB	4.1945683e-05
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05
1,584	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011255801
1,040	Graph Sketches: Sparsification, Spanners, and Subgraphs	2012	PODS	0.00014488943
8,451	Efficient framework for operating on data sketches	2023	VLDB	4.5086031e-05
9,041	TreeSensing: Linearly Compressing Sketches with Flexibility	2023	SIGMOD	4.4039656e-05
3,808	SketchML: Accelerating Distributed Machine Learning with Data Sketches	2018	SIGMOD	6.7455428e-05
8,599	Bias-Aware Sketches	2017	VLDB	4.4879268e-05
11,168	Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation	2023	PODS	4.1945683e-05