Algorithme de recherche rapide de balises

Le problème est le suivant.

• Il y a un ensemble d'entités simples E, chacune ayant un ensemble d'étiquettes T attachées. Chaque entité peut avoir un nombre arbitraire de balises. Le nombre total d'entités est proche de 100 millions et le nombre total de balises est d'environ 5000.

Ainsi, les données initiales ressemblent à ceci:

E1 - T1, T2, T3, ... Tn
E2 - T1, T5, T100, ... Tk
..
Ez - T10, T12, ... Tl

Ces données initiales sont assez rarement mises à jour.

• D'une manière ou d'une autre, mon application génère une expression logique sur des balises comme celle-ci:

  T1 & T2 & T3 | (T5 et! T6)

• Ce que je dois faire est de calculer un nombre d'entités correspondant à une expression donnée (note - pas les entités, mais juste le nombre). Bien sûr, celui-ci n'est peut-être pas totalement exact.

Ce que j'ai maintenant, c'est une simple recherche de table en mémoire, ce qui me donne un temps d'exécution de 5 à 10 secondes sur un seul thread.

Je suis curieux, existe-t-il un moyen efficace de gérer ce genre de choses? Quelle approche recommanderiez-vous? Existe-t-il des algorithmes ou des structures de données communs pour cela?

Mise à jour

Un peu de clarification comme demandé.

1. Tles objets sont en fait des chaînes constantes relativement courtes. Mais cela n'a pas vraiment d'importance - nous pouvons toujours attribuer des ID et opérer sur des entiers.
2. Nous pouvons certainement les trier.

je le ferais dans sql ayant une table de liens EntityCategoryentre l' eidentité de cidréférence et la catégorie de référence en utilisant les auto-jointures:

    select count(ec1.eid)
    from EntityCategory ec1 
    left join EntityCategory ec2 on ec1.eid=ec2.eid 
    left join EntityCategory ec3 on ec1.eid=ec3.eid 
    ...
    where 
      ec1.cid={categoryId1} and 
      ec2.cid={categoryId2} and
      ec3.cid={categoryId3} ...

Après avoir écrit cette réponse, je devrais probablement signaler la question comme «trop large» - nous pouvons parler pendant des siècles de différentes stratégies, à la fin un benchmark devra être exécuté avec vos données.

Chaque balise peut être efficacement représentée par un entier. Chaque entité possède un ensemble de balises. Il est important de choisir l'implémentation correcte de l'ensemble - les arbres B et les tableaux triés sont possibles. Avec cet ensemble, nous ne ferons que des tests d'adhésion. Comme les deux structures le font en O (log t) (avec t tags par entité), je préférerais les tableaux en raison de leur représentation plus dense.

Nous pouvons désormais filtrer toutes les entités dans une opération O (n · log t · p) , où p est la longueur moyenne du chemin dans l'arbre de décision des prédicats. Cet arbre de décision peut être commandé afin qu'une décision puisse être prise rapidement. Sans données statistiques, il est seulement possible de factoriser la sous-expression commune.

L'ordre dans lequel les entités sont recherchées n'est pas vraiment important. D'autre part , il peut être avantageux de trier de sorte que les entités à des indices 0à itous ont une certaine étiquette, alors que le reste ne fonctionne pas. Cela réduit le n lors de la recherche de cette balise spécifique (dans l'arbre de décision, ce devrait être le premier test). Cela peut être étendu à plusieurs niveaux, mais cela complique les choses et prend de la mémoire O (2 ^k ) avec kles niveaux. Avec plusieurs niveaux, les balises avec le gain le plus élevé doivent être décidées en premier, où le gain est le nombre d'entités qui ne doivent pas être recherchées multiplié par la probabilité de les rejeter. Le gain devient maximal pour 50:50 chances ou lorsque 50% des entités ont ce tag spécifique. Cela vous permettrait d'optimiser même si les modèles d'accès ne sont pas connus.

Vous pouvez également créer des ensembles qui indexent les entités par chaque balise utilisée - un ensemble avec toutes les entités pour T1, le suivant pour T2. Une optimisation évidente (espace et temps) consiste à s'arrêter lorsqu'un ensemble contient plus de la moitié de tous les éléments et à enregistrer les éléments qui n'ont pas cette balise - de cette façon, la construction d'index pour toutes les balises prendra moins d' ½ · n · tespace (avec t tags au total). Notez que l'enregistrement d'ensembles complémentaires peut rendre d'autres optimisations plus difficiles. Encore une fois, je (triais) des tableaux pour les ensembles.

Si vous représentez également vos entités via une plage entière, vous pouvez compresser l'espace utilisé pour les ensembles d'index en stockant uniquement le membre de début et de fin d'une plage continue. Au niveau de la mise en œuvre, cela se ferait probablement avec un bit élevé pour indiquer si une entrée est une entrée liée à une plage ou une entrée régulière.

Si nous avons maintenant des ensembles d'index (et donc des statistiques sur les balises), nous pouvons optimiser nos prédicats de sorte que les propriétés improbables soient testées en premier (stratégie fail-fast). Cela signifie que si T1est commun et T2rare, le prédicat T1 & T2doit être évalué en itérant dans toutes T2les entrées de l'ensemble d'index et en testant chaque élément T1.

Si nous utilisons des tableaux triés pour implémenter les ensembles d'index, de nombreuses étapes d'évaluation peuvent être implémentées en tant qu'opérations de fusion. T1 & T2signifie que nous prenons les listes T1et T2, allouons un tableau cible de la taille des entrées les plus grandes et exécutons l'algorithme suivant jusqu'à ce que les deux entrées soient vides: Si T1[0] < T2[0], alors T1++(jetez la tête). Si T1[0] > T2[0]alors T2++. Si les deux têtes sont égales, puis copiez ce nombre vers le tableau cible, et incrémenter les trois pointeurs ( T1, T2, cible). Si le prédicat est T1 | T2, alors aucun élément n'est rejeté, mais le plus petit est copié. Un prédicat du formulaire T1 & ¬T2peut également être mis en œuvre en utilisant une stratégie de fusion, mais ¬T1ou T1 | ¬T2ne peut pas.

Cela doit être pris en compte lors de la commande de l'arbre de décision des prédicats: les compléments doivent se produire sur le RHS d'un &ou à la fin, lorsque le décompte final est déterminé et que les éléments réels n'ont pas à être examinés.

Sans utiliser d'index, chaque thread peut filtrer sa partie des entités et renvoyer le nombre d'éléments correspondant au prédicat, qui peut être résumé. Lors de l'utilisation des ensembles d'index, chaque thread se verrait attribuer un nœud dans l'arbre de décision. Il prend deux flux d'entrée qui correspondent aux ensembles ordonnés et renvoie un flux fusionné. Notez que chaque nœud de l'arbre de décision a un ensemble correspondant qui représente toutes les entités qui remplissent cette sous-expression, et qu'en raison de l'ordre des ensembles, il n'est pas nécessaire de connaître l'ensemble à la fois pour les fusionner .

Différentes stratégies telles que la fusion d'ensembles indexés ou le filtrage à travers une liste d'entités peuvent être combinées dans une certaine mesure. Le filtrage a des performances très prévisibles. Si une requête est très spécifique, de sorte que l'utilisation des ensembles d'index réduit considérablement l'espace de recherche, les opérations de fusion pourraient être meilleures. Il est important de noter que la fusion de nombreux grands ensembles d'entrée peut entraîner des performances bien pires que la recherche par force brute. Un algorithme très optimisé sélectionnera une stratégie appropriée basée sur la taille d'entrée, la structure de requête et les indicateurs statistiques.

Soit dit en passant, la mise en cache des résultats partiels peut être bénéfique si l'on prévoit que des requêtes similaires seront exécutées à l'avenir, même si elles n'accélèrent pas l'exécution initiale.