views:

126

answers:

2

Hey,

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

+1  A: 

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.

Andrew Khosravian
Nope. Summing the absolute values is not a measure of 'distance' in the common, Euclidean sense. (You are talking of the '1-norm' measure of distance, instead.) You're right about storing / comparing the square though, that's fine.
Peter
yeah, squares look fine to compare, thanks for that. should help to reduce some of the overhead.
dittle
A: 

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.

Jerry Coffin