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,284 | Camel: Managing Data for Efficient Stream Learning | 2022 | SIGMOD | 7.4560271e-05 |
| 3,980 | BurstSketch: Finding Bursts in Data Streams | 2021 | SIGMOD | 6.8788724e-05 |
| 6,754 | Agile and Accurate CTR Prediction Model Training for Massive-Scale Online Advertising Systems | 2021 | SIGMOD | 5.6902479e-05 |
| 6,816 | Out of Many We are One: Measuring Item Batch with Clock-Sketch | 2021 | SIGMOD | 5.6731874e-05 |
| 7,873 | Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items | 2023 | SIGMOD | 5.4357887e-05 |
| 11,264 | Less is More: Efficient Time Series Dataset Condensation via Two-fold Modal Matching | 2025 | VLDB | 4.9793485e-05 |
| 11,504 | Relative Keys: Putting Feature Explanation into Context | 2024 | SIGMOD | 4.9793485e-05 |
| 11,538 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD | 4.9793485e-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 |
|---|---|---|---|---|
| 83 | Space-Efficient Online Computation of Quantile Summaries | 2001 | SIGMOD | 0.00035978046 |
| 124 | Approximate Frequency Counts over Data Streams | 2002 | VLDB | 0.00030600691 |
| 189 | Scorpion: Explaining Away Outliers in Aggregate Queries | 2013 | VLDB | 0.00025840026 |
| 654 | Materialization Optimizations for Feature Selection Workloads | 2014 | SIGMOD | 0.0001510357 |
| 909 | Finding Frequent Items in Data Streams | 2008 | VLDB | 0.00013125647 |
| 1,319 | Augmented Sketch: Faster and More Accurate Stream Processing | 2016 | SIGMOD | 0.00011045888 |
| 1,633 | Summingbird: A Framework for Integrating Batch and Online MapReduce Computations | 2014 | VLDB | 0.00010019617 |
| 1,833 | MacroBase: Prioritizing Attention in Fast Data | 2017 | SIGMOD | 9.5405247e-05 |
| 1,981 | Causality and Explanations in Databases | 2014 | VLDB | 9.2586863e-05 |
| 4,097 | Fast Data Stream Algorithms using Associative Memories | 2007 | SIGMOD | 6.8092798e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 2,930 | Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation | 2018 | SIGMOD |
| 2 | 11,812 | Bayesian Sketches for Volume Estimation in Data Streams | 2023 | VLDB |
| 3 | 11,538 | A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions | 2024 | SIGMOD |
| 4 | 1,169 | Graph Sketches: Sparsification, Spanners, and Subgraphs | 2012 | PODS |
| 5 | 1,319 | Augmented Sketch: Faster and More Accurate Stream Processing | 2016 | SIGMOD |
| 6 | 8,835 | Efficient framework for operating on data sketches | 2023 | VLDB |
| 7 | 8,477 | TreeSensing: Linearly Compressing Sketches with Flexibility | 2023 | SIGMOD |
| 8 | 3,872 | SketchML: Accelerating Distributed Machine Learning with Data Sketches | 2018 | SIGMOD |
| 9 | 8,815 | Bias-Aware Sketches | 2017 | VLDB |
| 10 | 11,690 | Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation | 2023 | PODS |