Abstract
Identifying anomalies in massive, high-dimensional data streams is a critical challenge in modern networking and data analytics. This paper presents Confidence Bounds based Random Walk (CBRW), an active inference strategy designed to navigate hierarchical data structures to locate targets with minimal sample complexity. Unlike traditional methods, CBRW operates effectively even when underlying data distributions are unknown or exhibit heavy-tailed behavior. We prove that CBRW achieves order-optimal sample complexity, scaling logarithmically with the search space size and the reliability requirement.
Introduction
In the era of big data, finding "needles in haystacks"—such as heavy-hitter IP flows or defective medical samples—requires efficient search strategies. These problems often involve millions of data streams ($N$), stochastic noise, and unknown probability distributions. Crucially, many of these domains possess an inherent hierarchical structure (e.g., IP prefixes or organizational groupings) that can be exploited to accelerate the search.
Existing solutions often fail to leverage this hierarchy or rely on restrictive assumptions about data distributions (e.g., sub-Gaussianity). This paper addresses the problem of finding all targets with a guaranteed reliability level ($\epsilon$) using the minimum number of samples, even in the presence of heavy-tailed noise.
Methodology: Confidence Bounds based Random Walk (CBRW)
The proposed CBRW algorithm treats the search space as a tree and performs a biased random walk starting from the root.
Local Sequential Tests
At each node $(l, i)$, the algorithm executes a local test to decide the next move:
- Descend: Move to a child node if evidence suggests a target lies below.
- Ascend: Move back to a parent node if the current branch appears non-anomalous.
- Terminate: Declare the current node a target if statistical confidence is sufficiently high.
Robust Statistics
To handle "messy" data, CBRW employs Upper and Lower Confidence Bounds (UCB/LCB). For standard data, it uses Chernoff-Hoeffding bounds. For heavy-tailed data, it utilizes a truncated sample mean statistic, ensuring the "walker" is mathematically biased toward true targets.
Theoretical Insights
A key contribution of this work is the proof of additive complexity. The cost of searching a larger space ($N$) and the cost of achieving higher reliability ($\epsilon$) are additive ($O(\log N + \log 1/\epsilon)$), rather than multiplicative. This property ensures that increasing the search space size does not exponentially increase the cost of maintaining high reliability.
Furthermore, by exploiting the tree structure, the algorithm examines only a diminishing fraction of the total search space, following the "scent" of anomalies down the hierarchy rather than performing an exhaustive search.
Key Results
CBRW is proven to be order-optimal in terms of both search space size ($N$) and reliability ($\epsilon$). The expected sample complexity is $O(\log N + \log \frac{1}{\epsilon})$. For a dataset with a billion streams, search time grows only linearly with the tree depth, making it highly efficient for massive-scale applications such as Hierarchical Heavy Hitter (HHH) detection and noisy group testing.
Conclusion and Future Work
While CBRW provides a robust framework for hierarchical anomaly detection, it assumes a minimum "gap" ($\delta$) between normal and anomalous means. Future research could investigate scenarios with vanishing gaps or unknown, dynamic hierarchies. Additionally, while the framework extends to multiple targets, further optimization for highly noisy trees with numerous simultaneous anomalies remains an open challenge.
Summary updated