Ph.D. alumnus Chengyang Zhang and UNT College of Engineering Senior Associate Dean Yan Huang have made quite an impact. The two researchers recently received the 2019 10-Year Impact Award from ACM SIGSPAITAL, a special interest group within the Association for Computing Machinery (ACM) that focuses on advancing spatial computing.

Published in 2009, the paper – “Map-Matching for Low-Sampling-Rate GPS Trajectories” – was a collaborative project with Microsoft Research Asia and Fudan University.

“When a GPS records positions, we want to map them to a road network,” said Huang. “This mapping allows us to understand trips, create digital road maps, and perform traffic flow analysis. The accuracy of this mapping process is important. Otherwise, cars can be off road and driving directions can be wrong.”

However, GPS is often not accurate. In an urban canyon environment like the downtown of a major city, GPS signals are often blocked by high buildings and there are not enough available satellite signals to estimate the positioning information. Furthermore, to save energy, large amount of GPS data has low-sampling rate, i.e. sampled 2-5 minutes.

This paper developed a novel method to achieve higher accuracy for map matching from low-sampling rate trajectories. The idea is to incorporate common sense into the calculation and find the best matching for all points collectively.

“We know road networks follow spatial geometric and topological structures and paths tend to be direct, rather than roundabout. We also know that true paths tend to follow the speed constraints of the road. By adding those into the algorithm design, we can significantly improve the mapping accuracy,” said Huang.

Zhang graduated 2011 from the Department of Computer Science and Engineering and now works at Amazon.