Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I just asked my CS friend, and he came up with the algorithm below. He doesn't have an account here (and apparently unwilling to create one), but I think his answer is worth sharing.</p> <pre><code>// We will find the best match in the minimax sense; we will minimize // the maximum matching error among all pairs. Alpha maintains a // lower bound on the maximum matching error. We will raise Alpha until // we find a solution. We assume MatchError returns an L_1 error. // This first part finds the set of all possible alphas (which are // the pairwise errors between all elements larger than maxi-min // error. Alpha = 0 For all i: min = Infinity For all j &gt; i: AlphaSet.Insert(MatchError(i,j)) if MatchError(i,j) &lt; min min = MatchError(i,j) If min &gt; Alpha Alpha = min Remove all elements of AlphaSet smaller than Alpha // This next part increases Alpha until we find a solution While !AlphaSet.Empty() Alpha = AlphaSet.RemoveSmallest() sol = GetBoundedErrorSolution(Alpha) If sol != nil Return sol // This is the definition of the helper function. It returns // a solution with maximum matching error &lt;= Alpha or nil if // no such solution exists. GetBoundedErrorSolution(Alpha) := MaxAssignments = 0 For all i: ValidAssignments[i] = empty set; For all j &gt; i: if MatchError &lt;= Alpha ValidAssignments[i].Insert(j) ValidAssignments[j].Insert(i) // ValidAssignments[i].Size() &gt; 0 due to our choice of Alpha // in the outer loop If ValidAssignments[i].Size() &gt; MaxAssignments MaxAssignments = ValidAssignments[i].Size() If MaxAssignments = 1 return ValidAssignments Else G = graph(ValidAssignments) // G is an undirected graph whose vertices are all values of i // and edges between vertices if they have match error less // than or equal to Alpha If G has a perfect matching // Note that this part is NP-complete. Return the matching Else Return nil </code></pre> <p>It relies on being able to compute a perfect matching of a graph, which is NP-complete, but at least it is reduced to a known problem. It is expected that the solution be NP-complete, but this is OK since in practice the size of the given lists are quite small. I'll wait around for a better answer for a few days, or for someone to expand on how to find the perfect matching in a reasonable way.</p>
    singulars
    1. This table or related slice is empty.
    1. POAlgorithm to find matching pairs in a list
      singulars
      1. PTQuestion
    1. PTAnswer
    1. This table or related slice is empty.
    1. USVictor Liu
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. COEh? Perfect matching is NPC? How about http://en.wikipedia.org/wiki/Edmonds%27s_matching_algorithm
      singulars
      1. PO
      1. USRobert Obryk
    2. COYes, you're right. Finding a perfect matching is actually a reasonably polynomial time operation. Saw that after posting, but didn't bother fixing it. It's rather surprising, since it feels like one of those things which should be difficult. Either way, this answer is superseded by my other one now.
      singulars
      1. PO
      1. USVictor Liu
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload