Computer Science Professor Patents New Method to Get You There Quickly
Craig Gotsman, distinguished professor of computer science and former dean of the Ying Wu College of Computing, is offering a new way to help you on your next journey to destinations unknown – and it’s recently been patented.
Together with long-time collaborator Renjie Chen from the Max-Planck Institute for Informatics in Germany, one of the top research labs for computer science in Europe, Gotsman has developed a new algorithmic method to significantly speed up the computation of navigation paths between points on digital road maps. These so-called “fastest path on a weighted directed graph” (in math terms) queries are notoriously difficult to answer efficiently on very large maps and have been the topic of intense research for decades.
According to Gotsman, these types of navigational queries are run billions of times a day on driving navigation servers such as Google Maps and Waze, among others, to recommend driving routes to hundreds of millions of users. Due to the overwhelming popularity of this type of operation, any reduction in computing time required to answer such a query can be critical, translating directly to a vast savings in the number of compute servers required and the energy it takes to power them.
At the core of the new method is a novel way to efficiently compute a “heuristic” lower bound estimate of the true travel time based on a hierarchical decomposition of the map. This, in turn, informs a very efficient search for the fastest path among the many possible options present in the map.
“There are billions of data points on maps,” he said. “Efficiency in handling millions of queries simultaneously is key – in saving time and money. We have experimentally shown a speedup by a factor of about ten compared to other methods”.
Gotsman and Chen, who is Gotsman’s former post-doctoral fellow, began their research over a period of four years, with the patent process taking several more.
“We had to contend with the fact that USPTO does not patent pure algorithms, only “methods” that are part of a concrete application and questions about prior art. Patenting is never a quick and easy process, but computer science seems to be one area where devising solutions through detailed research is only half the work!” he added with a laugh.
To date, Gotsman has been awarded a total of 13 patents. Prior to this one, he patented a method to hide private location data in COVID tracing apps.
He was also recently elected a Fellow of the Academy of Science, Engineering and Medicine of Florida, where he maintains dual residency. This fellowship is reserved for individuals who have achieved the highest recognition and impact in their field, within sciences, engineering, and/or medicine.