Increasingly, location-aware sensors in urban transportation networks are generating a wide variety of data which has spatio-temporal network semantics. Examples include temporally detailed roadmaps, GPS tracks, traffic signal timings, and vehicle measurements. These datasets, which we collectively call Big Spatio-Temporal Network (BSTN) Data, have value addition potential for several smart-city use-cases including navigation services which recommend eco-friendly routes. However, BSTN data pose significant computational challenges regarding the assumptions of the current state-of-the-art analytic-techniques used in these services. This article attempts to put forth some potential research directions towards addressing the challenges of scalable analytics on BSTN data. Two kinds of BSTN data are considered here, viz., the vehicle measurement big data and the travel-time big data.