Many continuously recorded data streams are generated by non-stationary processes, which may change over time, in some cases even drastically. Some adaptive learning agents deal with time-changing data streams by generating a new model from every incoming window of training examples. Though this solution should ensure an accurate and relevant model at all times, it may waste significant computational resources on continuous re-generation of nearly identical models during periods of stability. In this paper, we evaluate a series of efficient incremental algorithms that are nearly as accurate as existing online methods, sometimes even outperforming them, while being considerably cheaper in terms of the processing time. The proposed incremental techniques are based on the Information Network classification algorithm. The incremental methods efficiency is demonstrated on realworld streams of road traffic and intrusion detection data.