Resumo Técnico: Arithmetic Variable LogLog (AVLL)

Declaração do Problema

A estimativa de cardinalidade — a tarefa de contar elementos distintos em um fluxo de dados usando memória limitada — exige um compromisso fundamental entre o uso de memória e a precisão da estimativa. Embora o HyperLogLog (HLL) tenha sido, por muito tempo, o padrão prático de excelência, avanços recentes como o ExaLogLog expandiram a fronteira de memória-variância ao aumentar a densidade de informação por registrador (usando registradores de largura variável e ampla e estimativa de máxima verossimilhança). No entanto, essas abordagens frequentemente sofrem com uma baixa contagem de registradores por byte, limitando a independência estatística das observações. Por outro lado, métodos de compactação arquitetural como o DynamicLogLog (DLL) aumentam a densidade de registradores, mas historicamente careceram da profundidade de informação por registrador dos estimadores mais ricos. O desafio é determinar se maximizar o número de registradores independentes ou maximizar a informação por registrador produz melhor precisão sob um orçamento de memória fixo.

Metodologia

O artigo introduz o Arithmetic Variable LogLog (AVLL), um novo estimador que prioriza a densidade de registradores através de codificação aritmética e um pipeline de estimativa híbrido.

1. Codificação Aritmética de Registradores

Ao contrário dos variantes tradicionais de LogLog que usam slots de bits de largura fixa (ex: 6 ou 8 bits), o AVLL utiliza codificação aritmética de base-56.

• Espaço de Estados: Cada registrador codifica 56 estados distintos, consistindo em um expoente NLZ (Número de Zeros à Esquerda) e um padrão de histórico sub-NLZ de 2 bits.
• Empacotamento: Como $56^{11} < 2^{64}$, o AVLL empacota 11 registradores em uma única palavra de 64 bits com zero bits desperdiçados. Isso resulta em uma largura de registrador de aproximadamente 5,82 bits.
• Comparação: Em um orçamento de memória de 2 KB, o AVLL armazena 2.816 registradores, enquanto o ExaLogLog (usando registradores de 32 bits) armazena apenas 512. Isso resulta em uma vantagem de 5,5× na contagem de registradores.
• Acesso: O acesso ao registrador requer operações de divisão e resto de 64 bits sem sinal (Long.divideUnsigned, Long.remainderUnsigned), que são computacionalmente mais caras do que o mascaramento de bits de largura fixa, mas são amortizadas pelo mecanismo de saída antecipada (early exit) do estimador.

2. Arquitetura e Escalonamento

• Expoente Compartilhado (Piso Global): O AVLL armazena valores de NLZ relativos a um piso global (globalNLZ), de forma semelhante ao DynamicLogLog. Isso permite que o custo de memória escale como $O(B + \log \log C)$ em vez de $O(B \times \log \log C)$, efetivamente desacoplando a cardinalidade máxima representável da largura do registrador.
• Saída Antecipada (Early Exit): Elementos com valores de hash abaixo do piso global atual são rejeitados imediatamente sem tocar na memória do registrador. Em altas cardinalidades, isso rejeita >99% dos elementos, reduzindo drasticamente o uso de largura de banda de memória.
• Suporte à Fusão (Merge): O AVLL suporta a fusão de registradores através do desempacotamento dos registradores, realização de operações bitwise OR em suas representações de bitmap e repacotamento.

3. O Estimador HLDLC

O AVLL utiliza um estimador Hybrid Layered DLC (HLDLC), um framework de quatro componentes misturados projetado para minimizar o viés em toda a faixa de cardinalidade:

• LDLC (Layered DLC): Uma mistura de DLC (Dynamic Linear Counting) e SBS (State Bias Sum) para cardinalidade baixa a média, combinada com HC (History Counting) para alta cardinalidade.
• Hybrid+2: Uma mistura de SBS e Mean+H (uma nova média harmônica corrigida por histórico).
• Estratégia de Mistura: A estimativa final é uma mistura de 50/50 entre LDLC e Hybrid+2. Esse cancelamento de viés complementar reduz o erro abaixo de qualquer componente individual.
• Componentes:
  • SBS: Explora padrões específicos de histórico de 2 bits para estimativa de baixa cardinalidade.
  • DLC: Uma extensão de nível (tier-aware) do Linear Counting que elimina artefatos de transição.
  • HC: Utiliza bits de histórico em fronteiras de níveis para estimar alta cardinalidade.
  • Mean+H: Um estimador de média harmônica corrigido para padrões de histórico sub-NLZ.
