Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Aleatoriedade no Coração dos Algoritmos do Futuro

Juan Lopes
March 29, 2016

Aleatoriedade no Coração dos Algoritmos do Futuro

Juan Lopes

March 29, 2016

Transcript

81 slides
  1. • PAI DO MIGUEL • BACHAREL E QUASE MESTRE •

    PROGRAMADOR • VICIADO EM COMPETIÇÕES QUEM É JUAN LOPES?
  2. • HASHTABLES • GERAÇÃO DE PARES DE CHAVES CRIPTOGRÁFICAS •

    RANDOMIZED QUICKSORT ALGORITMOS RANDOMIZADOS
  3. A OPINIÃO DE UM INDIVÍDUO ALEATÓRIO EM UMA POPULAÇÃO É

    UM ESTIMADOR DA OPINIÃO DA POPULAÇÃO
  4. A QUANTIDADE DE PESSOAS EM UM TRECHO DE UMA MANIFESTAÇÃO

    É UM ESTIMADOR DO NÚMERO TOTAL DE PESSOAS
  5. • FILTRO DE BLOOM [Blo70] • CM-SKETCH [CM05] • MINHASH

    [Bro97] • HYPERLOGLOG [FFGM08] ESTRUTURAS PROBABILÍSTICAS
  6. 1970 1990 1980 2000 2010 LINHA DO TEMPO FILTRO DE

    BLOOM [Blo70] FM-SKETCH [FM85] MINHASH [Bro97] KMV-SKETCH [BYJK+02] LSH THEORY [IM98] SIMHASH [Cha02] LOGLOG [DF03] AMS PAPER [AMS96] CM-SKETCH [CM05] HYPERLOGLOG [FFGM08] SPECTRAL BLOOM [CM03]
  7. MINHASH [Bro97] Andrei Z Broder. On the resemblance and containment

    of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21–29. IEEE, 1997.
  8. MINHASH • CADA FUNÇÃO DEFINE UM ESTIMADOR NÃO-ENVIESADO • MÚLTIPLAS

    FUNÇÕES DE HASH • COMPARAÇÃO DOS VALORES DE CADA ASSINATURA
  9. MINHASH • ASSINATURA DEFINIDA POR K MENORES VALORES • TAMBÉM

    É VARIÁVEL DE BERNOULLI • COMPARAÇÃO DOS VALORES DE CADA ASSINATURA
  10. MINHASH S 1 S 2 S 3 S 4 S

    5 h 1 h 2 h 3 h 4 h 5 h 6 h 7 h 8
  11. MINHASH S 1 S 2 S 3 S 4 S

    5 h 1 h 2 h 3 h 4 h 5 h 6 h 7 h 8 r=2 }
  12. MINHASH S 1 S 2 S 3 S 4 S

    5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 }r=2 { b=4
  13. MINHASH S 1 S 2 S 3 S 4 S

    5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 1 S 4
  14. MINHASH S 1 S 2 S 3 S 4 S

    5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 2 S 5 S 1 S 4
  15. MINHASH S 1 S 2 S 3 S 4 S

    5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 2 S 5 S 2 S 5 S 1 S 4
  16. MINHASH S 1 S 2 S 3 S 4 S

    5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 1 S 4 S 2 S 5 S 2 S 5 S 2 S 5 S 2 S 5 S 2 S 5 S 1 S 4
  17. MINHASH S 1 S 2 S 3 S 4 S

    5 r 1 h 1 h 2 r 2 h 3 h 4 r 3 h 5 h 6 r 4 h 7 h 8 S 1 S 4 S 2 S 5 S 2 S 5 S 2 S 5 S 1 S 4 S 2 S 5 S 2 S 5 S 1 S 4
  18. SIMHASH • FUNÇÃO DE HASH DEFINIDA POR VETOR ALEATÓRIO •

    ESTIMATIVA DO MENOR ÂNGULO ENTRE DOIS VETORES
  19. HYPERLOGLOG [FFGM08] Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric

    Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. DMTCS Proceedings, (1), 2008.
  20. HYPERLOGLOG C 0 0 0 5 0 0 1 0

    01000001 CADA POSIÇÃO NESTE ARRAY DE EXEMPLO USA APENAS 3 BITS
  21. HYPERLOGLOG • SE O VALOR ESTIMADO FOR MUITO BAIXO (<2.5M),

    USA- SE LINEAR COUNTING NO MESMO VETOR • A ESTIMATIVA TEM UM VIÉS MULTIPLICATIVO CONSTANTE QUE PRECISA SER CORRIGIDO
  22. • SÃO MUITO IMPORTANTES QUANDO HÁ RESTRIÇÃO DE RECURSOS •

    ÁREA DE PESQUISA RECENTE • ATRAI MUITO INTERESSE DOS BIG PLAYERS • IMPLEMENTAR É MAIS SIMPLES QUE EXPLICAR ESTRUTURAS PROBABILÍSTICAS

More Decks by Juan Lopes

Other Decks in Technology