Road traffic prediction for the efficient traffic control has lately been in the focus of the research community, as it can solve significant urban issues, such as city evacuation plans, increased concentration of CO2 emissions and delays caused by extended traffic jams. The current paper proposes a novel approach for multi-variate data mining from past traffic data (i.e. average speed values per road), so as to dynamically detect all significant correlations between the road network components (i.e. the segments of the roads) by mapping the latter onto a low dimensional embedding. Multiple traffic-related features (e.g. speed correlation, spatial proximity, phase difference, etc.) are utilized in a multi-objective optimization framework, producing all Pareto-optimal embeddings, each one corresponding to a different trade-off between the objectives. The operator is provided with the option to interactively select among these Pareto-optimal solutions, so as to explore the most descriptive sets of road influences. The proposed method has been evaluated on real traffic data, while the evaluation of the forecasting performance of the multi-objective approach exhibited accuracy improvement with respect single-objective approaches.