3 papers
cs.DS2023
Learned Interpolation for Better Streaming Quantile Approximation with Worst-Case Guarantees
Nicholas Schiefer, Justin Y. Chen, Piotr Indyk +3
An -approximate quantile sketch over a stream of inputs approximates the rank of any query point - that is, the number of input points less than - up to an…
cs.DS2022
Streaming Algorithms for Support-Aware Histograms
Justin Y. Chen, Piotr Indyk, Tal Wagner
Histograms, i.e., piece-wise constant approximations, are a popular tool used to represent data distributions. Traditionally, the difference between the histogram and the underlyin…
cs.CG2016
Near-Optimal (Euclidean) Metric Compression
Piotr Indyk, Tal Wagner
The metric sketching problem is defined as follows. Given a metric on points, and , we wish to produce a small size data structure (sketch) that, given any pair of point i…