Reproduce “Almost Optimal Relative Error Streaming Quantiles with Full Mergeability” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Tomáš Domes, Pavel Veselý
The authors present a fully mergeable sketch for fixed-query relative-rank estimation. It combines item-linked adaptive compaction with a space-allocation strategy, improving the streaming space bound while supporting arbitrary merges. In tests on streams up to 10^9 items, they report similar error in streaming and about half the error for merge-built sketches at comparable item counts; this observation is not a guarantee.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.