fun.html

<h1>Estimation statistique de la taille des vues</h1>



<div class="">
    <p><strong>Conventions mathématiques</strong></p>
    <p>En informatique, il est important de pouvoir interpréter et appliquer un algorithme. On exprime souvent les algorithmes en utilisant une notation mathématique appelée pseudo-code. Elle a l’avantage de ne pas être spécifique à un langage informatique donné. Elle a l’inconvénient d’être intimidante, surtout lorsqu’on trouve les notations mathématiques ardues.<br class="autobr">
        (Ne vous en faites pas&nbsp;: il y a peu de pseudo-code dans ce cours!)</p>
    <p>En informatique, on utilise toujours le logarithme en base 2&nbsp;: $$<code><span class="spip_code" dir="ltr">\log 8 =3$$</span></code>. On note parfois le logarithme en base 2 &nbsp;avec $$<code><span class="spip_code" dir="ltr">\log_2$$</span></code>. Pour calculer le logarithme en base 2 avec<br class="autobr">
        une calculatrice qui n’a pas le logarithme en base 2, il suffit d’utiliser la formule $$<code><span class="spip_code" dir="ltr">\log_2 x = \log_a x /\log_a 2$$</span></code>. Dans les faits, il suffit de diviser le logarithme par $$<code><span class="spip_code" dir="ltr">\log_a 2$$</span></code>.</p>
    <p>On utilise la convention que $$<code><span class="spip_code" dir="ltr">x\leftarrow a$$&nbsp;</span></code>est l’assignation de la valeur $$<code><span class="spip_code" dir="ltr">a$$</span></code> à la variable $$<code><span class="spip_code" dir="ltr">x$$</span></code>.</p>
    <p>On note $$<code><span class="spip_code" dir="ltr">\lfloor x \rfloor$$</span></code> le plus grand entier plus petit ou égal à $$<code><span class="spip_code" dir="ltr">x$$</span></code>. On note $$<code><span class="spip_code" dir="ltr">\lceil x \rceil$$</span></code> le plus petit entier plus grand ou égal à $$<code><span class="spip_code" dir="ltr">x$$</span></code>. Nous avons que $$<code><span class="spip_code" dir="ltr">\lfloor 0.1 \rfloor = 0$$</span></code>&nbsp; et $$<code><span class="spip_code" dir="ltr">\lceil 0.1 \rceil = 1$$</span></code>. Nous avons aussi que $$<code><span class="spip_code" dir="ltr">\lfloor 0.9 \rfloor = 0</span></code>&nbsp;$$ et $$<code><span class="spip_code" dir="ltr">\lceil 0.9 \rceil = 1$$</span></code>.</p>
    <p>La valeur $$<code><span class="spip_code" dir="ltr">{k\choose a}$$</span></code> est le <a href="https://fr.wikipedia.org/wiki/Coefficient_binomial" class="spip_out" rel="noopener noreferrer external" target="_blank">coefficient binomial</a> définit par $$<code><span class="spip_code" dir="ltr">{k\choose a}=\frac{k!}{a! (k-a)!}$$</span></code> où $$<code><span class="spip_code" dir="ltr">k!$$</span></code> est la <a href="https://fr.wikipedia.org/wiki/Factorielle" class="spip_out" rel="noopener noreferrer external" target="_blank">factorielle</a>. Par exemple, nous avons $$<code><span class="spip_code" dir="ltr">{k\choose 1}=k</span></code>, <code><span class="spip_code" dir="ltr">{k\choose 2}=k(k-1)/2$$</span></code> et ainsi de suite.</p>
    <p><strong>Approche statistique</strong></p>
    <p>L’estimation de la taille d’une vue à l’aide d’une méthode statistique se fait normalement par échantillonnage, c’est-à-dire que l’on ne retient qu’une partie de nos données. Un algorithme aléatoire sélectionne les données à retenir.</p>
    <p><strong>Exemple</strong>. Si je sais que chez 1000 hommes choisis aléatoirement, un homme sur quatre a le cancer, je peux conclure que dans une population de 4 millions d’hommes, environ un million d’hommes ont le cancer.</p>
    <p>L’avantage de travailler avec un échantillon est que le traitement peut être beaucoup plus rapide et que l’utilisation de la mémoire est généralement minimale.</p>
    <p>L’inconvénient majeur de l’échantillonnage est que si l’on sélectionne un échantillon de nos données avant de faire les calculs, il peut être nécessaire de faire une hypothèse concernant la distribution statistique de nos données.</p>
    <p><strong>Exemple</strong>. Si je sais que chez 1000 hommes choisis aléatoirement, il n’y a que 40 prénoms différents (incluant Daniel, Robert, Richard, etc.), est-ce que je peux conclure que dans une population de 4 millions d’hommes, il y aura proportionnellement 160 mille prénoms différents?</p>
    <p>En pratique, dans les bases de données, un type d’agrégat particulièrement fréquent et difficile à estimer prend la forme d’une requête SQL avec un GROUP BY («&nbsp;SELECT D1, D2, ..., Dd FROM table GROUP BY D1, D2, ..., Dd&nbsp;»). Pour comprendre pourquoi il est difficile de faire une telle estimation, supposez que vous disposez d’une table où l’une des colonnes est très biaisées, c’est-à-dire qu’elle comporte des valeurs très peu fréquentes et des valeurs qui sont, au contraire, très fréquentes. Par exemple, prenons la colonne «&nbsp;produit&nbsp;» dans une base de données commerciales. Alors qu’une entreprise en ligne peut disposer de millions de produits (c’est le cas notamment de la société Amazon), la plupart des achats peuvent ne porter que sur une centaine ou un millier de produits. Ainsi, une requête de la forme «&nbsp;SELECT produit FROM table GROUP BY produit&nbsp;» peut donner un résultat qui comporte des millions de rangées, alors que si on utilise un échantillon et qu’on y fait la même requête, seulement un petit millier de produits seront sélectionnés.</p>
    <p>Il faut donc, d’une certaine manière, pouvoir estimer rapidement le biais des distributions. Heureusement, en pratique, les données sont souvent distribuées de manière assez prévisibles ce qui rend la chose plus facile. Par exemple, Faloutsos et al.<span class="spip_note_ref">&nbsp;[<a href="#nb1" class="spip_note" rel="appendix" title="C. Faloutsos, Y. Matias, and A. Silberschatz. Modeling  skewed distribution&nbsp;(...)" id="nh1">1</a>]</span> ont observé qu’on rencontre souvent des <i>distributions multifractales</i> dans le contexte des grandes bases de données.</p>
    <p>Une distribution multifractale est définie comme suit. On suppose qu’il y a $$<code><span class="spip_code" dir="ltr">2^k$$</span></code> valeurs distinctes. L’entier <code><span class="spip_code" dir="ltr">k</span></code> est l’ordre de la distribution. On choisit une probabilité $$<code><span class="spip_code" dir="ltr">p$$</span></code> ($$<code><span class="spip_code" dir="ltr">0 \leq p \leq 1$$</span></code>). La valeur $$<code><span class="spip_code" dir="ltr">p$$</span></code> est le biais de la distribution. Initiallement, on dispose les valeurs distinctes en deux tas de taille égale. Le premier tas reçoit une probabilité de $$<code><span class="spip_code" dir="ltr">p$$</span></code> alors que le second reçoit une probabilité de $$&nbsp;<code><span class="spip_code" dir="ltr">1-p$$</span></code>. On procède alors de manière itérative. Le premier tas, celui ayant une probabilité totale de $$<code><span class="spip_code" dir="ltr">p$$</span></code>, est divisé en deux tas auxquels ont alloue des probabilités de $$<code><span class="spip_code" dir="ltr">p^2$$</span></code> et $$<code><span class="spip_code" dir="ltr">p(1-p)$$</span></code>. Et ainsi de suite.</p>
    <p><strong>Exemple</strong>. Une distribution multifractale d’ordre 3 ($$<code><span class="spip_code" dir="ltr">k=3$$</span></code>) et de biais $$<code><span class="spip_code" dir="ltr">0.7$$</span></code> ($$<code><span class="spip_code" dir="ltr">p=0.7$$</span></code>) portera sur $$<code><span class="spip_code" dir="ltr">2^3=8$$</span></code> valeurs distinctes ayant des probabilités de $$<code><span class="spip_code" dir="ltr">(1-p)^3=0.027$$</span></code>, $$<code><span class="spip_code" dir="ltr">(1-p)^2 p=0.063$$</span></code>, $$<code><span class="spip_code" dir="ltr">(1-p)^2 p=0.063$$</span></code>, $$<code><span class="spip_code" dir="ltr">(1-p) p^2=0.147$$</span></code>, $$<code><span class="spip_code" dir="ltr">(1-p)^2 p=0.063$$</span></code>, $$<code><span class="spip_code" dir="ltr">(1-p) p^2=0.147$$</span></code>, $$<code><span class="spip_code" dir="ltr">(1-p) p^2=0.147$$</span></code>, $$<code><span class="spip_code" dir="ltr">p^3= 0.343$$</span></code>.</p>
    <p><strong>Exercice</strong>. Expliquez pourquoi la somme des probabilités dans une distribution multifractale doit être égale à un?</p>
    <p>Sur la base de ce type de distribution, Faloutsos et al. propose d’utiliser l’algorithme suivant pour estimer rapidement la taille d’une requête de type "SELECT D1, D2, ..., Dd FROM table GROUP BY D1, D2, ..., Dd". Cet algorithme a la particularité d’estimer tout à la fois le biais de la distribution et la taille de la vue. Il est aussi facile à mettre en oeuvre.</p>
    <p>Nous avons <a href="https://m2.teluq.ca/pluginfile.php/1069855/mod_folder/content/0/sem3/zip_MultiFractal.java.zip?forcedownload=1" class="spip_out" rel="noopener noreferrer external" target="_blank">une version mise en oeuvre en Java</a>.</p>


    <p>Voici une mise en oeuvre en Python:</p>

    <div style="max-width: 1000px; margin: 0 auto; background-color: #ffffff; padding: 24px; border-radius: 8px; box-shadow: 0 4px 6px rgba(0, 0, 0, 0.1);">Laboratoire Python en ligne
        <p style="margin-bottom: 16px; color: #4b5563;">
            Modifiez ou utilisez le code Python ci-dessous, puis cliquez sur "Exécuter" pour afficher les résultats. Exemple :
        </p>
        <script src="https://cdn.jsdelivr.net/pyodide/v0.27.6/full/pyodide.js"></script>


        <script src="https://cdnjs.cloudflare.com/ajax/libs/highlight.js/11.11.1/highlight.min.js"></script>
        <script src="https://cdn.jsdelivr.net/gh/highlightjs/[email protected]/build/languages/python.min.js"></script>

        <div style="background-color: #f9fafb; padding: 16px; border: 1px solid #e5e7eb; border-radius: 8px;">
            <p style="font-size: 16px; font-weight: bold; color: #374151; margin-bottom: 8px;">Code Python :</p>
            <textarea class="language-python" id="pythonInput" rows="15" cols="45" style="width: 100%; padding: 8px; border: 1px solid #d1d5db; border-radius: 4px; font-family: monospace; font-size: 14px; margin-bottom: 16px;">import math

