Let G = (V, E) be an undirected graph on n vertices, and let Δ(u, v) denote the distance in G between two vertices u and v. Thorup and Zwick showed that for any positive integer t, the graph G can be preprocessed to build a data structure that can efficiently report t-approximate distance between any pair of vertices. That is, for any u, v V, the distance reported is at least Δ(u, v) and at most tΔ(u, v). The remarkable feature of this data structure is that, for t3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t-approximate distance query in constant time. They named the data structure approximate distance oracle because of this feature. Furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal.In this article, we show that we can actually construct approximate distance oracles in expected O(n2) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph G = (V, E) is a subgraph (V, ), E, such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2Δ(u, v) + 1. © 2006 ACM.