We present fast algorithms for constructing probabilistic embeddings and
approximate distance oracles in sparse graphs. The main ingredient is a fast
algorithm for sampling the probabilistic partitions of Calinescu, Karloff, and
Rabani in sparse graphs.