STREAMING ANOMALY DETECTION

Abstract

Anomaly detection is critical for finding suspicious behavior in innumerable systems, such as intrusion detection, fake ratings, and financial fraud. We need to detect anomalies in real-time or near real-time, i.e. determine if an incoming entity is anomalous or not, as soon as we receive it, to minimize the effects of malicious activities and start recovery as soon as possible. Therefore, online algorithms that can detect anomalies in a streaming manner are essential. Also, since the data increases as the stream is processed, we can only afford constant memory which makes the problem of streaming anomaly detection more challenging.

We first propose Midas which detects anomalous edges in dynamic graphs. We then extend the count-min sketch data structure to a Higher-Order Sketch to capture complex relations in graph data, and to reduce detecting suspicious dense subgraph problem to finding a dense submatrix in constant time.

Next, we broaden the graph setting to multi-aspect data. We propose MStream which detects anomalies in multi-aspect data streams including both categorical and numeric attributes. Finally, we propose MemStream, a streaming anomaly detection framework, allowing us to detect unusual events in multi-dimensional data streams while being resilient to concept drift.