Timezone: »

 
Efficient Location Sampling Algorithms for Road Networks
Sara Ahmadian · Kostas Kollias · Ameya Velingker · Sreenivas Gollapudi · Vivek Kumar · Santhoshini Velusamy

@
in Sampling and Optimization in Discrete Space »
Event URL: https://openreview.net/forum?id=fPcIwNb3qI »
Many geographic information systems applications rely on data provided by user devices in the road network, including traffic monitoring, driving navigation, and road closure detection. The underlying signal is generally collected by sampling locations from user trajectories. The sampling process, though critical for various applications, has not been studied sufficiently in the literature. While the most natural way to sample a trajectory may be to use a frequency based algorithm, e.g., sampling locations every $x$ seconds, such a sampling strategy can be quite wasteful in resources (e.g., server-side processing, user battery) as well as stored user data. In this work, we conduct a horizontal study of various location sampling algorithms (based on frequency, road geography, reservoir sampling, etc.) on the road network of New York City and assess their trade-offs in terms of various metrics of interest, such as the size of the stored data and the induced quality of training for prediction tasks (e.g., predicting speeds).

Author Information

Sara Ahmadian (Google Research)
Kostas Kollias (Google Research)
Ameya Velingker (Google Research)
Sreenivas Gollapudi (Google Research)
Vivek Kumar (Banaras Hindu University, Dhirubhai Ambani Institute Of Information and Communication Technology)
Santhoshini Velusamy (Harvard University)

More from the Same Authors