class MultiFractal:
    @staticmethod
    def binom(n: int, m: int) -&gt; int:
        """
        Binomial coefficient
        """
        b = [0] * (n + 1)
        b[0] = 1
        for i in range(1, n + 1):
            b[i] = 1
            for j in range(i - 1, 0, -1):
                b[j] += b[j - 1]
        return b[m]

    @staticmethod
    def estimation(mmax: int, F0: int, p: float, N: int) -&gt; float:
        """
        mmax: number of occurrences of the most frequent row in g (groupby of the sample)
        F0: number of rows in g (groupby of the sample)
        p: sampling ratio
        N: number of rows in the initial table
        """
        k = math.ceil(math.log(F0) / math.log(2))
        print(f"valeur minimale de k = {k}")
        F = 0.0
        Nprime = math.floor(p * N)
        print(f"Nprime = {Nprime}")

        while F &lt; F0:
            print(f"Debut de boucle avec k = {k} p = {p} F = {F}")
            p = (mmax / Nprime) ** (1 / k)
            F = 0
            for a in range(k + 1):
                F += MultiFractal.binom(k, a) * (1 - ((p ** (k - a)) * ((1 - p) ** a)) ** Nprime)
            k += 1

        print(f"Valeur finales: k = {k} p = {p} F = {F}")
        p = (mmax / N) ** (1 / k)
        print(f"Dernier p = {p}")

        answer = 0
        for a in range(k + 1):
            answer += MultiFractal.binom(k, a) * (1 - ((p ** (k - a)) * ((1 - p) ** a)) ** N)
        
        return answer

