Bruno Guillon, Inria Lille
3 May 2019, 10:30-11:30
ENS, S16
Finding paths in large data graphs
When dealing with large graphs, classical algorithms for finding paths such as Dijkstra’s Algorithm are unsuitable, because they require to perform too many disk accesses. To avoid the cost of these expensive accesses, while keeping a data structure of size quasi-linear in the size of the graph, we propose to guide the path search with a distance oracle, obtained from a topological embedding of the graph.
I will present fresh experimental research on this topic, in which we obtain graph embeddings using learning algorithms from natural language processing. On some graphs, such as the graph of publications of DBLP, our topologically-guided path search allows us to visit a small portion of the graph only, in average.
This is joint work with Charles Paperman.
