💻 computer science

Arithmetic Variable LogLog: Advancing the Memory-Variance Frontier

Ce document introduit l'Arithmetic Variable LogLog (AVLL), un nouvel algorithme d'estimation de cardinalité qui surpasse l'état de l'art ExaLogLog en termes de précision et de vitesse en utilisant le codage arithmétique et un mécanisme de sortie anticipée pour atteindre un produit mémoire-variance supérieur pour toutes les tailles testées.

Auteurs originaux : Brian Bushnell

Publié 2026-08-14

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Brian Bushnell

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous organisiez une fête massive où des millions d'invités défilent par la porte, mais que vous ne disposez que d'un minuscule carnet pour noter qui est présent. Vous ne pouvez pas écrire chaque nom, car cela remplirait instantanément votre carnet. Au lieu de cela, vous avez besoin d'une astuce ingénieuse pour deviner combien de personnes uniques sont venues sans les compter une par une. C'est le problème de l'estimation de la cardinalité, un casse-tête qui fascine les informaticiens depuis des décennies. L'objectif est d'extraire l'estimation la plus précise possible avec la plus petite quantité de mémoire possible.

Pendant longtemps, la meilleure façon de faire consistait à avoir une rangée de casiers, chacun d'une taille spécifique. Vous jetiez le nom d'un invité dans un casier en fonction d'un code aléatoire, et si le casier était vide, vous le marquiez. S'il était déjà plein, vous vérifiiez si le nouvel invité était "plus unique" que celui qui s'y trouvait déjà. Plus vous aviez de casiers, meilleure était votre estimation. Mais il y avait un pièat : pour obtenir une estimation super précise, il vous fallait soit plus de casiers (ce qui prenait plus de place), soit de plus gros casiers capables de contenir des informations plus détaillées sur chaque invité. Pendant des années, le débat fut : vaut-il mieux avoir quelques casiers géants et super détaillés, ou une foule immense de petits casiers simples ?

Entrez en scène un nouveau prétendant appelé Arithmetic Variable LogLog (AVLL). Imaginez-le comme un magicien qui a réalisé que l'ancienne méthode de rangement des casiers était gaspilleuse. Au lieu d'utiliser des emplacements rigides et de taille prédéfinie, l'AVLL utilise une méthode de rangement "arithmétique" flexible qui permet de faire tenir beaucoup plus de petits casiers dans le même espace. Le document suggère qu'en faisant tenir 5,5 fois plus de ces petits casiers, le système peut produire une bien meilleure estimation que les anciens champions, même si chaque casier individuel contient moins d'informations. C'est comme réaliser qu'avoir 1 000 caméras minuscules à vue rapide donne une meilleure image d'une foule que d'avoir seulement 200 camères géantes au ralenti.

La grande découverte du papier

L'auteur, Brian Bushnell, présente l'AVLL comme une nouvelle façon de compter les éléments uniques dans un flux de données. Il a découvert qu'en utilisant une astuce mathématique appelée "encodage arithmétique en base 56", il pouvait empaqueter 11 registres (les casiers numériques) dans un seul mot de 64 bits de la mémoire informatique. Par le passé, les méthodes standards gaspillaient des bits en essayant de faire tenir ces registres dans des emplacements fixes, mais l'AVLL utilise chaque bit, ne laissant aucun gaspillage.

Cette astuce de rangement donne à l'AVLL un avantage massif : à une taille de mémoire de 1 Ko (ce qui est minuscule en termes informatiques), l'AVLL peut stocker 1 408 registres, alors que l'ancienne méthode de pointe, appelée ExaLogLog, ne pouvait contenir que 256 registres dans le même espace. C'est un avantage de 5,5× sur le nombre d'observations que le système peut effectuer.

Le papier démontre que cette approche du "plus c'est mieux" fonctionne extrêmement bien. Dans des tests utilisant 128 000 simulations indépendantes, l'AVLL a atteint une erreur absolue moyenne pondérée par la largeur de 1,63 % à 1 Ko. En comparaison, l'ExaLogLog présentait une erreur de 1,71 %. Bien que cette différence puisse sembler infime, dans le monde du comptage de haute précision, c'est une victoire significative. L'auteur a calculé un "produit mémoire-variance" (un score de l'efficacité de l'utilisation de la mémoire) d'environ 3,4 pour l'AVLL, ce qui est inférieur (et donc meilleur) au score pratique de 3,78 de l'ExaLogLog, et bat même son meilleur score théorique de 3,67.

Accélérer le comptage

Mais l'AVLL n'est pas seulement plus précis ; il est aussi étonnamment rapide, surtout lorsque l'ordinateur est très sollicité. Le papier décrit un mécanisme appelé "sortie anticipée" (early exit). Imaginez un videur à la porte de la fête qui peut instantanément dire si un invité est quelqu'un que vous avez déjà vu, sans même regarder la liste des invités. L'AVLL fait cela en comparant le code d'un invité à une valeur de "plancher" globale. Si le code est inférieur au plancher, l'invité est ignoré immédiatement, et le système ne touche même pas à la mémoire où sont stockés les casiers.

Dans des tests où des milliers de ces systèmes de comptage fonctionnaient simultanément (simulant un cache informatique encombré), l'AVLL était 2,7 à 4,5 fois plus rapide que l'ExaLogLog. Cela s'explique par le fait que l'ExaLogLog doit vérifier sa mémoire pour chaque article, même s'il s'agit d'un doublon, tandis que l'AVLL filtre la grande majorité des doublons avant qu'ils n'atteignent les registres. À des nombres élevés d'éléments uniques, l'AVLL rejette environ 96 % des données entrantes sans toucher aux registres, permettant au système de fonctionner de manière fluide.

Ce que cela signifie (et ce que cela ne signifie pas)

Le papier écarte explicitement l'idée que des registres "plus riches" (comme les casiers de 32 bits de l'ExaLogLog qui stockent un historique détaillé) sont toujours meilleurs. Les résultats suggèrent que pour ce type spécifique de problème de comptage, avoir plus d'observations indépendantes (plus de registres) est plus précieux que d'avoir des données plus riches par observation.

Cependant, l'auteur note prudemment que l'AVLL n'est pas "idempotent" au sens strict du terme. Cela signifie que si vous injectez deux fois exactement les mêmes données dupliquées dans le système, il pourrait se comporter légèrement différemment que si vous ne les injectiez qu'une seule fois, bien que le papier montre que dans des tests pratiques avec de fortes duplications, l'exactitude n'a pas diminué. Ils admettent également que leur estimateur "HLDLC" est un mélange ingénieux de différentes formules mathématiques trouvées grâce à des simulations massives, plutôt qu'une solution mathématiquement "parfaite" comme l'estimateur de maximum de vraisemblance de l'ExaLogLog.

Le papier conclut que l'AVLL est un outil autonome (écrit sous la forme d'une classe Java unique) qui est prêt à l'emploi. Il gère des quantités massives de données sans manquer d'espace mémoire pour le compteur lui-même, et il fonctionne aussi bien que les données soient un mélange chaotique d'éléments uniques ou un flux répétitif de doublons. Le message central est un changement de philosophie : dans la bataille de l'efficacité de la mémoire, la densité l'emporte sur la richesse. En empaquetant plus de compteurs simples et indépendants dans le même espace, on obtient une image plus claire, plus rapide et plus précise du flux de données.

Résumé Technique : Arithmetic Variable LogLog (AVLL)

Énoncé du Problème

L'estimation de la cardinalité — la tâche consistant à compter les éléments distincts dans un flux de données avec une mémoire limitée — nécessite un compromis fondamental entre l'utilisation de la mémoire et la précision de l'estimation. Bien que HyperLogLog (HLL) soit depuis longtemps la référence pratique, des avancées récentes comme ExaLogLog ont repoussé la frontière de la mémoire-variance en augmentant la densité d'information par registre (en utilisant des registres à largeur variable et un codage large, ainsi qu'une estimation de maximum de vraisemblance). Cependant, ces approches souffrent souvent d'un faible nombre de registres par octet, ce qui limite l'indépendance statistique des observations. À l'inverse, les méthodes de compaction architecturale comme DynamicLogLog (DLL) augmentent la densité des registres mais manquaient historiquement de la profondeur d'information par registre des estimateurs plus riches. Le défi est de déterminer si maximiser le nombre de registres indépendants ou maximiser l'information par registre produit une meilleure précision sous un budget mémoire fixe.

Méthodologie

Le document présente l'Arithmetic Variable LogLog (AVLL), un nouvel estimateur qui privilégie la densité des registres grâce au codage arithmétique et à un pipeline d'estimation hybride.

1. Codage Arithmétique des Registres

Contrairement aux variantes traditionnelles de LogLog qui utilisent des créneaux de bits à largeur fixe (par exemple, des registres de 6 ou 8 bits), l'AVLL utilise un codage arithmétique en base 56.

Espace d'états : Chaque registre encode 56 états distincts, comprenant un exposant NLZ (Number of Leading Zeros - nombre de zéros initiaux) et un motif d'historique sub-NLZ de 2 bits.
Compactage : Puisque $56^{11} < 2^{64}$ , l'AVLL emballe 11 registres dans un seul mot de 64 bits sans aucun bit gaspillé. Cela résulte en une largeur de registre d'environ 5,82 bits.
Comparaison : Pour un budget mémoire de 2 Ko, l'AVLL stocke 2 816 registres, tandis qu'ExaLogLog (utilisant des registres de 32 bits) n'en stocke que 512. Cela offre un avantage de 5,5× sur le nombre de registres.
Accès : L'accès aux registres nécessite des opérations de division et de reste sur des entiers non signés de 64 bits (Long.divideUnsigned, Long.remainderUnsigned), qui sont plus coûteuses en calcul que le masquage de bits à largeur fixe, mais qui sont amorties par le mécanisme de sortie anticipée de l'estimateur.

2. Architecture et Mise à l'Échelle

Exposant Partagé (Plancher Global) : L'AVLL stocke les valeurs NLZ relatives par rapport à un plancher global (globalNLZ), de manière similaire à DynamicLogLog. Cela permet au coût de la mémoire de passer à une échelle de $O(B + \log \log C)$ plutôt que $O(B \times \log \log C)$ , isolant ainsi efficacement la cardinalité maximale représentable de la largeur du registre.
Sortie Anticipée (Early Exit) : Les éléments dont les valeurs de hachage sont inférieures au plancher global actuel sont rejetés immédiatement sans toucher à la mémoire des registres. À haute cardinalité, cela rejette plus de 99 % des éléments, réduisant considérablement l'utilisation de la bande passante mémoire.
Support de Fusion (Merge) : L'AVLL supporte la fusion de registres par déballage, l'exécution d'opérations OR bit à bit sur leurs représentations de bitmap, puis le re-compactage.

3. L'Estimateur HLDLC

L'AVLL utilise un estimateur Hybrid Layered DLC (HLDLC), un cadre hybride à quatre composants conçu pour minimiser le biais sur toute la plage de cardinalité :

LDLC (Layered DLC) : Un mélange de DLC (Dynamic Linear Counting) et de SBS (State Bias Sum) pour les cardinalités faibles à moyennes, combiné avec HC (History Counting) pour la haute cardinalité.
Hybrid+2 : Un mélange de SBS et de Mean+H (une nouvelle moyenne harmonique corrigée par l'historique).
Stratégie de Mélange : L'estimation finale est un mélange 50/50 de LDLC et de Hybrid+2. Cette annulation de biais complémentaire réduit l'erreur en dessous de celle de n'importe quel composant individuel.
Composants :
- SBS : Exploite des motifs d'historique spécifiques de 2 bits pour l'estimation de faible cardinalité.
- DLC : Une extension sensible aux paliers du Linear Counting qui élimine les artefacts de transition.
- HC : Utilise les bits d'historique aux limites de paliers pour estimer la haute cardinalité.
- Mean+H : Un estimateur de moyenne harmonique corrigé par les motifs d'historique sub-NLZ.
Implémentation : Toutes les formules de correction sont intégrées sous la forme d'environ 100 constantes statiques dans une seule classe Java, ne nécessitant ni tables externes ni dépendances au moment de l'exécution.

Principales Contributions

Codage Arithmétique : Démontre la faisabilité pratique du codage arithmétique en base 56, permettant d'emballer 11 registres par mot de 64 bits sans perte de bits.
Estimateur HLDLC : Introduit un estimateur hybride à quatre composants qui atteint une précision record sans résolution itérative (contrairement à l'approche de maximum de vraisemblance d'ExaLogLog).
Précision Record : Atteint une erreur absolue moyenne (MAE) pondérée par la largeur de 1,63 % à 1 Ko, surpassant ExaLogLog (1,71 %) de 4,7 %. Le produit mémoire-variance (MVP) empirique est d'environ 3,4, ce qui est inférieur au MVP de 3,78 d'ExaLogLog et à son optimum théorique de 3,67, bien que le document note qu'il s'agit d'une observation empirique et non d'une borne théorique prouvée.
Vitesse de Déploiement : Sous pression de cache (milliers de sketches simultanés), l'AVLL est 2,7 à 4,5 fois plus rapide qu'ExaLogLog grâce au mécanisme de sortie anticipée qui filtre la plupart des éléments avant l'accès au registre.
Cardinalité Illimitée : L'architecture à plancher glissant supprime le plafond imposé par la largeur du registre, supportant des cardinalités allant jusqu'à la limite de la largeur de hachage (ex: $2^{256}$ ) avec un surcoût de mémoire quasi constant.
Robustesse : Maintient sa précision sous des distributions de données à faible complexité (duplications élevées) avec une dégradation nulle, malgré l'utilisation d'une promotion de palier non-idempotente.

Résultats Expérimentaux

Précision : L'AVLL surpasse ExaLogLog et sept autres estimateurs (incluant HLL-TailCut4, UltraLogLog et Apache HLL4) à chaque point de mémoire testé (de 0,25 Ko à 4 Ko) sous des conditions de haute complexité (tous uniques) et de faible complexité (duplication biaisée).
Débit :
- Limité par l'ALU : L'AVLL égale le débit d'ExaLogLog (~14 681 vs 13 801 millions d'ajouts/s) lorsque les sketches tiennent en cache.
- Limité par la bande passante mémoire : Sous une pression extrême de cache (sim=4 096), l'AVLL atteint 4 360 millions d'ajouts/s contre 1 609 millions d'ajouts/s pour ExaLogLog (un avantage de 2,7×).
- Échelle de Cardinalité : Le débit de l'AVLL augmente de 177 % lorsque la cardinalité du flux passe de 5M à 80M, alors qu'ExaLogLog reste plat, élargissant l'écart de vitesse à 9,7× à haute cardinalité.
Efficacité de la Mémoire : L'AVLL atteint le plus bas MVP empirique (~3,4) démontré à ce jour, battant le MVP pratique d'ExaLogLog (3,78) et son optimum théorique (3,67).

Signification et Revendications

Le document pose un principe de conception central : « La densité bat la richesse. » Pour les estimateurs de la famille LogLog, maximiser le nombre d'observations de hachage indépendantes (nombre de registres) produit souvent une meilleure précision que de maximiser le contenu d'information par registre, à condition que l'estimateur soit suffisamment sophistiqué pour extraire l'information d'un codage plus simple.

L'auteur affirme que l'AVLL représente un nouvel état de l'art en :

Surpassant la performance empirique des estimateurs à registres fixes (ExaLogLog) via le compactage arithmétique et un estimateur hybride, atteignant un MVP inférieur à l'optimum théorique d'ExaLogLog (bien que le document précise qu'il s'agit d'un résultat empirique et non d'une preuve de l'optimalité du codage de l'AVLL).
Résolvant le compromis vitesse-précision dans les scénarios de déploiement en utilisant la sortie anticipée pour minimiser l'utilisation de la bande passante mémoire.
Supprimant le plafond de cardinalité inhérent aux schémas de registres à largeur fixe.

Le document reconnaît que l'AVLL n'est pas strictement idempotent (en raison de la promotion de palier) et que l'accès aux registres implique un surcoût de division. Cependant, il soutient que ces limitations sont négligeables dans les applications de streaming à haute cardinalité où la sortie anticipée domine, et que les gains de précision sont robustes à travers diverses distributions de données. L'implémentation est fournie sous la forme d'une classe Java autonome au sein de la suite BBTools.