if __name__ == "__main__":
    # Self-evaluation
    print(MultiFractal.estimation(4, 5, 0.01, 1100))
            </textarea>

            <button id="runButton" style="width: 100%; background-color: #2563eb; color: #ffffff; padding: 10px; border: none; border-radius: 4px; cursor: pointer; font-size: 16px; transition: background-color 0.2s; margin-bottom: 16px;">
                Exécuter
            </button>

            <div id="error" style="margin-bottom: 16px; color: #dc2626; font-size: 14px;"></div>
            <div id="result" style="padding: 12px; border: 1px solid #d1d5db; border-radius: 4px; min-height: 50px;"></div>
        </div>
    </div>

    <script type="text/javascript">
        let pyodideInstance = null;

        // Function to load Pyodide
        async function loadPyodideOnce() {
            if (pyodideInstance) {
                return pyodideInstance;
            }
            try {
                const pyodide = await loadPyodide({
                    indexURL: "https://cdn.jsdelivr.net/pyodide/v0.27.6/full/"
                });
                // Initialize sys.stdout redirection once
                pyodide.runPython(`
                    import sys
                    from io import StringIO
                    sys.stdout = StringIO()
                    sys.stderr = StringIO()
                `);
                pyodideInstance = pyodide;
                return pyodide;
            } catch (e) {
                document.getElementById('error').textContent = `Erreur : Impossible de charger Pyodide - ${e.message}`;
                throw e;
            }
        }

        // Initialize highlight.js
        hljs.highlightAll();

        // Optional: Re-highlight on content change
        const codeBlock = document.getElementById('pythonInput');
        codeBlock.addEventListener('input', function() {
            hljs.highlightElement(this);
        });

        // Event listener for the run button
        document.getElementById('runButton').addEventListener('click', async function() {
            const pythonInput = document.getElementById('pythonInput').value.trim();
            const errorDiv = document.getElementById('error');
            const resultDiv = document.getElementById('result');

            // Clear previous results and errors
            errorDiv.textContent = '';
            resultDiv.innerHTML = '';

            if (!pythonInput) {
                errorDiv.textContent = 'Erreur : Veuillez entrer un code Python.';
                return;
            }

            try {
                const pyodide = await loadPyodideOnce();

                // Clear the StringIO buffers before each run
                pyodide.runPython('sys.stdout = StringIO()');
                pyodide.runPython('sys.stderr = StringIO()');

                // Execute the Python code
                await pyodide.runPythonAsync(pythonInput);

                // Get output from stdout
                const output = pyodide.runPython('sys.stdout.getvalue()');
                // Get errors from stderr
                const errorOutput = pyodide.runPython('sys.stderr.getvalue()');

                if (errorOutput) {
                    errorDiv.textContent = `Erreur Python : ${errorOutput}`;
                } else if (output) {
                    const pre = document.createElement('pre');
                    pre.textContent = output;
                    pre.style.fontFamily = 'monospace';
                    pre.style.fontSize = '14px';
                    pre.style.color = '#374151';
                    pre.style.padding = '8px';
                    pre.style.backgroundColor = '#f9fafb';
                    pre.style.border = '1px solid #e5e7eb';
                    pre.style.borderRadius = '4px';
                    pre.style.margin = '0';
                    resultDiv.appendChild(pre);
                } else {
                    resultDiv.textContent = 'Le code s\'est exécuté sans erreur et n\'a produit aucune sortie.';
                    resultDiv.style.color = '#4b5563';
                }
            } catch (e) {
                errorDiv.textContent = `Erreur lors de l'exécution : ${e.message}`;
            }
        });

        // Load Pyodide when the page loads
        document.addEventListener('DOMContentLoaded', loadPyodideOnce);
    </script>


    <p>Voici le pseudocode&nbsp;:</p>
    <hr class="spip">
    <p><strong>En entrée&nbsp;:</strong> Une table $$<code><span class="spip_code" dir="ltr">t$$</span></code> comportant $$<code><span class="spip_code" dir="ltr">N$$</span></code> rangées</p>
    <p><strong>En entrée&nbsp;:</strong> Une sélection de colonnes $$<code><span class="spip_code" dir="ltr">D_1, D_2, \ldots, D_d$$</span></code></p>
    <p><strong>En entrée&nbsp;:</strong> Un ratio d’échantillonnage $$<code><span class="spip_code" dir="ltr">0\lt p \lt 1$$</span></code></p>
    <p><strong>En sortie&nbsp;:</strong> L’estimation de la taille d’une requête GROUP BY sur ces colonnes</p>
    <p><span class="spip-puce ltr"><b>–</b></span>&nbsp;Choisir un échantillon $$<code><span class="spip_code" dir="ltr">t’$$&nbsp;</span></code> comportant $$<code><span class="spip_code" dir="ltr">N’=\lfloor pN \rfloor$$</span></code> rangées
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Calculez le GROUP BY $$<code><span class="spip_code" dir="ltr">t’$$</span></code> sur les colonnes $$<code><span class="spip_code" dir="ltr">D_1, D_2, \ldots, D_d$$</span></code>, stockez le résultat dans $$<code><span class="spip_code" dir="ltr">g$$</span></code>
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Soit $$<code><span class="spip_code" dir="ltr">m_{\textrm{max}}$$</span></code> le nombre d’occurrences de la rangée $$<code><span class="spip_code" dir="ltr">x_1,\ldots, x_d</span></code>&nbsp;$$ la plus fréquente dans $$<code><span class="spip_code" dir="ltr">g$$</span></code>
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Soit $$<code><span class="spip_code" dir="ltr">F_0$$</span></code> le nombre de rangées dans $$<code><span class="spip_code" dir="ltr">g$$</span></code>
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Posons $$<code><span class="spip_code" dir="ltr">k \leftarrow \lceil\log F_0 \rceil$$</span></code>
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Posons $$<code><span class="spip_code" dir="ltr">F \leftarrow 0$$</span></code>
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Tant que $$<code><span class="spip_code" dir="ltr">F\lt F_0</span></code>&nbsp;$$:
    </p>
    <ul>
        <li><code><span class="spip_code" dir="ltr">$$p\leftarrow (m_\textrm{max}/{N’})^{1/k}$$</span></code></li>
        <li> <code><span class="spip_code" dir="ltr">$$F\leftarrow \sum_{a=0}^k {k\choose a} (1-(p^{k-a}(1-p)^a)^{N’})$$</span></code><span class="spip_note_ref">&nbsp;[<a href="#nb2" class="spip_note" rel="appendix" title="La valeur $k\choose a$ est le coefficient binomial." id="nh2">2</a>]</span>
        </li>
        <li> <code><span class="spip_code" dir="ltr">$$k \leftarrow k+1$$</span></code></li>
    </ul>
    <p><br><span class="spip-puce ltr"><b>–</b></span>&nbsp;Posons $$<code><span class="spip_code" dir="ltr">p\leftarrow (m_\textrm{max}/N)^{1/k}</span></code>&nbsp;$$<br><span class="spip-puce ltr"><b>–</b></span>&nbsp;<strong>Valeur retournée&nbsp;:</strong>&nbsp;$$<code><span class="spip_code" dir="ltr">\sum_{a=0}^k {k\choose a} (1-(p^{k-a}(1-p)^a)^N)$$</span></code></p>




    <hr class="spip">
    <p>Nous reviendrons sur cet algorithme dans l’activité d’autoévaluation. Évidemment, cet algorithme n’est qu’un exemple. Il existe plusieurs travaux sur l’estimation statistique des vues. Si vous voulez en savoir plus, consultez les articles suivants&nbsp;:</p>
    <p><span class="spip-puce ltr"><b>–</b></span>&nbsp;P. Haas, J. Naughton, S. Seshadri, et L. Stokes et J. D.Ullman. <a href="https://www.vldb.org/conf/1995/P311.PDF" class="spip_out" rel="noopener noreferrer external" target="_blank">Sampling-based estimation of the number of distinct values of an attribute</a>. VLDB’95, pages 311–322, 1995.
        <br><span class="spip-puce ltr"><b>–</b></span>&nbsp;P. Dagum, R. Karp, M.&nbsp;Luby, S. Ross, <a href="https://epubs.siam.org/doi/abs/10.1137/S0097539797315306" class="spip_out" rel="noopener noreferrer external" target="_blank">An Optimal Algorithm for Monte Carlo Estimation</a>, SIAM J. Comput., 2000.
    </p>
</div>
<hr>
<div class="">
    <div id="nb1">
        <p><span class="spip_note_ref">[<a href="#nh1" class="spip_note" title="Notes 1" rev="appendix">1</a>]&nbsp;</span>C. Faloutsos, Y. Matias, and A. Silberschatz. <a href="https://theory.stanford.edu/~matias/papers/mf.pdf" class="spip_out" rel="external">Modeling skewed distribution using multifractals and the 80-20 law</a>. In VLDB’96, pages 307–317, 1996.</p>
    </div>
    <div id="nb2">
        <p><span class="spip_note_ref">[<a href="#nh2" class="spip_note" title="Notes 2" rev="appendix">2</a>]&nbsp;</span>La valeur $$<i>k\choose a</i>$$ est le <a href="https://fr.wikipedia.org/wiki/Coefficient_binomial" class="spip_out" rel="external">coefficient binomial</a>.</p>
    </div>
</div>