Suppose I have an n-dimensional dataset and its points are roughly in the shape of an n-dimensional horseshoe or something along those lines. Using euclidian distance might be a bad idea, since points on the tip of the horseshoe would the appear close, although this wouldnt make any sense given the shape of the data.

It should be possible to find something like a (lower dimensional) topology and a meaningful metric on it, that uses the intrinsic topology of the data.

A couple of years ago, I had a longer discussion about that sort of thing, but i can't remember what it was called...

  • 2
    $\begingroup$ I guess you are thinking of "nonlinear dimensionality reduction" aka "manifold learning" techniques. There is a whole bunch of them, so it's hard to say which one you were discussing a couple of years ago. It might have been for example Isomap or maybe Locally-Linear Embedding. Google each of them to see some pictures. $\endgroup$
    – amoeba
    Jan 13 '15 at 22:38
  • $\begingroup$ Sounds like it could be topological data analysis by Gunnar Carlsson at Stanford. $\endgroup$ Jan 13 '15 at 22:40