There is a famous paper by Childs, et al, in which it is shown that a quantum algorithm can find the name of the exit node for a certain graph in a way that is exponentially faster than any classical algorithm. This speedup assumes an oracle that tells you which nodes are connected to a given node, as well as a labelling of the nodes that prevents the exit name being deduced without navigating the graph.
In the paper, a random labelling of the nodes is used. However, this will presumably prevent the efficient implementation of an oracle.
Is there any cases for which an efficient oracle is known, that allows for the exponential speedup?