Algorithme pour trouver des utilisateurs similaires à travers une table de jointure

Question

J'ai une application où les utilisateurs peuvent sélectionner une variété d'intérêts d'environ 300 intérêts possibles. Chaque intérêt sélectionné est stocké dans une table de jointure contenant les colonnes user_id et interest_id.

utilisateurs typiques sélectionner environ 50 intérêts sur la 300.

Je voudrais construire un système où les utilisateurs peuvent trouver les 20 premiers utilisateurs qui ont le plus d'intérêts en commun avec eux.

En ce moment, je suis en mesure d'accomplir ceci en utilisant la requête suivante:

SELECT i2.user_id, count(i2.interest_id) AS count 
    FROM interests_users as i1, interests_users as i2 
    WHERE i1.interest_id = i2.interest_id AND i1.user_id = 35 
    GROUP BY i2.user_id 
    ORDER BY count DESC LIMIT 20; 

Cependant, cette requête prend environ 500 millisecondes pour exécuter avec 10.000 utilisateurs et 500.000 lignes dans la table de jointure. Tous les index et les paramètres de configuration de la base de données ont été ajustés au mieux de mes capacités.

J'ai aussi essayé d'éviter l'utilisation des jointures avec tout à fait la requête suivante:

select user_id,count(interest_id) count 
    from interests_users 
    where interest_id in (13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,508) 
    group by user_id 
    order by count desc 
    limit 20; 

Mais celui-ci est encore plus lent (~ 800 millisecondes).

Comment est-ce que je pourrais mieux réduire le temps que je peux rassembler ce genre de données à moins de 100 millisecondes? J'ai envisagé de mettre ces données dans une base de données graphique comme Neo4j, mais je ne suis pas sûr si c'est la solution la plus simple ou si elle serait même plus rapide que ce que je fais actuellement.

Answer 1

Le code que vous avez indiqué comme réponse est incorrect. En stockant les comptes dans un hachage, vous oublierez beaucoup d'utilisateurs, puisque vous ne garderez qu'un utilisateur par total. Si deux utilisateurs ont les mêmes intérêts (ou ont au moins le même nombre d'intérêts correspondants avec l'utilisateur actuel), par exemple, votre variable t sera la même et la première regardée sera écrasée par la seconde.

Voici une version correcte du code que vous avez posté en réponse. Il est plus court et plus idiomatique et devrait être plus rapide aussi. Notez que j'ai utilisé true et false au lieu de 1 et 0.

USERS_COUNT = 10_000 
INTERESTS_COUNT = 500 

users = Array.new(USERS_COUNT) { rand(100000)+100000 } 

table = Array.new(INTERESTS_COUNT) do 
    Array.new(USERS_COUNT) { rand(10) == 0 } 
end 

s = Time.now 
cur_user = 0 
cur_interests = table.each_index.select{|i| table[i][cur_user]} 

scores = Array.new(USERS_COUNT) do |user| 
    nb_match = cur_interests.count{|i| table[i][user] } 
    [nb_match, users[user]] 
end 

scores.sort! 

puts Time.now.to_f - s.to_f 

BTW, vous pouvez presser un peu plus de performance en transposant la table, qui éviterait la moitié des recherches.

Answer 2

Ce dont vous parlez s'appelle clustering.

Clustering est une question difficile, et calculer à la volée nécessite plus de ressources que nous voulons épargner je crains, car un calcul complet est O (N).

Je pense que la recherche d'idées sur cette voie est peu susceptible de donner des résultats (je peux me tromper) en raison de la complexité inhérente du problème. Cependant, il n'est pas nécessaire de tout calculer à partir de zéro à chaque fois. Je n'ai pas été capable de comprendre une image évolutive (raisonnable) et comment la mettre à jour.

Je peux cependant trouver comment mettre en cache le résultat!

UserId* | LinkedUserId* | Count 
35  | 135   | 47 
35  | 192   | 26 

