Abstract Anomaly-based methods of intrusion detection are gaining increasing interest among IT-security practitioners. Unlike the traditional intrusion detection systems (IDS) based on pattern matching they are capable of detecting previously unknown attacks without any knowledge about attack signatures. For practical deployment, not only accuracy but also the computational performance is crucial. A deployed IDS must be able to process traffic volumes of several Gbps, which is typical for network infrastructure nodes. Most of the previously proposed anomaly-based IDS have not specifically addressed performance issues. Moreover, it has been widely believed that no anomaly-based system with full analysis of packet payload can reach a “sound barrier” of 1 Gbps. In this contribution, we show that using a careful selection of algorithms and common parallelization techniques, the performance of well over 1 Gbps is possible for a wide range of methods based on a metric embedding of packet/connection payloads. After a brief introduction to the embedding techniques, we describe the specific algorithms and data structures for a high-performance implementation of such methods. We present experiments on large-scale traces of real network traffic that demonstrate that processing rates of over 4 Gbps can be attained by our methods on commodity multi-core processors.