Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees.
Nicholas SchieferJustin Y. ChenPiotr IndykShyam NarayananSandeep SilwalTal WagnerPublished in: ACDA (2023)
Keyphrases
- worst case
- error bounds
- approximation algorithms
- central limit theorem
- gaussian convolution
- theoretical guarantees
- average case
- worst case analysis
- approximation guarantees
- greedy algorithm
- upper bound
- approximation ratio
- data streams
- np hard
- quality guarantees
- lower bound
- worst case bounds
- real time
- constant factor
- data sets
- theoretical analysis
- unsupervised manner
- running times
- linear interpolation
- relative error
- streaming data
- space complexity
- closed form
- real time streaming
- sparse sampling
- objective function
- learning algorithm
- neural network