Estimation de la taille d'une intersection de plusieurs ensembles à l'aide d'un échantillon d'un ensemble

Je travaille sur un algorithme qui doit calculer la taille d'un ensemble généré par les intersections d'au moins 2 ensembles. Plus précisement:

z = | A_{0} \cap \dots \cap A_{n} |

$z = \left |A_0 \cap \ldots \cap A_n \right |$

Les ensembles qui sont intersectés sont générés par des requêtes SQL, et dans un effort pour garder les choses rapides, j'obtiens un compte de chaque requête à l'avance, puis je prends l'ensemble avec le plus petit nombre ( ) et j'utilise ces ID comme limites sur le reste des grandes requêtes, donc l'intersection devient effectivement: $A_0$

z = | (A_{0} \cap A_{1}) \cap \dots \cap (A_{0} \cap A_{n}) |

$z = \left |\left ( A_0 \cap A_1 \right ) \cap \ldots \cap \left ( A_0 \cap A_n \right ) \right |$

Même cette stratégie me laisse de très grosses requêtes à exécuter, car peut parfois être volumineux. Mon idée pour y faire face est de prendre un échantillon aléatoire de et de l'intersecter avec le reste des ensembles avant d'extrapoler vers une estimation correcte de . Ma question est la suivante: quelle est la meilleure façon de procéder à l'échantillonnage puis à l'extrapolation pour revenir à une valeur de qui, si elle n'est pas entièrement exacte, a une plage d'erreur prévisible? $\left | A_0 \right |$ $A_0$ $z$ $z$

Voici ce que j'ai essayé jusqu'à présent (en pseudocode, en quelque sorte):

sample_threshold := 10000
factor := 1
if (len(A0) > sample_treshold) {
    factor = sample_threshold / len(A0)
}

// Take a random sample of size 10000 from A0

// Intersect all the other sets with the A0 sample, then with each other
working_set := A0
for i, a := range A {
    a = intersect(A0, a)
    working_set = intersect(working_set, a)
}

z := len(working_set) * (1 / factor)

Ce code fonctionne, mais semble constamment surestimer z, avec une taille d'échantillon inférieure donnant une estimation plus élevée. De plus, je ne sais pas comment cela évoluerait avec plus de deux ensembles à intersecter.

J'espère que cette question a du sens, faites-moi savoir si je peux clarifier davantage. De plus, si cette question est hors sujet ou appartient à un autre endroit, faites-le moi savoir et je serai ravie de la déplacer.

Selon le commentaire de Bill , j'ai effectué quelques essais rapides pour montrer la taille de l'échantillon par rapport à l'erreur. Chaque taille d'échantillon a été exécutée 20 fois, et comme vous pouvez le voir, la tendance est assez claire:

Terrain

error sample Jimmy Sawczuk
la source

A_{0}

$A_0$

A

$A$

@Bill J'ai ajouté un graphique de la taille de l'échantillon par rapport à l'erreur qui illustre ce que je vois. Cela ressemble plus à 20 fois sur 20. Quant à l'échantillon aléatoire, il est aussi aléatoire que ORDER BY RAND(), ce qui n'est pas parfait mais devrait convenir à cette tâche.

Jimmy Sawczuk

@JimmySawczuk Ne serait-il pas préférable de simplement couper le "jeu de travail" avec "a" directement, au lieu de "recouper (A0, a)"? Parce que "A0" sera probablement plus grand que le "jeu de travail" actuel dans l'algorithme après la première exécution ... Est-ce que je comprends bien?

A_{0}

$A_0$

Puis-je également demander si la taille de l'intersection, par rapport à la taille des ensembles d'origine, est extrêmement petite? Si c'est le cas, je pense que cela expliquerait votre problème. J'ai exécuté quelques simulations (avec des ensembles plus petits) et j'obtiens également une surestimation assez cohérente, quoique petite.

Estimation de la taille d'une intersection de plusieurs ensembles à l'aide d'un échantillon d'un ensemble

Réponses: