Por que algoritmos diferentes?
Dados massivos não cabem na memória principal de uma máquina. O custo dominante passa a ser leitura em disco e comunicação em rede, não só operações de CPU. Por isso surgem três modelos clássicos: distribuído (vários nós), streaming (dados passam uma vez) e memória externa (minimizar acessos ao disco). Muitas vezes troca-se exatidão por respostas aproximadas com garantia probabilística.
Contar visitantes distintos de um portal com bilhões de acessos diários usando poucos kilobytes de memória, aceitando pequeno erro.
MapReduce: map, shuffle, reduce
MapReduce divide o trabalho em fases. Map lê blocos de entrada e emite pares chave-valor. Shuffle/sort agrupa todos os valores de uma mesma chave e os envia ao mesmo reducer. Reduce agrega os valores de cada chave. O combiner é um reduce local opcional, aplicado após o map para diminuir o tráfego de rede.
Contagem de palavras: map emite (palavra, 1); reduce soma os 1 de cada palavra.
Streaming e amostragem
No modelo de streaming, os itens chegam em sequência e são lidos em uma única passagem (ou poucas). A memória usada deve ser sublinear em relação ao tamanho do fluxo. A amostragem por reservatório mantém uma amostra uniforme de k itens sem saber de antemão quantos itens virão: o item de posição i substitui um elemento do reservatório com probabilidade k/i.
Manter 1.000 tweets aleatórios de um fluxo contínuo cujo total é desconhecido.
Na plataforma, cada ideia vem com uma pergunta de checagem, flashcards para revisar e questões da banca.