<p>For a really thorough listing of various distances, metric or not, that are in use, I recommend <a href="http://rads.stackoverflow.com/amzn/click/3642309577">Encyclopedia of Distances</a> 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 <a href="https://en.wikipedia.org/wiki/Lp_space">$L_p$ distance</a>, for example. For a family that is in heavy, actual use, you could look into various forms of <a href="http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance">weighted edit distance</a>. 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 <a href="http://siret.ms.mff.cuni.cz/skopal/pub/TODSpreprint.pdf">Skopal's paper on indexing non-metric distances</a>.</p>

CC BY-SA 3.0
2013-06-24T23:46:09.957Z
Second the pointer to the Deza and Deza book. It's a very nice reference.
Suresh Venkat
CC BY-SA 3.0
2013-06-25T03:23:33.203Z
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?
Leonid Boytsov
CC BY-SA 3.0
2013-06-25T13:14:52.773Z
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
CC BY-SA 3.0
2013-06-25T17:41:04.860Z
@LeonidBoytsov you might also be aware of the Jensen-Shannon type approaches to symmetrizing the Bregman divergences.
Suresh Venkat
CC BY-SA 3.0
2013-06-28T02:26:32.057Z
Yes, symmetrization is an option.
Leonid Boytsov
CC BY-SA 3.0
2013-06-24T07:08:31.463Z
2013-06-24T07:08:31.463Z
Magnus Lie Hetland
<p>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.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-06-21T20:36:19.257Z
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
CC BY-SA 3.0
2013-06-22T17:12:32.093Z
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
CC BY-SA 3.0
2013-06-22T19:21:54.030Z
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
CC BY-SA 3.0
2013-06-22T19:22:25.237Z
Shir, could you provide a reference? Thanks!
Leonid Boytsov
CC BY-SA 3.0
2013-06-23T15:03:16.173Z
Maybe distance between nodes in directed graphs would interest you.
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-24T07:11:12.957Z
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: https://en.wikipedia.org/wiki/Metric_(mathematics)#Quasimetrics
Magnus Lie Hetland
CC BY-SA 3.0
2013-06-24T14:52:50.830Z
I think the Renyi divergences are a special class of $\alpha$-divergences.
Suresh Venkat
CC BY-SA 3.0
2013-06-25T07:51:04.087Z
Thank you for the information. The most interesting functions that non-symmetric and "non-triangular". Yet, distances in graphs can be interesting too.
Leonid Boytsov
<metric-spaces>
Non-metric distances
Leonid Boytsov
# Non-metric distances

(Asked by: username_0 on 2013-06-21)

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!

**Tags:** metric-spaces

> **Comments:**
> **username_1**: 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.  
> **username_2**: Maybe I'm missing something, but aren't distances on any real road network non-symmetric? (due to one-way-roads and so on)  
> **username_0**: 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?  
> **username_0**: username_2, could you provide a reference? Thanks!  
> **username_3**: Maybe distance between nodes in directed graphs would interest you.  
> **username_4**: What username_2 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: https://en.wikipedia.org/wiki/Metric_(mathematics)#Quasimetrics  
> **username_1**: I think the Renyi divergences are a special class of $\alpha$-divergences.  
> **username_0**: Thank you for the information. The most interesting functions that non-symmetric and "non-triangular". Yet, distances in graphs can be interesting too.  

---

## 1 answers

### Answer by username_4 on 2013-06-24. Score: 6

For a really thorough listing of various distances, metric or not, that are in use, I recommend [Encyclopedia of Distances](http://rads.stackoverflow.com/amzn/click/3642309577) 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](https://en.wikipedia.org/wiki/Lp_space), for example. For a family that is in heavy, actual use, you could look into various forms of [weighted edit distance](http://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_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](http://siret.ms.mff.cuni.cz/skopal/pub/TODSpreprint.pdf).

> **Comments:**
> **username_1**: Second the pointer to the Deza and Deza book. It's a very nice reference.  
> **username_0**: 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?  
> **username_4**: 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).  
> **username_1**: @LeonidBoytsov you might also be aware of the Jensen-Shannon type approaches to symmetrizing the Bregman divergences.  
> **username_0**: Yes, symmetrization is an option.  

---