• Implementação: Todas as fórmulas de correção estão incorporadas como aproximadamente 100 constantes estáticas em uma única classe Java, não exigindo tabelas externas ou dependências de tempo de execução.

Principais Contribuições

1. Codificação Aritmética: Demonstra a praticidade da codificação aritmética de base-56, alcançando 11 registradores por palavra de 64 bits com zero desperdício de bits.
2. Estimador HLDLC: Introduz um estimador de quatro componentes misturados que alcança precisão recorde sem solução iterativa (ao contrário da abordagem de Máxima Verossimilhança do ExaLogLog).
3. Precisão Recorde: Alcança um erro absoluto médio (MAE) ponderado pela largura de 1,63% em 1 KB, superando o ExaLogLog (1,71%) em 4,7%. O produto memória-variância (MVP) empírico é de ~3,4, que é inferior ao MVP prático do ExaLogLog (3,78) e seu ótimo teórico (3,67), embora o artigo note que esta é uma observação empírica e não um limite teórico provado.
4. Velocidade de Implantação: Sob pressão de cache (milhares de sketches simultâneos), o AVLL é 2,7–4,5× mais rápido que o ExaLogLog devido ao mecanismo de saída antecipada que filtra a maioria dos elementos antes do acesso ao registrador.
5. Cardinalidade Ilimitada: A arquitetura de piso deslizante remove o teto imposto pela largura do registrador, suportando cardinalidades de até o limite da largura do hash (ex: $2^{256}$) com overhead de memória quase constante.
6. Robustez: Mantém a precisão sob distribuições de dados de baixa complexidade (altamente duplicadas) com zero degradação, apesar de usar promoção de nível não idempotente.

Resultados Experimentais

• Precisão: O AVLL supera o ExaLogLog e outros sete estimadores (incluindo HLL-TailCut4, UltraLogLog e Apache HLL4) em todos os pontos de memória testados (0,25 KB a 4 KB) sob condições de alta complexidade (todos únicos) e baixa complexidade (duplicação enviesada).
• Vazão (Throughput):
  • Limitado por ALU: O AVLL iguala a vazão do ExaLogLog (~14.681 vs 13.801 milhões de adições/s) quando os sketches cabem no cache.
  • Limitado por Largura de Banda de Memória: Sob pressão extrema de cache (sim=4.096), o AVLL atinge 4.360 milhões de adições/s comparado aos 1.609 milhões de adições/s do ExaLogLog (uma vantagem de 2,7×).
  • Escalonamento de Cardinalidade: A vazão do AVLL aumenta em 177% conforme a cardinalidade do fluxo cresce de 5M para 80M, enquanto o ExaLogLog permanece estável, ampliando a lacuna de velocidade para 9,7× em alta cardinalidade.
• Eficiência de Memória: O AVLL alcança o menor MVP empírico (~3,4) demonstrado até o momento, superando o MVP prático do ExaLogLog (3,78) e seu ótimo teórico (3,67).

Significância e Alegações

O artigo propõe um princípio central de design: "Densidade vence riqueza". Para estimadores da família LogLog, maximizar o número de observações de hash independentes (contagem de registradores) frequentemente produz melhor precisão do que maximizar o conteúdo de informação por registrador, desde que o estimador seja sofisticado o suficiente para extrair informação de uma codificação mais simples.

O autor afirma que o AVLL representa um novo estado da arte ao:

1. Superar o desempenho empírico de estimadores de registro fixo (ExaLogLog) através de empacotamento aritmético e um estimador misto, alcançando um MVP inferior ao ótimo teórico do ExaLogLog (embora o artigo esclareça que este é um resultado empírico, não uma prova teórica de otimalidade para a codificação do AVLL).
2. Resolver o compromisso velocidade-precisão em cenários de implantação ao utilizar a saída antecipada para minimizar o uso de largura de banda de memória.
3. Remover o teto de cardinalidade inerente aos esquemas de largura de registrador fixa.

O artigo reconhece que o AVLL não é estritamente idempotente (devido à promoção de nível) e que o acesso ao seu registrador envolve sobrecarga de divisão. No entanto, argumenta que essas limitações são negligenciáveis em aplicações de streaming de alta cardinalidade onde a saída antecipada domina, e que os ganhos de precisão são robustos através de diversas distribuições de dados. A implementação é fornecida como uma classe Java autossuficiente dentro da suíte BBTools.