Weihe Li and Paul Patras awarded Best Student Paper Award
ACM Web Conference 2024
Congratulations to ICSA members, Weihi Li and Paul Patras who received the Best Student Paper award at the ACM Web Conference 2024, which took place 13-17th May in Singapore.
The award winning paper was entitled 'Stable-Sketch: A Versatile Sketch for Accurate, Fast, Web-Scale Data Stream Processing':
Abstract:
Data stream processing plays a pivotal role in various web-related applications, including click fraud detection, anomaly identification, and recommendation systems. Accurate and fast detection of items relevant to such tasks within data streams, e.g., heavy hitters, heavy changers, and persistent items, is however non-trivial. This is due to growing streaming speeds, limited fast memory (L1 cache) available in current systems, and highly skewed item distributions encountered in practice. In effect, items of interest that are tracked only based on their features (e.g., item frequency or persistence value) are susceptible to replacement by non-relevant ones, leading to modest detection accuracy, as we reveal. In this work, we introduce the notion of bucket stability, which quantifies the degree of recorded item variation, and show that this is a powerful metric for identifying distinct item types. We propose Stable-Sketch, an elegant and versatile sketch that exploits multidimensional information, including item statistics and bucket stability, and adopts a stochastic approach to drive replacement decisions. We present a theoretical analysis of the error bounds of Stable-Sketch, and conduct extensive experiments to demonstrate that our solution achieves substantially higher accuracy and faster processing speeds than state-of-the-art sketches in a range of item detection tasks, even with tight memories. We further enhance Stable-Sketch's update throughput with Single Instruction Multiple Data (SIMD) instructions and implement our solution with P4, demonstrating real world deployment viability.
Our work proposes a new data structure (sketch) design that builds on the new concept of 'bucket stability' that we introduce to improve the tracking of 'hot' items in data streams, when the data rates are very high, and the available fast memory is limited. This is important for a range of web-centric applications such as web personalization, intrusion detection, and web traffic analysis.
The ACM Web Conference (formerly WWW) is the premier venue to present and discuss progress in research, development, standards, and applications of topics related to the Web.
The Conference offers high quality programs including research sessions, posters and demonstrations, a PhD symposium for junior scholars, workshops, tutorials, as well as thought provoking keynote speakers and panels.
The Web Conference 2024 was an in-person event, held at the Resorts World Convention Centre, Singapore.