In Search of Points of Interest: A Story of Decoupled Heuristics on Road Networks

Map-based services like Google Maps have become a part of daily life. The key to many of these services is in finding points-of-interest through the road network. For example, a ride-hailing app like Uber must find the nearest drivers to your location by their ETA. As a result, accurately and efficiently finding such points-of-interest in road networks has become an important area of scientific endeavour. This thesis tells a story of a long-neglected strategy known as “Decouple Heuristics”, which we revive to develop new techniques that significantly improve the performance of road network point-of-interest search.