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

• Second the pointer to the Deza and Deza book. It's a very nice reference. Jun 24 '13 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? Jun 25 '13 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). Jun 25 '13 at 13:14
• @LeonidBoytsov you might also be aware of the Jensen-Shannon type approaches to symmetrizing the Bregman divergences. Jun 25 '13 at 17:41
• Yes, symmetrization is an option. Jun 28 '13 at 2:26