determining the distance between points in n-dimensions

Question

I am building a mySQL table listing points in n-dimensions, each dimension being indexed. Given any point in the n-dimensional system, I would like to be able to output all of the other points in order of their distance from the chosen point.

A simple solution would be to calculate distances from each point using the pythagorean theorem... sqrt(x^2+y^2)=z. I have been seeking a more efficient method. Only an approximate order is needed, so i'm very open minded.

Thanks.

-diddle

Answer 1

Along with what's been given, you could also consider "binning" your points -- i.e. (at least mentally) draw a grid over your "map", and track points based on which square they fall into. Basically, you start with the points in the same square, then the ones in a "ring" surrounding the chosen point's square, then the next ring outward, and so on. Depending on the size of grid you use, you can make this about as precise or approximate as you like. Of course, a 2D grid is for 2D points -- if have more dimensions, you'll have to increase the dimensionality of the grid to match.

Answer 2

A common technique for this sort of thing is to consider the squared distance instead of the actual distance which eliminates the square root, but, if I am understanding the question correctly, you don't need to retrieve the actual distance from your index. In that case you could just use the sum of the absolute value of each component.