Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 3 down vote favorite

I have two tables at my disposal, one work dataset and one reference dataset. Each dataset has got two columns, lets say these are fields A and B. I would like to associate the rows in the reference dataset with the rows in work dataset that are 'closest' w.r.t. some distance. I have more rows in the work dataset than in the reference dataset, and I will match all rows in the reference dataset to some rows in the work dataset.

I can define distance between two rows in the reference and work datasets as:

$ d_{i,j} = (A_{w}(i) - A_{r}(j))^{2} + (B_{w}(i) - B_{r}(j))^{2} $

with $A_{w}, A_{r}, B_{w}, B_{r} $ the A and B columns in the work and reference datasets with obvious notation.

In other word, I want to minimize over all permutations of rows from the work dataset (with the same number of rows as in the reference dataset) the sum of distances between one row in reference dataset and one row in work dataset.

I do not know how to proceed other than by brute-force examination of all permutations.

This problem is combinatorial. What about stochastic methods: genetic algorithm, swarm...

Could you hint at some idea for a start?

Thanks!

share|improve this question
do you want to minimize the distance over all i and j, (so the point in the work data set must be as close as possible to all points in ref) or over certain pairs (such as i=j)? – Godric Seer Nov 29 '12 at 14:16
@GodricSeer i have to map each row in reference dataset to one row in work dataset minimizing sum of distances between associated rows. I have to find the best injection from reference to work dataset. – antitrust Nov 29 '12 at 14:40

1 Answer

up vote 3 down vote accepted

If I interpret the problem right, the task is to assign to each $j$ in the column index set $J$ of the distance matrix an index $x_j$ from the row index set $I$ such that the $x_j$ are all different and the $\sum_j d(x_j,j)$ is minimal.

This can be posed as a combinatorial constraint satisfaction problem to a number of constraint solvers. See, e.g.,
http://en.wikipedia.org/wiki/Constraint_programming
http://argo.matf.bg.ac.rs/publications/2010/alldiff-smt2010.pdf
http://www-circa.mcs.st-and.ac.uk/Preprints/alldiff-paper.pdf

Whether the problem is tractable depends on thestructure and size of the distance matrix derived from the data sets.

share|improve this answer
thanks a lot for your answer. i agree this is constraint combinatrial problem. However, i see it can further come down to linear assignment problem. Do you agree? nevertheless, there is one problem to convert my problem into an assignment problem: this cannot be represented by complete bipartite graph, it is not complete (may be more data in work set than in reference set). the hungarian algo holds for complete bipartite graph, do you know some way to deal with injection instead of bijection? thanks !!! – antitrust Nov 29 '12 at 16:57
@antitrust: The 2nd and 3rd cited papers on the all-different constraint contain assignment formulations of similar optimization problems. You'll have to check for yeorself whether it matches one of the easily tractable cases. In any case there is diverse CSP software that handles all-different constraints quite well, as long as the problem is not too large. – Arnold Neumaier Nov 29 '12 at 17:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.