Databases
StackOverflow2013
Postsdbo
POAlgorithm for filling a matrix of item, item pairs
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POAlgorithm for filling a matrix of item, item pairs
    primarykey
    data
    text
    <p>Hey guys, I have a sort of speed dating type application (<strong>not used for dating, just a similar concept</strong>) that compares users and matches them in a round based event.</p> <p>Currently I am storing each user to user comparison (using cosine similarity) and then finding a round in which both users are available. My current set up works fine for smaller scale but I seem to be missing a few matchings in larger data sets.</p> <pre><code>For example with a setup like so (assuming 6 users, 3 from each group) Round (User1, User2) ---------------------------- 1 (x1,y1) (x2,y2) (x3,y3) 2 (x1,y2) (x2,y3) (x3,y1) 3 (x1,y3) (x2,y1) (x3,y2) </code></pre> <p>My approach works well right now to ensure I have each user meeting the appropriate user without having overlaps so a user is left out, just not with larger data sets.</p> <pre><code>My current algorithm </code></pre> <p>I store a comparison of each user from x to each user from y like so</p> <pre><code>Round, user1, user2, similarity </code></pre> <p>And to build the event schedule I simply sort the comparisons by similarity and then iterate over the results, finding an open round for both users, like so:</p> <pre><code>event.user_maps.all(:order =&gt; 'similarity desc').each do |map| (1..event.rounds).each do |round| if user_free_in_round?(map.user1) and user_free_in_round?(map.user2) #creates the pairing and breaks from the loop end end end </code></pre> <p>This isn't exact code but the general algorithm to build the schedule. Does anyone know a better way of filling in a matrix of item pairings where no one item can be in more than one place in the same slot?</p> <p><code>EDIT</code></p> <p>For some clarification, the issue I am having is that in larger sets my algorithm of placing highest similarity matches first can sometimes result in collisions. What I mean by that is that the users are paired in such a way that they have no other user to meet with.</p> <p>Like so:</p> <pre><code>Round (User1, User2) ---------------------------- 1 (x1,y1) (x2,y2) (x3,y3) 2 (x1,y3) (x2,nil) (x3,y1) 3 (x1,y2) (x2,y1) (x3,y2) </code></pre> <p>I want to be able to prevent this from happening while preserving the need for higher similar users given higher priority in scheduling.</p> <p>In real scenarios there are far more matches than there are available rounds and an uneven number of x users to y users and in my test cases instead of getting every round full I will only have about 90% or so of them filled while collisions like the above are causing problems.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USJimmy
    1. USJimmy
    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. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POAlgorithm for filling a matrix of item, item pairs
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POAlgorithm for filling a matrix of item, item pairs
      1. US828
      1. VTFavorite
    1. COUnless you're prone to dating yourself, I think the idea of maximising similarity is a horrendous one. Of all the dates I had (thanking whatever deity you believe in that I'm now married), the _worst_ ones were with IT bods, mostly because of the arguments about efficiency of sort algorithms and such :-) The best ones were with people well outside my area of expertise but with a _moderate_ amount of commonality. I think if I ever dated someone exactly like me, it would be like a matter/anti-matter explosion.
      singulars
      1. POAlgorithm for filling a matrix of item, item pairs
      1. USpaxdiablo
    2. COIt's not for dating, but a similar concept
      singulars
      1. POAlgorithm for filling a matrix of item, item pairs
      1. USJimmy
    3. COBy the way, I'm strangely transfixed by your gravatar :-)
      singulars
      1. POAlgorithm for filling a matrix of item, item pairs
      1. USpaxdiablo
 

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