Papers for

network monitoring teams

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Fast method improves sampling from data streamed in real time

Fast Perfect $L_2$ Sampling

Abstract: Perfect $L_2$ sampling is a powerful primitive for turnstile data streams, allowing algorithms to extract an index with probability proportional to its squared frequency, with applications to dynamic join size estimation, query optimization, heavy-hitters, sampling from self-joins, and real-time monitoring of evolving datasets. The setting $p=2$ is also the largest $p$ for which $L_p$ sampling can be achieved in polylogarithmic space. However, existing space-optimal perfect samplers rely on explicit polynomial duplication, requiring inefficient polynomial update times per stream arrival. Resolving a open question left by Swartworth, Woodruff, and Zhou [FOCS 2025], we present a perfect $L_2$ sampler that achieves an expected $\text{polylog}(n)$ update time while maintaining an optimal $\tilde{\mathcal{O}}(\log^3 n)$ bits of space.

Wed 28 OctData Structures and Algorithms
The gist
Selecting items from a large list based on how often they appear is useful for many computer tasks, but doing this quickly and perfectly is hard. The authors solved a puzzle about how to pick items with probability proportional to the square of their frequency using very little memory and very fast updates. Their new technique makes these perfect picks in a way that uses only a small amount of space and can update quickly as new data arrives. This breakthrough opens the door for more efficient data analysis in environments where data is changing rapidly.
Open → 2610.38860v1

Dynamic graph learning improved by simple low dimensional predictors

From Complex Histories to Simple Predictors: Predictive Dimension in Dynamic Graph Learning

Abstract: Existing continuous-time graph learning methods rely heavily on complex neural architectures to encode ever-expanding interaction histories. However, the future conditional distribution induced by complex histories can often be characterized by a low-dimensional predictive state manifold, implying that only a few predictive degrees of freedom are essential for future interactions. We therefore argue that continuous-time graph learning should identify low-dimensional states sufficient for future prediction rather than reconstruct the full history. To make this perspective measurable, we define and independently estimate the intrinsic predictive dimension, which quantifies the effective predictive degrees of freedom required by a given task. Specifically, we remove the history-independent marginal from the history-conditioned future distribution, decompose the resulting predictive residual operator, and estimate the minimum effective rank needed to preserve the predictive power of the full history. Experiments across datasets show that model performance saturation is largely determined by the intrinsic predictive dimension. Based on this finding, we propose PreDyG, a lightweight model whose capacity is matched to the intrinsic predictive dimension. PreDyG achieves superior predictive performance with only 0.07\% of the parameters of a representative complex baseline.

Tue 20 OctMachine LearningArtificial Intelligence
The gist
Predicting future connections or interactions in continuously changing networks can be complicated because it usually requires looking at long histories. The authors find that only a few key aspects of the history really matter for making accurate predictions. They define a way to measure how many of these key predictive factors are needed, called the intrinsic predictive dimension. Using this insight, they build a much simpler and smaller model that predicts future interactions as well as much larger ones but with far fewer parameters.
Open → 2610.28090v1

Algorithm detects changes quickly despite unknown post-change models

Robust Quickest Change Detection with Cost-Efficient Experiment Design and Unknown Post-Change Model

Abstract: A quickest change detection problem is studied where the decision-maker has access to multiple experiments, but can choose only one experiment at a time to detect the change. The true post-change distribution under each experiment is unknown, but known to belong to a family of distributions. It is assumed that each of these families of distributions has an element that is least favorable in a well-defined sense. An algorithm is proposed that is designed using the least favorable distributions. It is shown that the algorithm is first-order asymptotically optimal, as the rate of false alarms goes to zero. This algorithm minimizes the worst-case average detection delay over all post-change distributions within the assumed families, subject to a constraint on the average run length to false alarm and constraints on the average fraction of time each experiment is performed before change.

Mon 12 OctInformation Theory
The gist
Detecting sudden changes as quickly as possible is important but hard when the exact change is unknown. This paper looks at a situation where multiple ways to test for change exist, but only one can be used at a time. The authors propose a method that works well even under the worst-case scenario within a range of possible changes. Their approach makes the detection process both efficient and reliable while controlling false alarms.
Open → 2610.16055v1