I need to calculate the distance two points, but these two points contain more than 100 dimensions. With the regular two or three dimension distance formula, we can extend this further to n dimension distance formula, however, this takes some computation time quite a bit. So if possible, I would like to find a way to cut down some computation, as I have quite a number of huge data sets.

My constrains are:

  • In one data set, all points contain exactly n dimension, but n is quite huge, always more than 100.
  • the numerical data in each dimension lies between 0 to 255 only.

With these constrains above, is there a faster way to compute the n dimension distance between each point in this case?

  • $\begingroup$ What is taking all that time for you? You're not doing a square root for each new dimension, are you? Or it is the squarings that cost you time? $\endgroup$ – Henning Makholm Nov 21 '12 at 15:46
  • $\begingroup$ To be frank, I am not sure, but I am using en.wikipedia.org/wiki/Euclidean_distance#N_dimensions $\endgroup$ – Karl Nov 21 '12 at 15:49
  • $\begingroup$ Frankly, in 100 dimensions, it might be the case that Euclidean distance is not the best measure anyway; high-dimensional space is just asn awful lot of void. The 1-norm $d(a,b)=\sum |a_i-b_i|$ or the $\infty$-norm $d(a,b)=\max |a_i-b_i|$ might be just as useful, but that depends on your intended application. $\endgroup$ – Hagen von Eitzen Nov 21 '12 at 16:24
  • $\begingroup$ @Hagen: could you elaborate what is ∞-norm ? $\endgroup$ – Karl Nov 22 '12 at 14:07

Squaring is generally quite fast, there are faster ways to optimize square roots http://en.wikipedia.org/wiki/Fast_inverse_square_root

You could always offload the computation onto the GPU if you have the freedom to do that. I'm not entirely sure of the situation here

You could also try building a lookup table of square numbers (between 0-255) if they are whole numbers only and keep in memory.


Your constraints that the values are betwen 0 and 255 indicate that they are actually one byte integers, not floating point numbers. In that case, squaring might be sped up by a lookup table, but in fact parallel SSE squaring might even be faster CPU-wise. The sum of 100 squares then fits into 3 bytes and taking a single square root is quite fast. However, often you might be able to simply drop taking the square root. For example, if you want to sort points by distance, you could also sort by squared distance. Or to see if a point is closer than 100 units, check if the squared distance is less than 10000.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.