Efficiently answering regular path queries on very large graphs, by guiding the search through distances in an embedding of the graph. This embedding is precomputed in quasi-linear time and space, independently of the regular query.