Public transport buses have uncertainties associated with its arrival/travel times, due to several factors such as signals, dwell times at bus stops, seasonal variations, fluctuating travel demands, and so on. In the developing world, these uncertainties are further magnified by the presence of excess vehicles, diverse modes of transport, and acute lack of lane discipline. Hence, the problem of bus arrival time prediction continues to be a challenging one especially in developing countries. This paper proposes a new methodology for bus arrival time prediction in real time. Unlike existing approaches, the proposed method explicitly learns the spatial (and temporal) correlations/patterns of traffic in a novel fashion. Specifically, it first detects the unknown order of spatial dependence and then learns linear, non-stationary spatial correlations for this detected order. It learns temporal correlations between successive trips as a function of their time difference. To make the optimal prediction feasible, the learnt predictive model is rewritten in a suitable linear state-space form, and then, an appropriate Kalman filter (KF) is applied. The performance was evaluated with real field data and compared with existing methods. IEEE