Abstract Motivated by scenarios in network anomaly detection, we consider the problem of detecting persistent items in a data stream, which are items that occur `regularly' in the stream. In contrast with heavy hitters, persistent items do not necessarily contribute significantly to the volume of a stream, and may escape detection by traditional volume-based anomaly detectors. We first show that any online algorithm that tracks persistent items exactly must necessarily use a large workspace, an.
展开▼