A Distance Oracle is a succinct data structure that provides fast answers to distance queries between any two points. Distance oracles are measured by several parameters: construction time (the running time of the algorithm to produce the data structure), size (the worst case size of the data structure), query complexity (the running time of the query algorithm, given two points), and stretch guarantee (the maximum ratio between the estimated distance returned by the distance oracle and the actual distance).

In this talk we will consider a more refined local stretch guarantee first suggested by Abraham, Bartal and Neiman [STOC 07]. Informally, we wish to obtain better stretch guarantees for nearby pairs. We would like the stretch bound to gradually improve as we query closer pairs of points.

We consider two notions of local stretch for distance oracles:

1. Strong local stretch provides stretch guarantees for any pair of nodes with better stretch guarantees for nearby pairs.
2. Weak local stretch provides stretch guarantees only between pair of nodes u and v, such that v is in the r-neighborhood of u (v is one of the r’th closest nodes to u), for some parameter r.

We will discuss these two notions and see efficient constructions for both these notions improving upon previous work.

Based on a joint work with Ittai Abraham.