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)
Incoming Non-self Citations Over Time
Authors
- 1. Kai Sheng Tai (Stanford University)
- 2. Vatsal Sharan (Stanford University)
- 3. Peter Bailis (Stanford University)
- 4. Gregory Valiant (Stanford University)
BibTeX Citation
@inproceedings{tai_sigmod18,
title = {{Sketching Linear Classifiers over Data Streams}},
author = {Tai, Kai Sheng and Sharan, Vatsal and Bailis, Peter and Valiant, Gregory},
series = {{SIGMOD} '18},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3183713.3196930},
url = {https://dl.acm.org/doi/10.1145/3183713.3196930},
year = {2018}
}Incoming Citations (Sorted by Pagerank)
Showing 8 of 8 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,221 | Camel: Managing Data for Efficient Stream Learning | 2022 | SIGMOD | 7.6271601e-05 |
| 3,898 | BurstSketch: Finding Bursts in Data Streams | 2021 | SIGMOD | 7.0367583e-05 |
| 6,633 | Agile and Accurate CTR Prediction Model Training for Massive-Scale Online Advertising Systems | 2021 | SIGMOD | 5.8185371e-05 |
| 6,685 | Out of Many We are One: Measuring Item Batch with Clock-Sketch | 2021 | SIGMOD | 5.8034001e-05 |
| 7,716 | Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items | 2023 | SIGMOD | 5.5605526e-05 |
| 10,861 | Less is More: Efficient Time Series Dataset Condensation via Two-fold Modal Matching | 2025 | VLDB | 5.093636e-05 |
| 11,157 | Relative Keys: Putting Feature Explanation into Context | 2024 | SIGMOD | 5.093636e-05 |
| 11,196 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 5.093636e-05 |
Previous
Page 1 / 1
Next
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 |
|---|---|---|---|---|
| 82 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD | 0.00036378991 |
| 122 | Approximate Frequency Counts over Data Streams | 2002 | VLDB | 0.00031260115 |
| 191 | Scorpion: Explaining Away Outliers in Aggregate Queries | 2013 | VLDB | 0.00026096009 |
| 640 | Materialization Optimizations for Feature Selection Workloads | 2014 | SIGMOD | 0.00015409494 |
| 885 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00013419017 |
| 1,294 | Augmented Sketch: Faster and More Accurate Stream Processing | 2016 | SIGMOD | 0.00011291308 |
| 1,639 | Summingbird: A Framework for Integrating Batch and Online MapReduce Computations | 2014 | VLDB | 0.00010155021 |
| 1,792 | MacroBase: Prioritizing Attention in Fast Data | 2017 | SIGMOD | 9.7436856e-05 |
| 1,943 | Causality and Explanations in Databases | 2014 | VLDB | 9.440636e-05 |
| 4,005 | Fast Data Stream Algorithms using Associative Memories | 2007 | SIGMOD | 6.9643802e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 2,878 | Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation | 2018 | SIGMOD |
| 2 | 11,503 | Bayesian Sketches for Volume Estimation in Data Streams | 2023 | VLDB |
| 3 | 11,196 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD |
| 4 | 1,294 | Augmented Sketch: Faster and More Accurate Stream Processing | 2016 | SIGMOD |
| 5 | 1,146 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS |
| 6 | 8,666 | Efficient framework for operating on data sketches | 2023 | VLDB |
| 7 | 8,310 | TreeSensing: Linearly Compressing Sketches with Flexibility | 2023 | SIGMOD |
| 8 | 4,083 | SketchML: Accelerating Distributed Machine Learning with Data Sketches | 2018 | SIGMOD |
| 9 | 8,653 | Bias-Aware Sketches | 2017 | VLDB |
| 10 | 11,374 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS |