Links' Seminars and Public Events |
Fri, February 15, 2019 11:00 am 12:00 pm | Seminar [Florent] |
Wed, February 13, 2019 1:30 pm 2:30 pm | 30mn de science : Florent Capelli on Knowledge Compilation Inria salle Plénière (Bâtiment A) |
Fri, February 1, 2019 11:00 am 12:30 pm | Bruno Guillon in Links' seminar Title: Finding paths in large graphs Abstract: 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 this 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 from 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. B21 Room |