# What data structures exist for fast calculation of distances between multi-dimensional points

I'm writing a program that receives data over a network connection. Every data point is simply a 4 dimensional vertex, lets call the dimensions X,Y,Z,W. The values of each dimension are exponentially distributed.

I'm currently saving the data and plotting the data, in real time, as a 2D scatter plot. Here is an example of such a plot:

One thing is obvious in the picture is there are most of the points are near the origin. Any two points that overlap are redundant as they carry the identical information. This means that the majority of the points near the origin can be discarded where as very few points far from the origin can be discarded. I'd like to come up with an intelligent way to filter out redundant points.

I've thought of a few way of doing this. One of which would use an intelligent data structure that when insertNewPoint is called the structure first checks to see if any points in the data structure are within a predefined distance of the new point. If this is true than the new point is discarded otherwise it is added to the data structure.

Here is some pseudo code that illustrates the idea:

Structure Points{
list storedPoints;
distance threshold;

insertNewPoint(newPoint){
for each point in storedPoints
if calculateDistance(newPoint, point) < threshold
return false

return true
}

}


I anticipate that these data structures will eventually contain upwards of 50K+ points, and each second between 10-100 new points will be received by my program.

Are there data structures that are designed for these kind of operations? If not, what would be the most efficient way implement a structure like this for 4 dimensions?

• If you are pruning points for efficiency, most likely you do not care if there are some false negatives (i.e., you occasionally insert a point even if there is another point near it). If this is the case, you can simply discretise everything into a sufficiently dense grid: you round all coordinates, use the rounded coordinates as the key, and store all points in a hash table (discarding points with identical keys). You just need to choose a sufficiently dense grid so that "points located in the same grid cell" implies "distance is less than threshold". – Jukka Suomela Oct 12 '11 at 20:34
• I think that's similar to the answer I gave below... – Suresh Venkat Oct 12 '11 at 21:01
• @SureshVenkat: Oh, apologies, I somehow understood your answer so that you were describing how to implement exact queries. – Jukka Suomela Oct 13 '11 at 0:55
• I was, but grids are good for the approximate kind as well as you point out. Not clear exactly what the OP wants though. – Suresh Venkat Oct 13 '11 at 2:12
• @JukkaSuomela but doesn't a dense grid become un-reasonable if the dimensionality gets to high? for example if I want 100 bins on each of the 4 dimensions then i end up with 100^4 (100,000,000) bins – slayton Oct 13 '11 at 14:08