# Non-metric distances

Could anybody suggest practically important distances that are significantly non-metric and are not Bregman divergences? For instance, they are non-symmetric and not equivalent to the Euclidean distance.

Thanks!

• I'm guessing then you're also not interested in f-divergences or the alpha-divergences ? Also, I don't know if you're implying that Bregman divergences are equivalent to Euclidean distances, because they're not. – Suresh Venkat Jun 21 '13 at 20:36
• Maybe I'm missing something, but aren't distances on any real road network non-symmetric? (due to one-way-roads and so on) – Shir Jun 22 '13 at 17:12
• Hi Suresh, Bregman divergences are not equivalent, for sure. I only meant that we worked with Bregman divergences, but also wanted to try divergences of different types. Thank you for suggesting f- and -alpha divergences. Is the alpha-divergence the same as Rényi divergence? – Leonid Boytsov Jun 22 '13 at 19:21
• Maybe distance between nodes in directed graphs would interest you. – MCH Jun 23 '13 at 15:03
• What Shir is talking about is probably the same as what MCH suggests: Shortest paths in directed graphs. For undirected graphs, shortest-path-distances yield metrics, but if the edges are directed, the resulting distance may (depending on the graph layout) be asymmetric. It will still obey the oriented triangle inequality, though; i.e., it's a quasimetric: en.wikipedia.org/wiki/Metric_(mathematics)#Quasimetrics – Magnus Lie Hetland Jun 24 '13 at 7:11

For a really thorough listing of various distances, metric or not, that are in use, I recommend Encyclopedia of Distances by Deza and Deza. (It is also available electronically from Springer.) For a really simple example of a family of non-metric distances, you can simply let $p$ be less than 1 for an $L_p$ distance, for example. For a family that is in heavy, actual use, you could look into various forms of weighted edit distance. There's also the cosine measure, Jeffrey divergence, partial Hausdorff distance, dynamic time warping distance, and domain-dependent distances such as the COSIMIR model, all discussed in Skopal's paper on indexing non-metric distances.
• He discusses how to circumvent the asymmetry, as far as I can recall (e.g., by using $d'(x,y) = d(x,y) + d(y,x)$ or the like). – Magnus Lie Hetland Jun 25 '13 at 13:14