<p>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"</p>

<p>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 <a href="http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/" rel="nofollow">spiral search</a> (or something similar) around the cell your query lies in. </p>

<p>The next idea would be to build a <a href="http://goo.gl/pLiEO" rel="nofollow">generalized quad tree data structure</a> (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. </p>

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

CC BY-SA 3.0
2011-10-12T21:02:51.573Z
hmm... what about something like a kd-Tree? or Flann?
slayton
CC BY-SA 3.0
2011-10-12T21:06:48.950Z
I don't know what a 'Flann' is, but k-d trees are also viable solutions.
Suresh Venkat
CC BY-SA 3.0
2011-10-13T11:51:40.360Z
http://opencv.willowgarage.com/documentation/cpp/flann_fast_approximate_nearest_neighbor_search.html
Jeffε
CC BY-SA 3.0
2011-10-12T20:17:48.537Z
2011-10-12T20:17:48.537Z
Suresh Venkat
<p>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.  </p>

<p>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:</p>

<p><img src="https://i.sstatic.net/ELjdr.png" alt="enter image description here"></p>

<p>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.  </p>

<p>I've thought of a few way of doing this. One of which would use an intelligent data structure that when <code>insertNewPoint</code> 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. </p>

<p>Here is some pseudo code that illustrates the idea:</p>

<pre><code>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
    }

}
</code></pre>

<p>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. </p>

<p>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? </p>

CC BY-SA 3.0
2011-10-12T20:34:58.463Z
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
CC BY-SA 3.0
2011-10-12T21:01:56.943Z
I think that's similar to the answer I gave below...
Suresh Venkat
CC BY-SA 3.0
2011-10-13T00:55:25.613Z
@SureshVenkat: Oh, apologies, I somehow understood your answer so that you were describing how to implement *exact* queries.
Jukka Suomela
CC BY-SA 3.0
2011-10-13T02:12:32.477Z
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
CC BY-SA 3.0
2011-10-13T14:08:15.513Z
@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
CC BY-SA 3.0
2011-10-13T14:16:33.197Z
@slayton: But if you use a hash table, you do not need to store empty bins; the size of the hash table is approximately the number of non-empty bins.
Jukka Suomela
CC BY-SA 3.0
2011-10-13T14:20:51.697Z
By the way, another possible approach might be this: If you only need 2-dimensional projections, you can simply generate the 2-dimensional bitmaps directly. Just plot the point (in each projection that you might find relevant) and discard the original point. The memory usage will be constant (the size of the bitmaps), no matter how many points you get.
Jukka Suomela
<ds.data-structures><cg.comp-geom><near-neighbors>
What data structures exist for fast calculation of distances between multi-dimensional points
slayton
# What data structures exist for fast calculation of distances between multi-dimensional points

(Asked by: username_0 on 2011-10-12)

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


        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?

**Tags:** ds.data-structures, cg.comp-geom, near-neighbors
> **Comments:**
> **username_1**: 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".  
> **username_2**: I think that's similar to the answer I gave below...  
> **username_1**: @SureshVenkat: Oh, apologies, I somehow understood your answer so that you were describing how to implement *exact* queries.  
> **username_2**: I was, but grids are good for the approximate kind as well as you point out. Not clear exactly what the OP wants though.  
> **username_0**: @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  
> **username_1**: @slayton: But if you use a hash table, you do not need to store empty bins; the size of the hash table is approximately the number of non-empty bins.  
> **username_1**: By the way, another possible approach might be this: If you only need 2-dimensional projections, you can simply generate the 2-dimensional bitmaps directly. Just plot the point (in each projection that you might find relevant) and discard the original point. The memory usage will be constant (the size of the bitmaps), no matter how many points you get.  

---

## 1 answers

### Answer by username_2 on 2011-10-12. Score: 4 | Accepted answer

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](http://www.ecse.rpi.edu/Homepages/wrf/pmwiki/) (or something similar) around the cell your query lies in.

The next idea would be to build a [generalized quad tree data structure](http://goo.gl/pLiEO) (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.

> **Comments:**
> **username_0**: hmm... what about something like a kd-Tree? or Flann?  
> **username_2**: I don't know what a 'Flann' is, but k-d trees are also viable solutions.  
> **username_3**: http://opencv.willowgarage.com/documentation/cpp/flann_fast_approximate_nearest_neighbor_search.html  

---

