Estimation des valeurs fréquentes¶

Vue d’ensemble¶

Snowflake fournit une implémentation de l’algorithme « Space Saving » présentée dans « Efficient Computation of Frequent and Top-k Elements in Data Streams » par Metwally, Agrawal et Abbadi. Il est implémenté via l’ensemble de fonctions APPROX_TOP_K.

En outre, la fonction APPROX_TOP_K_COMBINE utilise l’algorithme « Space Saving » parallèle décrit par Cafaro, Pulimeno et Tempesta.

Le pourcentage d’erreur de l’algorithme dépend fortement de la déformation des données et du nombre de compteurs utilisés dans l’algorithme. Au fur et à mesure que les données deviennent plus déformées ou qu’un plus grand nombre de compteurs sont utilisés, le résultat est plus précis.

Fonctions SQL¶

Les Fonctions d’agrégation suivants sont fournis pour l’utilisation de « Space Saving » pour estimer les valeurs fréquentes :

• APPROX_TOP_K : renvoie une approximation des valeurs fréquentes dans l’entrée.

• APPROX_TOP_K_ACCUMULATE : ignore l’étape d’estimation finale et retourne l’état « Space Saving » à la fin d’une agrégation.

• APPROX_TOP_K_COMBINE : combine (c’est-à-dire fusionne) les états d’entrée en un seul état de sortie.

• APPROX_TOP_K_ESTIMATE : calcule une estimation de cardinalité d’un état « Space Saving » produit par APPROX_TOP_K_ACCUMULATE et APPROX_TOP_K_COMBINE.

Détails de l’implémentation¶

Chaque compteur dans notre implémentation suit un élément et sa fréquence. Notre implémentation ne suit pas les valeurs epsilon des compteurs, car elles ne sont utiles que pour donner des garanties sur le rendement de l’algorithme. Elles ne sont pas utilisées pour l’algorithme lui-même.

Le nombre maximum de compteurs est fixé à 100 000. Dans ce cas, il y a 100 000 compteurs stockés en mémoire, mais seulement une fraction d’entre eux est stockée dans un état exporté.

Le nombre maximum de k est de 100 000. Cette valeur est automatiquement réduite si toutes les valeurs ne peuvent pas être contenues dans la sortie.

Dans la plupart des cas, la durée d’exécution de notre implémentation ne dépend pas du nombre de compteurs. Notre implémentation garantit que le nombre de compteurs n’a pas d’effet notable sur la durée d’exécution de l’algorithme.

Chaque compteur dans chaque état d’agrégation utilise une quantité constante de mémoire d’environ 100 octets. Ainsi, si une agrégation utilise c compteurs et qu’il y a des g groupes d’agrégations, l’agrégation utilise c * g * 100B de mémoire, plus la mémoire pour stocker les valeurs. Si cette mémoire dépasse le budget mémoire total, la mémoire se déverse sur le disque (« spill to disk »). La quantité de mémoire est bien moindre que celle qu’utiliserait la version exacte, plus particulièrement lorsqu’il y a un grand nombre de valeurs uniques.