Databases
StackOverflow2013
Postsdbo
POMySQL architecture for n * (n - 1) / 2 algorithm
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POMySQL architecture for n * (n - 1) / 2 algorithm
    primarykey
    data
    text
    <p>I'm currently developing a website where users can search for other users based on attributes (age, height, town, education, etc.). I now want to implement some kind of rating between user profiles. The rating is calculated via its own algorithm based on similiarity between the 2 given profiles. User A has a rating "match rating" of 85 with User B and 79 with User C for example. B and C have a rating of 94 and so on....</p> <p>The user should be able to search for certain attributes and filter the results by rating.</p> <p>Since the rating differs from profile to profile and also depends on the user doing the search, I can't simply add a field to my users table and use ORDER BY. So far I came up with 2 solutions:</p> <ul> <li><p>My first solution was to have a nightly batch job, that calculates the rating for every possible user combination and stores it in a separate table (user1, user2, rating). I then can join this table with the user table and order the result by rating. After doing some math I figured that this solution doesn't scale that well.</p> <p>Based on the formula n * (n - 1) / 2 there are 45 possible combination for 10 users. For 1.000 users I suddenly have to insert 499.500 rating combinations into my rating table.</p></li> <li><p>The second solution was to leave MySQL be and just calculate the rating on the fly within my application. This also doesn't scale well. Let's say the search should only return 100 results to the UI (with the highest rated on top). If I have 10.000 users and I want to do a search for every user living in New York sorted by rating, I have to load EVERY user that is living in NY into my app (let's say 3.000), apply the algorithm and then return only the top 100 to the user. This way I have loaded 2.900 useless user objects from the DB and wasted CPU on the algorithm without ever doing anything with it.</p></li> </ul> <p>Any ideas how I can design this in my MySQL db or web app so that a user can have an individual rating with every other user in a way that the system scales beyond a couple thousand users?</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USblack666
    1. USblack666
    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
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POMySQL architecture for n * (n - 1) / 2 algorithm
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POMySQL architecture for n * (n - 1) / 2 algorithm
      1. USgtgaxiola
      1. VTFavorite
    3. VO
      singulars
      1. POMySQL architecture for n * (n - 1) / 2 algorithm
      1. This table or related slice is empty.
      1. VTUpMod
    1. COIt's `n*(n-1)/2` and I don't like the title, but the question is interesting.
      singulars
      1. POMySQL architecture for n * (n - 1) / 2 algorithm
      1. USPatrick
    2. COthanks, I fixed the formula. I'm open for title suggestions .. didn't really know how else to phrase it :-)
      singulars
      1. POMySQL architecture for n * (n - 1) / 2 algorithm
      1. USblack666
    3. COat first step, isn't it possible to leave the worst matches in the database (e.g. a simpler algorithm that scales well in mysql), so that you only have to load - let's say 500 matches in your app, so that you can bring up a result that is not complete, but almost perfect?
      singulars
      1. POMySQL architecture for n * (n - 1) / 2 algorithm
      1. USRomanKonz
 

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