Intrusion detection is one of core technologies of computer security. The goal of intrusion detection goal is identication of malicious activity in a stream of monitored data which can be network trac, operating system events or log entries. A majority of current intrusion detection systems (IDS) follows a signature-based approach in which, similar to virus scanners, events are detected that match specic pre-dened patterns known as \signatures". The main limitation of signature-based IDS is their failure to identify novel attacks, and sometimes even minor variations of known patterns. Besides, a signicant administrative overhead is incurred by the need to maintain signature databases. Machine learning oers a major opportunity to improve quality and to facilitate administration of IDS. Supervised learning can be used for automatic generation of detectors without a need to manually dene and update signatures. Anomaly detection and other unsupervised learning techniques can detect new kinds of attacks provided they exhibit unusual character in some feature space. In our contribution, kernel and distance based learning algorithms for network intrusion detection will be presented. The two essential parts of our approach are online learning algorithms and feature extraction. The major requirements on the algorithmic part are linear run-time, online learning and data type abstraction. Simple but eective anomaly detection algorithms will be presented that satisfy these requirements (1). Feature extraction algorithms can be reduced to computation of similarity measures between sequential objects. In order to access the feature from the application-layer network protocols, in which most of modern remote exploits operate, similarity measures are computed directly over byte streams of TCP connections. Algorithms and data structures will be presented that allow e- cient computation of similarity measures in linear time with very low run-time constants and memory consumption (2)