# 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. Commented Jun 21, 2013 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
Commented Jun 22, 2013 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? Commented Jun 22, 2013 at 19:21
• Maybe distance between nodes in directed graphs would interest you. Commented Jun 23, 2013 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 Commented Jun 24, 2013 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.

• Second the pointer to the Deza and Deza book. It's a very nice reference. Commented Jun 24, 2013 at 23:46
• Cool, excellent paper, I have also found a more recent survey by Bustos & Skopal (On nonmetric similarity search problems in complex domains). Do I get it correctly that TriGen is designed for symmetric distances, or, is there a non-symmetric extension? Commented Jun 25, 2013 at 3:23
• 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). Commented Jun 25, 2013 at 13:14
• @LeonidBoytsov you might also be aware of the Jensen-Shannon type approaches to symmetrizing the Bregman divergences. Commented Jun 25, 2013 at 17:41
• Yes, symmetrization is an option. Commented Jun 28, 2013 at 2:26