2023/09/20 by Claire Mathieu, Mathieu, Claire, Michel de Rougemont +1
Computer Science · #Advanced Database Systems and Queries #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2309.11175
openalex publication_date 2023/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study how to verify specific frequency distributions when we observe a stream of N data items taken from a universe of n distinct items. We introduce the relative Fréchet distance to compare two frequency functions in a homogeneous manner. We consider two streaming models: insertions only and sliding windows. We present a Tester for a certain class of functions, which decides if f is close to g or if f is far from g with high probability, when f is given and g is defined by a stream. If f is uniform we show a space Ω(n) lower bound. If f decreases fast enough, we then only use space O(log2 n⋅ loglog n). The analysis relies on the Spacesaving algorithm \citeMAE2005,Z22 and on sampling the stream.