This paper studies an unexplored attribute in data streams - item freshness. The freshness of an item refers to the time interval between its last arrival and the present moment. The information of item freshness is useful in various scenarios like cache, online advertising, computer network, etc. Currently, there is no algorithm tailored for estimating item freshness. We propose a theoretically guaranteed sketch algorithm called RingSketch, which integrates time-agnostic sketch algorithm with time-aware CLOCK algorithm for real-time freshness measurement. With the key idea of tracing the trajectory of the clock pointer, the estimation process of RingSketch is akin to observing the length of the growth rings in a tree trunk. We theoretically derive the average error of RingSketch and validate it with extensive experiments. The results show that RingSketch simultaneously achieves high accuracy (<10-3 average relative error) and fast update speed (>11.4 M/s), outperforming the baseline solutions by at least 13.3x and 1.5x respectively. All codes are open-sourced at GitHub.

Frequent object mining has gained considerable interest in the research community and can be split into frequent item mining and frequent set mining depending on the type of object. While existing sketch-based algorithms have made significant progress in addressing these two tasks concurrently, they also possess notable limitations. They either support only software platforms with low throughput or compromise accuracy for faster processing speed and better hardware compatibility. In this paper, we make a substantial stride towards supporting frequent object mining by designing SandwichSketch, which draws inspiration from sandwich making and proposes two techniques including the double fidelity enhancement and hierarchical hot locking to guarantee high fidelity on both two tasks. We implement SandwichSketch on three platforms (CPU, Redis, and FPGA) and show that it enhances accuracy by$38.4\times$and$5\times$for two tasks on three real-world datasets, respectively. Additionally, it supports a distributed measurement scenario with less than a 0.01% decrease in Average Relative Error (ARE) when the number of nodes increases from 1 to 16.

The growing memory demands of embedding tables in Deep Learning Recommendation Models (DLRMs) pose great challenges for model training and deployment. Existing embedding compression solutions cannot simultaneously achieve memory efficiency, low latency, and adaptability to dynamic data distribution. This article presents CAFE+, a Compact, Adaptive, and Fast Embedding compression framework that meets the above requirements. The design philosophy of CAFE+ is to dynamically allocate more memory to important features and less to unimportant ones. We assign unique embedding to important feature and allow multiple unimportant features sharing one embedding. We propose a fast and lightweight feature monitor, to real-time capture feature importance and report important features. We theoretically analyze the accuracy of our feature monitor and prove the superiority of CAFE+ from the aspect of model convergence. Extensive experiments show CAFE+ outperforms existing embedding compression methods, yielding \(3.94\%\) and \(3.94\%\) superior testing AUC on Criteo Kaggle dataset and CriteoTB dataset at a compression ratio of \(10{,}000\times\) . Building on our conference version [ 114 ], this journal version introduces several novel designs (implicit importance attenuation, adaptive threshold adjustment, and ColdSifter) that enable CAFE+ to more effectively adapt to long-term online learning and achieve better model quality. All codes are available at GitHub [ 112 ].

Layer-3 load balancing is a key topic in the networking field. It is well acknowledged that flowlet is the most promising solution because of its good trade-off between load balance and packet reordering. However we find its one significant limitation: it makes the forwarding paths of flows unpredictable. To address this limitation this paper presents BurstBalancer a simple yet efficient load balancing system with a sketch named BalanceSketch. Our design philosophy isdoing less changesto keep the forwarding path of most flows fixed which guides the design of BalanceSketch and our balance operations. We have fully implemented BurstBalancer in a small-scale testbed built with Tofino switches and conducted both large-scale event-level (NS-2) and ESL (electronic system level) simulations. Our results show that BurstBalancer achieves 5%$\sim$35% smaller FCT than LetFlow in symmetric topology and up to 30× smaller FCT in asymmetric topology while 58× fewer flows suffer from path changing. All related codes are open-sourced at GitHub