5 papers
Sampling in Distributed Data Streams with Applications to Adversarial Robustness
Honghao Lin, Zhao Song, David P. Woodruff +2
In the distributed monitoring model, a data stream over a universe of size is distributed over servers, who must continuously provide certain statistics of the overall data…
Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie +1
We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph with nodes, hyperedges, and rank , an…
Transductive and Learning-Augmented Online Regression
Vinod Raman, Shenghao Xie, Samson Zhou
Motivated by the predictable nature of real-life in data streams, we study online regression when the learner has access to predictions about future examples. In the extreme case,…
Towards Sampling Data Structures for Tensor Products in Turnstile Streams
Zhao Song, Shenghao Xie, Samson Zhou
This paper studies the computational challenges of large-scale attention-based models in artificial intelligence by utilizing importance sampling methods in the streaming setting.…
Perfect Sampling in Turnstile Streams Beyond Small Moments
David P. Woodruff, Shenghao Xie, Samson Zhou
Given a vector induced by a turnstile stream , a non-negative function , a perfect -sampler outputs an index with proba…