(un index pour UserId et un autre pour LinkedUserId, la contrainte d'unicité est qu'il ne devrait jamais être 2 lignes avec la même paire de noms d'utilisateur/LinkedUserId)

Chaque fois que vous devez obtenir le groupe pour cette utilisateur, consultez d'abord la table de cache.

Maintenant, nous devons également invalider certaines entrées de cache de temps en temps: chaque fois qu'un utilisateur ajoute ou supprime un intérêt, alors il affecte potentiellement tous les utilisateurs qui lui sont liés.

Lorsqu'un utilisateur ajoute une entrée, invalide toutes les lignes de cache des utilisateurs utilisant cet intérêt.

Lorsqu'un utilisateur supprime une entrée, invalide toutes les lignes de cache des utilisateurs qui lui sont liés.Honnêtement, je ne suis pas sûr qu'il serait plus performant.

Answer 3

SELECT DISTINCT TOP 20 b.user_id, SUM(1) OVER (PARTITION BY b.user_id) AS match 
    FROM interests_users a 
    LEFT OUTER JOIN interests_users b ON a.interest_id = b.interest_id AND b.user_id <> 35 
WHERE a.user_id = 35 AND b.user_id IS NOT NULL 
ORDER BY 2 DESC 

Si vous construisez de bons index, ça devrait aller.

Answer 4

En fait, j'ai été en mesure d'obtenir ce que je cherchais en faisant cela en pur Ruby.

D'abord, je crée un tableau à deux dimensions où chaque colonne est un utilisateur et chaque ligne est un intérêt. Chaque valeur dans le tableau est 0 ou 1 selon que l'utilisateur actuel a cet intérêt. Ce tableau est stocké en mémoire avec des fonctions pour ajouter ou modifier des lignes et des colonnes.

Ensuite, quand je veux calculer les utilisateurs avec des intérêts similaires à l'utilisateur actuel, je rajoute toutes les colonnes pour chaque ligne où la colonne est définie sur "1" pour l'utilisateur actuel. Cela signifie que je dois parcourir 10 000 colonnes et exécuter en moyenne 50 opérations d'addition par colonne, suivies d'une opération de tri à la toute fin.

Vous pouvez supposer que cela prend beaucoup de temps, mais c'est en fait environ 50-70 millisecondes sur ma machine (Core 2 Duo, 3ghz., Ruby 1.9.1), et environ 110 millisecondes sur nos serveurs de production. La bonne chose est que je n'ai même pas besoin de limiter le jeu de résultats.

Voici le code ruby ​​que j'ai utilisé pour tester mon algorithme.

USERS_COUNT = 10_000 
INTERESTS_COUNT = 500 

users = [] 
0.upto(USERS_COUNT) { |u| users[u] = rand(100000)+100000 } 

a = [] 
0.upto(INTERESTS_COUNT) do |r| 
    a[r] = [] 
    0.upto(USERS_COUNT) do |c| 
    if rand(10) == 0 # 10% chance of picking an interest 
     a[r][c] = 1 
    else 
     a[r][c] = 0 
    end 
    end 
end 

s = Time.now 

countable_rows = [] 

a.each_index { |i| countable_rows << i unless a[i][0].zero? } 

b = {} 
0.upto(USERS_COUNT) do |c| 
    t = 0 
    countable_rows.each { |r| t+= a[r][c] } 
    b[t] = users[c] 
end 
b = b.sort {|x,y| y[0] <=> x[0] } 

puts Time.now.to_f - s.to_f 

Les premières lignes sont utilisées pour créer un tableau bidimensionnel simulé. Le reste du programme exécute l'algorithme comme je l'ai décrit ci-dessus.

L'algorithme ci-dessus évolue raisonnablement bien pendant un certain temps. Évidemment, il ne conviendrait pas à plus de 50 000 utilisateurs, mais comme notre produit segmente les communautés en petits groupes, cette méthode fonctionne assez bien (et beaucoup plus rapidement que SQL).

Toutes les suggestions sur la façon dont il pourrait être réglé pour des performances encore meilleures sont les bienvenues.