2011-03-07 1 views
4

Je construis un site où je veux faire correspondre les gens par intérêt commun. Je le fais en calculant un poids entre chaque utilisateur et déterminer qui sont les meilleurs match - ceux qui ont un poids élevé:La meilleure façon de stocker des paires avec des poids pour 500 000 utilisateurs?

Exemple:

user 1 with user 2 = weight of 1 
user 1 with user 3 = weight of 10 
user 1 with user 4 = weight of 20 

Je veux mettre les poids dans un DB. Le problème est que si j'ai 500 000 utilisateurs c'est 500 000 x 500 000 combinaisons possibles, ou 125 000 000 000 entrées - dans une base de données mysql. Il n'est pas réaliste d'insérer autant de données dans l'un des nombreux tableaux.

Ma question est la suivante: existe-t-il un moyen de gérer autant d'appariements avec des poids en utilisant un autre type de DB? J'ai lu sur les vecteurs et les choses, mais je ne sais pas assez pour évaluer cela.

J'ai vérifié la documentation sur:

  • bases de données NoSQL: MongoDB
  • bases de données objet: (db4o, Versant)
  • bases de données graphiques: Neo4j, sones ...
  • colonne large: Hadoop , Hbase
  • document Store: CouchDB
  • Valeur clé magasin: Redis, Voldemort
  • Bases de données de grille: Gigaspaces ..
  • Bases de données XML.

Mais parmi ceux-ci, je ne vois pas de solution. Est-ce que quelqu'un a connu ce problème et peut me donner un indice?

+0

ne serait-il pas beaucoup plus facile de stocker des poids absolus, et d'utiliser des requêtes SQL et/ou des scripts pour trouver les poids relatifs les plus proches? –

+0

Ceci est une question intéressante. Je vais y penser ... –

+0

Je ne pense pas que vous allez trouver une réponse en regardant les choses NoSQL –

Répondre

1

Je vais m'excuser et dire qu'il n'y a pas de bonne solution à la question posée. Il semble qu'il n'y ait aucun moyen d'éviter de stocker les valeurs utilisateur/poids 125B étant donné la question posée.

En regardant un autre type de DB ne va pas aider. Vous ne pouvez simplement pas contourner le fait que vous avez des valeurs de 125B qui doivent être stockées.

