Real-time data mining of high-speed and non-stationary data streams has a large potential in such fields as efficient operation of machinery and vehicles, wireless sensor networks, urban traffic control, stock data analysis etc.. These domains are characterized by a great volume of noisy, uncertain data, and restricted amount of resources (mainly computational time). Anytime algorithmsoffer a tradeoff between solution quality and computation time, which has proveduseful in applying artificial intelligence techniques to time-critical problems. Inthis paper we are presenting a new, enhanced version of an anytime algorithm forconstructing a classification model called Information Network (IN). The algorithmimprovement is aimed at reducing its computational cost while preservingthe same level of model quality. The quality of the induced model is evaluatedby its classification accuracy using the standard 10-fold cross validation. Theimprovement in the algorithm anytime performance is demonstrated on severalbenchmark data streams.