Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators.

David P. Woodruff Samson Zhou

Published in: FOCS (2022)

Keyphrases

sliding window
tight bounds
data streams
upper bound
streaming data
continuous queries
limited memory
fixed size
space efficient
window size
exponential decay
variable size
stream data
walsh hadamard transform
window sizes
data structure
sql queries
concept drift
query optimization
lower bound
data sets
database