Online network anomaly-based intrusion detection systems responsible about monitoring the novel anomalies. Network anomaly detection system architecture with a new outlier detection approach is presented in this paper. A new outlierness measurement is proposed which is based on frequent patterns technique and an approach for detecting outliers is introduced. The proposed approach features main advantages which are: effective and direct in detect the anomalous of the online traffic data; adaptive to underlying changes of the traffic streams. The empirical results exhibit a good detection for the new anomalous behavior and the accuracy performance of our proposed approach is approximately close to the static approach. © 2013 IEEE.