Online Detection of Outstanding Quantiles with QuantileFilter

In quantile estimation within a stream of key-value pairs, recent work has made significant progress in query flexibility, supporting quantile estimation for any key using a unified statistical structure. However, despite this flexibility, their query speed falls behind, unable to match the high speed of online data insertion. This “offline query + online insertion” model is not ideal for online quantile estimation. Our goal is to online detect keys whose quantiles exceed a user-queried threshold in real-time, such as identifying the user whose 95 % latency exceeds 200ms in network data. These keys, termed “Quantile-Outstanding Keys,” are vital for anomaly detection in streaming data. In this paper, we propose QuantileFilter, the first approximate algorithm specifically designed for detecting quantile-outstanding keys. QuantileFilter overcomes existing limitations by 1) enabling fast online computation, capable of handling streaming data in real-time with a constant processing time for each data item, accelerating the state-of-the-art (SOTA) by 10 100 times, and 2) maintaining high space efficiency, saving 50 500 times storage space compared to the SOTA while maintaining the same accuracy. All associated code is available on GitHub.