Quantile estimation is critical for diverse applications, including database management and network traffic monitoring. Probabilistic quantile sketches are widely employed in practice, with the KLL sketch (introduced in 2016) being particularly notable for its theoretically space-optimal properties. However, KLL overlooks the inherent repetition of elements often present in real-world data streams. Such streams are frequently highly skewed, characterized by ''hot items''-items that appear with high frequency. The KLL sketch processes these hot items without accounting for their prevalence, resulting in suboptimal space utilization due to redundant insertions and storage. To overcome this limitation, we propose Cooled-KLL, an enhanced KLL sketch. Cooled-KLL introduces a novel ''Hot Filter'' structure that efficiently identifies and stores hot items as compact key-value pairs. This mechanism ensures that only ''cold'' (less frequent) items are subsequently processed by the core KLL sketch. Our approach significantly reduces memory consumption without compromising processing speed. Extensive experiments demonstrate that Cooled-KLL consistently outperforms five other state-of-the-art algorithms, achieving up to 2.5 orders of magnitude higher accuracy compared to the standard KLL sketch.

IP lookup plays a significant role in networking. The rapid development of the Internet brings new challenges to IP lookup in recent years. To deal with these challenges, we propose the first algorithm that we are aware of to use Minimal Perfect Hash (MPH) filters in IP lookup. It achieves the information theoretic optimum on-chip memory storage and O(1) worst case on-chip lookup speed. To overcome the shortcoming of MPH filter's no support for insertions, we propose an incremental update algorithm which achieves average update speed of O(1) memory access per update.

The size of Forwarding Information Base (FIB) maintained at backbone routers is experiencing an exponential growth, and various solutions have been proposed in the literature. The main shortcoming of FIB compression is the update overhead. Only when the update speed of FIB compression algorithms is sufficiently fast and bounded, the probability of packet loss incurred by FIB compression operations during update can be completely avoided. However, no prior FIB compression algorithm can bound the worst case of update, and hence a mature solution with complete avoidance of packet loss is still yet to be identified. To address this issue, we propose the Unite and Split (US) compression algorithm to enable fast update with bounded worst case performance. Experimental results show that the average update speed of the US algorithm is almost the same as that of the binary trie without any compression.