Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.22070 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914172497821696 |
|---|---|
| author | Guo, Jiarui Lyu, Qiushi Wu, Yuhan Li, Haoyu Yao, Zhaoqian Dong, Yuqi Wang, Xiaolin Cui, Bin Yang, Tong |
| author_facet | Guo, Jiarui Lyu, Qiushi Wu, Yuhan Li, Haoyu Yao, Zhaoqian Dong, Yuqi Wang, Xiaolin Cui, Bin Yang, Tong |
| contents | In this paper, we take into consideration quantile estimation in data stream models, where every item in the data stream is a key-value pair. Researchers sometimes aim to estimate per-key quantiles (i.e. quantile estimation for every distinct key), and some popular use cases, such as tail latency measurement, recline on a predefined single quantile (e.g. 0.95- or 0.99- quantile) rather than demanding arbitrary quantile estimation. However, existing algorithms are not specially designed for per-key estimation centered at one point. They cannot achieve high accuracy in our problem setting, and their throughput are not satisfactory to handle high-speed items in data streams. To solve this problem, we propose MagnifierSketch for point-quantile estimation. MagnifierSketch supports both single-key and per-key quantile estimation, and its key techniques are named Value Focus, Distribution Calibration and Double Filtration. We provide strict mathematical derivations to prove the unbiasedness of MagnifierSketch and show its space and time complexity. Our experimental results show that the Average Error (AE) of MagnifierSketch is significantly lower than the state-of-the-art in both single-key and per-key situations. We also implement MagnifierSketch on RocksDB database to reduce quantile query latency in real databases. All related codes of MagnifierSketch are open-sourced and available at GitHub. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22070 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | MagnifierSketch: Quantile Estimation Centered at One Point Guo, Jiarui Lyu, Qiushi Wu, Yuhan Li, Haoyu Yao, Zhaoqian Dong, Yuqi Wang, Xiaolin Cui, Bin Yang, Tong Data Structures and Algorithms In this paper, we take into consideration quantile estimation in data stream models, where every item in the data stream is a key-value pair. Researchers sometimes aim to estimate per-key quantiles (i.e. quantile estimation for every distinct key), and some popular use cases, such as tail latency measurement, recline on a predefined single quantile (e.g. 0.95- or 0.99- quantile) rather than demanding arbitrary quantile estimation. However, existing algorithms are not specially designed for per-key estimation centered at one point. They cannot achieve high accuracy in our problem setting, and their throughput are not satisfactory to handle high-speed items in data streams. To solve this problem, we propose MagnifierSketch for point-quantile estimation. MagnifierSketch supports both single-key and per-key quantile estimation, and its key techniques are named Value Focus, Distribution Calibration and Double Filtration. We provide strict mathematical derivations to prove the unbiasedness of MagnifierSketch and show its space and time complexity. Our experimental results show that the Average Error (AE) of MagnifierSketch is significantly lower than the state-of-the-art in both single-key and per-key situations. We also implement MagnifierSketch on RocksDB database to reduce quantile query latency in real databases. All related codes of MagnifierSketch are open-sourced and available at GitHub. |
| title | MagnifierSketch: Quantile Estimation Centered at One Point |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.22070 |