Precise short-term prediction of traffic parameters such as flow and travel-time is a necessary component for many ITS applications. This work describes the research on a novel, fast, and robust algorithm which is based on a partitioning cluster analysis. It is able to calculate travel times from Floating Car Data (FCD) for a whole city, even for minor roads. A potential problem with FCD is the insufficient penetration rate of smaller taxi fleets and the resulting noisy and/or missing data (4). The new approach accounts for this by smoothing the data by a local fit method based on polynomials with the help of a Singular Value Decomposition (SVD). Numerical experiments confirm the high efficiency of the algorithm and a promising quality of the prediction.