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) &lt; threshold
                return false


        storedPoints.add(newPoint)
        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?
I'm not sure what you mean by 'overlapping points', and even less clear how you construct a 2D scatter plot from 4D data unless by doing some kind of projection. Having said that, what I think you're looking for is a dynamic near-neighbor data structure. Specifically, you want a data structure that processes queries of the form "Who's my nearest neighbor in the current set" and "insert a point into the current set"

While there's a ton of work on different kinds of near-neighbor structures, your particular situation (dynamic 4D points) suggests at least starting with a grid-based structure. Make (4D) buckets based on segmenting the coordinates, and hash the points in, and then for a query you can do a spiral search (or something similar) around the cell your query lies in. 

The next idea would be to build a generalized quad tree data structure (a compressed quad tree) or even something involving space-filling curves, if this first approach doesn't yield the performance you need. There are even more powerful methods, but I wouldn't recommend looking into them till you've exhausted the simple approaches. 

Bottom line: "dynamic" and "nearest-neighbor" and "low dimensional" are your google friends.