אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Stream frequency measurements are fundamental in many data stream applications such as financial data trackers, intrusion detection systems, and network monitoring. Count-Min Sketch and its variants have been widely adopted for this task due to their space efficiency and ability to provide approximate frequency estimates with bounded error guarantees. However, these sketches suffer from a limitation: they have a fixed memory usage determined by the desired accuracy, unable to adapt to changing memory availability or accuracy requirements during runtime. Dynamic solutions exist, but they are likewise still constrained. We introduce the Geometric Sketch, a frequency estimation sketch that addresses the limitations of existing sketches by offering dynamic memory allocation. Unlike existing sketches with fixed memory footprints, the Geometric Sketch can dynamically grow or shrink its memory usage at an arbitrary size, down to a single-counter granularity, making it well-suited to systems with changing memory availability When evaluated using real Internet packet traces, the Geometric Sketch achieves higher accuracy compared to the existing method, DCMS, by employing fine-grained expansion and compression.