The Philips automatic train timetable information system AIS provides accurate information about train connections between more than 1100 German cities over the telephone [2]. Its speaker-independent speech recognizer is monophone-based and uses continuous-mixture densities. Most of the CPU time is spent on log-likelihood computation. For realtime operation, the number of densities had to be limited, sacrificing accuracy. To overcome this restriction, we developed a fast hierarchical within-mixture nearest neighbor search with logarithmic computational effort. The method degrades recognition accuracy by roughly 2-7% rel., but on the other hand allows for a larger number of densities to be processed. With the new method, the AIS log-likelihood computation was accelerated by a factor of nine retaining optimal accuracy.