Distance Query in Road Network
Project 2022-23
Project Title: Distance Query in Road Networks.
Lab/Research Group: Theory Group
The theory group consists of eight faculty members (plus four adjuncts) who use mathematical techniques to study problems throughout computer science. We work on network algorithms, coding theory, combinatorial optimization, computational geometry, data streams, dynamic algorithms and complexity, model checking and static analysis, database theory, descriptive complexity, parallel algorithms and architectures, and computational complexity theory. Members of the theory group wear other hats as well and collaborate throughout the department and the world beyond. For more details of the myriad work going on, please visit our web-pages.
You can find more about the group and the weekly seminars at https://groups.cs.umass.edu/theory/
Project Description
Finding the shortest distance between two given locations in a road network is a fundamental problem that finds numerous practical applications. While the famous Dijkstra's algorithm can handle a single distance query in a fraction of a second for very large networks, it becomes infeasible when there are thousands to millions of distance queries per second. Handling a large number of distance queries is a central problem in applications such as Google Maps.
In this project, you will study distance oracles, which are compact data structures that can answer distance queries quickly. You will learn the basics of planar graphs, a theoretical model of road networks. Then you will learn how to construct distance oracles for planar graphs. Finally, you will implement a distance oracle and test it on large road networks.
Learning Objectives:
Learn the basics of planar graphs, how to design planar graph algorithms, how to tune code for fast runtime, and how to turn a theoretically guaranteed algorithm into real code.
Prerequisites
Knowing how to program is the only prerequisite.