Large Structures Seminar: Konstantin Tretjakov

The problem of estimating shortest paths between nodes in large graphs is fairly common. It pops up in situations ranging from the familiar GPS-based routing, to social search and data mining. Although there are multiple classical shortest path algorithms, most of them are at least linear in complexity and are thus prohibitively slow when the number of nodes or edges reaches into billions, yet the queries have to be answered in interactive manner. Landmark-based methods offer a simple yet efficient approximate way of answering shortest path queries in this situation and although the core algorithm is fairly trivial, there have been several less trivial improvements suggested for it in the recent years. The talk provides a brief overview of such techniques.