A system and method for predicting travel time of a vehicle on one or more routes within arterial roads. It collects historical information from probe vehicles positions using GPS technology in a periodic fashion and the sequence of links traversed between successive position measurements. Further, it collects information of neighborhood structure for each link within the arterial roads network. A NoisyOR conditional probability distribution function is proposed to capture the spatio-temporal dependencies between each link of the arterial network and its neighbors. It learns the parameters of this data driven probabilistic model from collected historical information of probe vehicle trajectories traversed within the arterial roads network using a proposed expectation maximization method. Finally it predicts travel time of vehicles on routes within the arterial roads using the learnt parameters and real time information of trajectories of vehicle that have been recorded from the arterial roads network using GPS technology sensing.