Problem Description

I have two sets of 2D points with flavours:

Noisy points $$p_i = (x_i, y_i, f_i) : p_i \in N : |N|\approx 10^8 $$

and true points $$p_{t_i} = (x_{t_i}, y_{t_i}, f_{t_i}) : p_{t_i} \in T : 10^6 \lt |T| \lt 10^7.$$

Each noisy point $p_i$ has been generated by adding errors $p_{e_i} = (x_{e_i}, y_{e_i}, f_{e_i})$ to a true point, s.t. $p_{t_i}+p_{e_i} = p_i$

For each point $p_i$, $(x_{e_i}, y_{e_i})$ is gaussian with a probability $P : 0.9 < P < 1$ and in the other cases $(x_{e_i}, y_{e_i})$ is so large that $p_i$ can be considered uncorrelated with $p_{t_i}$. The standard deviation of all gaussian errors in both direction $x$ and $y$ can be assumed to have the same standard deviation $\sigma$.

Flavours are different from Euclidian distances in that they can not be sorted. We can however compare two flavours and measure a distance between them. The error distribution of the flavours is unknown.

The number of noisy points generated by each true point follows a power law distribution, meaning that some true points generate far more noisy points than others. A significant amount of true points generate only a few or no noisy points.

The density of true points differs over the search space. True point density varies over regions of space between $10/\sigma$ points/area units to $1/1000 \sigma$. Number of points in different densities is also power law distributed with more points i high density.

My task is to approximate $T$, given $N$. I also want to weight each $p_{t_i}$ with a value $w_i$ representing how many noisy points it generated. I want to do this with an algorithm that will have a reasonable runtime, given the set sizes. How can this be done?


I probably want to start by clustering points according to their Euclidian position. The points in these clusters can then be checked against each other for flavour similarities and grouped further.

Point clustering in Euclidian space could be done with a KD-tree or a QuadTree. I would also like to be able to gradually feed more Noisy points into the model so I would prefer an algorithm that takes one new noisy point at a time. I could therefore merge new points into the tree if they are a close enough match to a current point. Averaging the distances and keeping a list of all flavours that have been merged.

I think that flavour is my best bet to merge efficiently as there will be such a high overlap of distributions generated from neighboring true points. My merge procedure could be one of the two following:

  • Add a new point to the tree. Locate all points within $3\sigma$. If $\delta f < \alpha$: merge those points.

  • Add a new point to the tree. Locate 1000 nearest neighbours. If $\delta |(x,y)| < 3\sigma$ and $\delta f < \alpha$: merge those points.

I would probably discard points that can not be merged with any other due to the risk of identifying false points due to noise.

  • $\begingroup$ What does it mean to approximate $T$? Can you define/specify the measure you'll use to evaluate the quality of a proposed output? $\endgroup$
    – D.W.
    Jan 28 at 6:34
  • $\begingroup$ I'm a bit confused by reference to $10/\sigma$ points/area units. I think area is proportional to $\sigma^2$, not $\sigma$, right? $\endgroup$
    – D.W.
    Jan 28 at 6:57
  • $\begingroup$ Are you sure that nothing is known about the error distribution for flavors? If truly nothing is known about the flavors, then you can't use the flavors of noisy points, as they might be totally unrelated/uncorrelated to the flavors of the corresponding true points. I suspect that you do have some partial knowledge about the error distribution, and that providing that knowledge will help with better algorithms. For instance, when you say "I think that flavour is my best bet to...", that sounds like an implicit assumption/prior that the amount of error in flavour is not too large. $\endgroup$
    – D.W.
    Jan 28 at 6:59
  • $\begingroup$ Why do you need to estimate $T$, if all the true points are given? Isn't $T$ the set of all true points, so $T$ is given? I suspect I'm misunderstanding something fundamental. I hope you can edit your post so that all of these aspects are clearer. $\endgroup$
    – D.W.
    Jan 28 at 7:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.