Il y a deux manières autour de cette

  • Trouver une relation entre les utilisateurs et les poids. Par exemple. Si le poids est toujours égal à la somme des deux ID utilisateur (en supposant qu'un utilisateur possède un ID), vous n'avez pas besoin de stocker les poids.
  • Calculer à la volée et ne de la question, il ne semble pas stocker
0

que la structure représente un maillage, où chaque utilisateur est connecté à d'autres (500K X (500k -1)). Cela semble très complexe. En faisant des suppositions heuristiques, des optimisations peuvent être possibles. Hypothèse Cas 1: Toutes les paires d'utilisateurs peuvent ne pas avoir de poids, ce qui peut entraîner une matrice clairsemée. Alors pourquoi ne pas stocker des poids non-zéro seul

Hypothèse Cas 2: J'ai le sentiment fort que la gamme de poids peut être limitée. Je ne pense pas qu'il y aurait 500k poids différents, probablement 500 poids différents. Si c'est le cas, créez 500 groupes différents sous lesquels les paires d'utilisateurs sont stockées. Pas beaucoup d'espace, mais une méthode de partitionnement.

Pour économiser de l'espace en utilisant le cas 2, éliminez le besoin de stocker les utilisateurs dans ces groupes. Agréger les caractéristiques d'intérêt (une limite inférieure et une limite supérieure). Pour chercher une correspondance pour un utilisateur donné, effectuer les opérations suivantes:

  1. Traverse les 500 groupes de poids impair et aller chercher les bornes inférieures et supérieures les plus adaptés. Vous ne connaissez pas l'utilisateur exact, mais vous savez maintenant comment il/elle cartographie.
  2. Rechercher la table utilisateur pour les utilisateurs qui tombent dans la présente délimite
  3. Exécuter vous analyse plus approfondie sur le groupe d'utilisateurs réel retourné par étape 2.

Mes hypothèses peuvent être erronées. Je cas, juste donné un copain de tir.

0

Tant que votre conception implique de stocker tous les poids pour toutes les combinaisons, il n'y a aucun moyen d'éviter le problème de stockage. Une optimisation raisonnable de l'espace peut être obtenue uniquement en optimisant votre conception elle-même. Questzen ci-dessous suggère quelques bonnes approches. L'approche de la matrice clairsemée peut fonctionner au départ, mais peut devenir inutile à mesure que de plus en plus d'utilisateurs se connectent. Il serait préférable d'identifier les compartiments fixes (plages) de poids au lieu de valeurs de poids absolu par exemple. Alternativement, voyez si vous pouvez rejeter la topologie de maillage entièrement connecté et adopter quelque chose comme des clusters faiblement connectés ou une hiérarchie etc. Si oui, alors chaque cluster peut recevoir un identifiant et vous pouvez avoir des poids pour chaque utilisateur avec son propre cluster (un degré d'appartenance ') et poids pour une connexion de cluster à cluster. Le poids pour la connexion de l'utilisateur-1 dans le cluster-1 à l'utilisateur-2 dans le cluster-2 pourrait alors être dérivé en fonction des poids inter-cluster et du «degré d'appartenance» des utilisateurs à leurs propres clusters.

0

Je pense que c'est une question très simple mais intéressante, surtout si vous ne pouvez pas utiliser de trucs pour réduire le nombre de poids stockés. En fin de compte, vous avez des paires clé-valeur où les clés sont composées de paires d'utilisateurs. Tant que vous ne souhaitez récupérer que des poids individuels lorsque des paires d'utilisateurs sont données, vous pouvez utiliser le sharding. Si vos données ne changent pas souvent et que vous disposez de plusieurs ordinateurs, vous devez pouvoir implémenter votre propre stratégie de partitionnement simple ou utiliser Gizzard pour gérer un cluster simple avec un magasin de données de valeurs-clés compatible sur chaque ordinateur. (Gizzard exige que toutes les opérations soient commutatives et idempotentes.)

0

Êtes-vous prêt à créer une solution à partir de zéro? Si vous êtes à la hauteur, vous devriez peut-être créer 500 000 fichiers, un pour chaque utilisateur, et stocker 500 000 poids dans chaque fichier, triés par ID utilisateur, avec des longueurs fixes. Vous pouvez alors aller à un endroit spécifique dans le fichier dont vous avez besoin et lire la valeur, sans utiliser de délimiteurs ni stocker les identifiants de l'utilisateur. (Si vos ID utilisateur ne sont pas des numéros compris entre 1 et 500 000, vous aurez également besoin d'un mappage entre l'ID utilisateur et le nouvel ID compris entre 1 et 500 000). besoin de vos poids?
Vous pouvez arrondir chaque poids au multiple de n/(2^k) le plus proche qui correspond à vos besoins. Dans le cas de 3 décimales, vous pouvez stocker chaque nombre comme 10 bits, avec k = 10. De cette façon, chaque fichier ne serait que de 500 000 * 10 bits = 625 Ko et l'ensemble de données serait de 312,5 Go. Vous pouvez même compresser les fichiers et seulement les décompresser en cas de besoin, en fonction bien sûr des compromis que vous êtes prêt à faire entre la vitesse et l'espace. Cette solution suppose également que les modifications sont rarement effectuées et que vous ne récupérez qu'une seule valeur à la fois (ou une sorte de plage de valeurs).

1

D'après votre explication, je ne pense pas que ces poids devraient être stockés du tout. Ils sont une sorte de cache de certains calculs que vous avez fait. Vous n'avez pas besoin de stocker le résultat, car vous pouvez répéter le calcul quand vous en avez besoin. Vous pouvez toujours stocker vos poids, mais juste garder à l'esprit que c'est le cache, et que les données sont éligibles à la suppression, lorsque le cache est plein.

BTW, les utilisateurs ont généralement des filtres. Ces filtres peuvent automatiquement ignorer 95% de votre base d'utilisateurs. Vous pouvez l'utiliser à votre avantage.

-1

Le problème n'existe pas, à mon avis. Comme il n'est pas réaliste qu'une seule personne connaisse 500k personnes. Peut-être qu'une personne est connue par 500.000 personnes, mais cette personne ne connaît probablement qu'une infime fraction d'entre eux en personne, par ex. Lady Gaga

Probablement une moyenne réaliste est de 300 pour les réseaux sociaux dans la vie entière. Donc vous avez "seulement" 150 - 200 millions de relations.

Je voudrais aller avec un graphique DB, car avec eux, il est assez facile de modéliser les relations.

Questions connexes