2
$\begingroup$

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:

enter image description here

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


        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?

$\endgroup$
  • 3
    $\begingroup$ 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". $\endgroup$ – Jukka Suomela Oct 12 '11 at 20:34
  • $\begingroup$ I think that's similar to the answer I gave below... $\endgroup$ – Suresh Venkat Oct 12 '11 at 21:01
  • $\begingroup$ @SureshVenkat: Oh, apologies, I somehow understood your answer so that you were describing how to implement exact queries. $\endgroup$ – Jukka Suomela Oct 13 '11 at 0:55
  • $\begingroup$ I was, but grids are good for the approximate kind as well as you point out. Not clear exactly what the OP wants though. $\endgroup$ – Suresh Venkat Oct 13 '11 at 2:12
  • $\begingroup$ @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 $\endgroup$ – slayton Oct 13 '11 at 14:08
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ hmm... what about something like a kd-Tree? or Flann? $\endgroup$ – slayton Oct 12 '11 at 21:02
  • $\begingroup$ I don't know what a 'Flann' is, but k-d trees are also viable solutions. $\endgroup$ – Suresh Venkat Oct 12 '11 at 21:06
  • 1
    $\begingroup$ opencv.willowgarage.com/documentation/cpp/… $\endgroup$ – Jeffε Oct 13 '11 at 11:51

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.