+
+
Dados Armazenados vs. Fluxos
Mineração de Fluxos (Streams)
Modelo de Fluxos
Técnicas de Amostragem
Janelas Deslizantes
Contadores de 1
Contagem de Elementos Distintos
2
n  Em
um SGBD, os dados de entrada estão sob o
controle do programador
n  A
gerência de fluxos é necessária quando a taxa
de entradas dos dados é controlada externamente
n 
Consultas em uma máquina de busca, post no Twitter ou
Facebook
n  Podemos
imaginar os dados como infinitos e nãoestacionários (a distribuição dos dados muda com
o tempo)
Gerência de Dados na Web Edição Big Data 2013-02
Prof. Altigran Soares da Silva
Baseado nos Slides do Professor Jeffrey Ullman
1
+
O Modelo de Fluxos
n Registros
são recebidas a uma taxa rápida
de uma ou mais portas
n O
sistema não tem capacidade de
armazenar o fluxo inteiro
n Como
fazer analises sobre o fluxo usando
uma quantidade limitada de memoria?
Consultas
Ad-Hoc
3
. . . 1, 5, 2, 7, 0, 9, 3
. . . a, r, v, t, y, h, b
. . . 0, 0, 1, 0, 1, 1, 0
tempo
4
Consultas
Permanentes
Processador
Entrada dos Fluxos
Memória
Limitada
Arquivamento
+
Problemas sobre Fluxos (1)
5
n Gerar
uma amostra aleatória dos
dados de um fluxo
n Consultas
n Contagem
n Estimativa
de itens de um certo tipo que
ocorreram entres os últimos k elementos
do fluxo
Estimar a média ou desvio padrão dos
últimos k elementos
em fluxos de dados:
n Encontrar
n  Quais
consultas são mais frequentes hoje que
ontem
n Mineração
de fluxos de click:
n  Que
páginas tiveram um número não-usual de
acessos na última hora
n Detecção
de tópicos emergentes em posts
de redes sociais
elementos frequentes no
fluxo
Selecionar os elementos que tem uma
certa propriedade em um fluxo
de fluxos de consultas:
de Momentos (Estatística):
n 
n 
n Mineração
de elementos distintos
Número de elementos distintos nos
últimos k elementos
sobre janelas deslizantes:
+
Aplicações (1)
6
n 
n Número
n Filtragem
+
Problemas sobre Fluxos (2)
7
+
Aplicações (2)
n Monitoramento
de sensores
n Geração
de contas de telefone a partir de
registros de chamada
n Monitoramento
de pacotes IP para
detecção de ataques
8
+
Amostragem de Fluxos (1)
9
Amostra de Proporção Fixa:
n  Amostrar uma proporção fixa dos elementos
em um fluxo, por exemplo, 1 em 10
n  (2) Amostra de Tamanho Fixo:
n  Manter uma amostra aleatória de tamanho fixo
sobre um fluxo potencialmente infinito
n  A cada “tempo” k, gostaríamos de ter uma
amostra aleatória de s elementos
n  Para todos os intervalos k, cada um dos k
elementos encontrados até o momento tem
igual probabilidade de estar na amostra
não se pode armazenar o fluxo
inteiro, uma abordagem óbvia é armazenar
uma amostra
problemas distintos:
n  Amostra
de Proporção Fixa
n  Amostra de Tamanho Fixo
+
Amostra de Proporção Fixa (1)
n  Cenário: Fluxo
busca
n  Fluxo
de consultas em uma máquina de
11
+
Amostra de Proporção Fixa (2)
n Solução
Naïve
n  Gerar
de registros: (usuário, consulta, tempo)
n  Responder
questões como: Qual a frequência com
que um usuário executa a mesma consulta em um
dado dia?
n  Assume-se
que há espaço para armazenar 1/10
das consultas
10
n  (1)
n Como
n Dois
+
Amostragem de Fluxos (2)
uma inteiro aleatório entre 0 e 9 para cada
consulta
n  Armazenar a consulta se o inteiro é 0. Caso
contrário, descarta.
n Essa
solução traz problemas
12
+
Problema com a Solução Naïve
13
+
Problema com a Solução Naïve
n  Solução
n Questão
simples: que fração das consultas
são duplicadas?
n  A
n  Suponha
que nenhuma consulta ocorre mais de
duas vezes
n  Assim:
n 
n Resposta: d/(s+d)
s/10 + d/100 + 18d/100 = 10s+19d/100
n  Fração
n 
15
de duplicados seria
(d/100) ÷ (10s+19d/100) = d/(10s+19d)
+
Solução Geral
n 
n Tomar
1/10 usuários e usar todas as
suas consultas na amostra
uma função de hashing que
mapeia o nome do usuário ou o seu ID
em um 10 posições de maneira
uniforme.
amostra conterá:
s/10 das consultas únicas e d/100 pares duplicados,
n  pois d/100 = 1/10 x 1/10 x d
n  18d/100 consultas únicas de pares duplicados
n  pois 18d/100 = ((1/10 x 9/10) + (9/10 x 1/10)) x d
que cada usuário faz s consultas
uma vez e d consultas duas vezes
n Usar
proposta: manter 10% das consultas
n 
n Suponha
+
Alternativa: Amostra por Usuários
14
Fluxo de registros com Chaves
n 
n 
n 
A chave é formada por um subconjunto dos campos do registro
n 
Ex: Registro = (usuário, consulta, tempo)
n 
Chave: usuário, consulta, usuário + consulta
Para obter uma amostra de uma fração a/b do fluxo:
n 
Mapear a chaves uniformemente em uma tabela hashing de b posições
n 
Selecionar o registro para a amostra se seu valor de hashing é no máximo a
Exemplo: como gerar uma amostra de 30%?
n 
Usar um hash de 10 posições
n 
Selecionar o registro se ele é mapeado para as 3 primeiras posições da
tabela
16
+
Amostra de Tamanho Fixo
n 
17
Suponha que precisamos manter uma amostra aleatória S de
exatamente s registros
n 
n  Algoritmo
Por exemplo, devido a restrições de memória
n  Exemplo: s=2
Fluxo: a x c y z k c d e g...
n  Quando n=5, cada um dos primeiros 5 elementos é
incluído na amostra com igual probabilidade
n  Quando n=7, cada um dos primeiros 7 elementos é
incluído na amostra com igual probabilidade
n  Solução: Armazenar todos n elementos vistos até o
momento e selecionar s elementos aleatoriamente Impraticável
n 
+
Janelas Deslizantes
n Um
de interesse: N é tão grande que não
cabe na memória ou nem mesmo no disco.
n  Ou, existem
tantos fluxos que as janelas para todos
eles não podem ser armazenadas.
18
Amostragem Reservoir
n 
Guarde os primeiros s elementos do Fluxo S
n 
Suponha que n-1 elementos foram vistos e agora o n-ésimo
elemento chega (n>s)
n 
Com probabilidade s/n, selecione o n-ésimo elemento, senão
descarte
Se o n-ésimo elemento foi selecionado, então ele substitui um dos
s elementos da amostra S, escolhido uniformemente de forma
aleatória
n 
n  Para
um valor adequado de s realiza uma
amostragem aleatória uniforme e, assim,
selecionar uma amostra com as principais
características do fluxo.
19
modelo útil para processar fluxos é
considerar que processamento será feito sobre
uma janela de tamanho N – os N elementos
recebidos mais recentemente
n Caso
+
Amostra de Tamanho Fixo (2)
20
Janela deslizante de tamanho 6 sobre um fluxo
qwertyuiopasdfghjklzxcvbnm
qwertyuiopasdfghjklzxcvbnm
qwertyuiopasdfghjklzxcvbnm
qwertyuiopasdfghjklzxcvbnm
Passado
Futuro
+
Contagem de Bits (1)
21
n Problema: Seja
um fluxo de 0 e1,
responder consultas da forma
“quantos 1 existem nos últimos k
bits?” onde k ≤ N.
+
Contagem de Bits – (2)
n Não
é possível obter a resposta exata
sem armazenar a janela inteira
n Problema
Real: E se não pudermos
armazenar os N bits?
n Solução
Óbvia: Armazenar os N bits
mais recentes.
n Ex., estamos
processando 1 bilhão de
fluxos e N = 1 bilhão
n Quando
um novo bit chegar no fluxo,
descartar o N +1º. bit.
+
Solução Simples (e pouco eficaz)
n Estaremos
satisfeitos com uma resposta
aproximada
23
+
Exemplo
n 
regiões exponencialmente
crescentes do fluxo, olhando para o
passado
22
n Sumarizar
Armazenar somente informação das regiões
n 
Posição no Fluxo e número de Bits
n 
Construir o contador nos últimos N bits a partir desta
informações
n 
Não se sabe quantos dos últimos 6 não estão incluídos
n Remover
regiões pequenas se elas
começam no mesmo ponto que
regiões maiores
24
+
Vantagens
n Armazena
n O(log
25
apenas O(log2N ) bits.
+
Desvantagens
n Se
a ocorrência de “1” é igualmente
distribuída, o erro devido à região
desconhecida é pequeno – não maior
que 50%
N ) contadores de log2N bits cada.
n Fácil
de atualizar quando mais bits
chegam
n Mas
pode ser que todos os “1”
estejam justamente no fim da zona
desconhecida
n Erro
é menor que o número de “1” na
área desconhecida.
n Neste
+
Soluções
n  Ao
invés de sumarizar blocos com
comprimento fixo, sumarizar blocos
com número específico de “1”
n Quando
existirem poucos “1” na
janela, o tamanho dos blocos continua
pequeno e assim o erro é pequeno.
26
27
caso o erro é ilimitado
+
Método DGIM*
n Armazena
O(log2N ) bits por fluxo.
n Provê
resultado aproximado com erro
menor que 50%.
n O
fator de erro pode ser reduzido para
qualquer fração < 0, com sofisticações
sobre o algoritmo e proporcionalmente
mais bits armazenados.
*Datar,
Gionis, Indyk, and Motwani
28
+
Timestamps
29
n Cada
bit no fluxo tem um timestamp,
começando em 1, 2, …
+
Buckets
n 
Um bucket é um registro que
consiste de :
1. 
n São
armazenados dos valores de
timestamps modulo N (tamanho da
janala).
2. 
n 
n Assim, é
possível representar qualquer
timestamp relevante com O(log2N ) bits.
31
Timestamp do seu final [O(log N ) bits].
O número de “1” entre seu inicio e fim
[O(log log N ) bits].
Restrição: O número de “1” deve ser
uma potência de 2.
n 
+
Representação do Fluxo
30
Por isso log log N
+
Exemplo:
32
n Existem
um ou dois buckets com o mesmo
número de “1” em potência de dois.
n Sobre
os buckets
n  Não
se sobrepõem nos timestamps.
n  São ordenados pelo tamanho.
n  Buckets mais velhos não são menores que os
mais novos
n Desaparecem
quando o seu tempo de fim é
> N unidades de tempo no passado
Pelo menos 1 de tam 16
Parcialmente além da janela
2 de tam. 8
2 de tam 4
1 de
tam 2
2 de
tam 1
1001010110001011010101010101011010101010101110101010111010100010110010
N
+
Atualizando Buckets (1)
33
n  Se
n Quando
um novo bit chega, removese o último bucket (+velho) se seu
tempo de fim é anterior a N unidades
de tempo antes do tempo atual.
1. 
2. 
3. 
n Se
o bit corrente é 0, não há
alterações.
+
Exemplo 1
+
Atualizando Buckets (2)
4. 
35
1001010110001011010101010101011010101010101110101010111010100010110010
0010101100010110101010101010110101010101011101010101110101000101100101
34
o bit corrente é 1:
Cria-se um novo bucket de tamanho 1 só para este
bit com timestamp de fim = tempo atual
Se agora existem 3 buckets de tamanho 1, combinar
os 2 mais antigos em um bucket de tamanho 2.
Se agora existem 3 buckets de tamanho 2, combinar
os 2 mais antigos em um bucket de tamanho 4.
E assim por diante ...
+
Exemplo 2
36
0101100010110101010101010110101010101011101010101110101000101100101101
0101100010110101010101010110101010101011101010101110101000101100101101
.....
0010101100010110101010101010110101010101011101010101110101000101100101
0101100010110101010101010110101010101011101010101110101000101100101101
+
Consulta
37
+
Estimativa de Erro
n Suponha
Para estimar o número de “1” no N
bits mais recentes:
n 
1. 
2. 
n 
possível usar o mesmo truque para
responder um consulta do tipo
“Quantos “1” existem nos últimos k
bits?” onde k < N ?
n É
n Então, assumindo
que 2k -1 dos seus “1”ainda
estão na janela, o erro é no máximo 2k -1.
n Como
existe pelo menos um bucket de
tamanho menor que 2k, a soma verdadeira
não é menor que 2k -1.
Lembrete: não se sabe quantos “1”
do último bucket ainda existem.
n É
possível lidar com o caso em que o
o fluxo é de inteiros, ao invés de bits,
e nós queremos a soma dos últimos k
inteiros ?
que o último bucket tenha tamanho
2k.
Somar os tamanhos de todos os
buckets, exceto o último.
Soma metade do tamanho do último
bucket.
+
Extensões
38
n Portanto, o
39
erro é menor que 50%.
+
40
Contagem de Elementos Distintos (1)
n Problema:
n Seja
um fluxo de dados cujos elementos
pertencem a conjunto de tamanho n.
n Manter um contador do nr. de elementos
distintos vistos até então.
n Abordagem
óbvia: manter o conjunto
de elementos vistos
n Por
exemplo, através de uma tabela hash
+
Aplicações
41
palavras diferentes são
encontradas entre as páginas coletadas de
um site?
n Suponha
que não dispomos de
memória para armazenar todos os
itens
n  Números
muito grandes ou muito pequenos pode
indicar páginas artificiais (spam)
n É
páginas cada cliente visita em uma
na estimativa é aceitável, mas
deve-se limitar a probabilidade de
que esse erro seja grande.
n Quantos
produtos distintos foram vendidos
na última semana?
+
Aproximação Flajolet-Martin
n  Tomar
uma função de hashing h e mapear cada
um dos n elementos para pelo menos w = log2n
bits.
n  Para
cada elemento a do fluxo, seja r(a) o
número de zeros à direita em h(a).
n  r(a) = Posição do 1º. Zero à direita
n  w=4, h(a) = 12 = 11002, r(a) = 2
r(a) visto
n  Nr. Aproximado
de elementos distintos = 2R
necessário estimar a contagem
n Erro
semana?
n  R=máximo
42
Contagem de Elementos Distintos (2)
n Quantos
n Quantas
+
43
+
Aproximação FM – Intuição (1)
n h(a)
mapeia a com igual
probabilidade para qualquer um dos
N valores
n h(a)
é uma sequência de log2 N bits,
onde uma fração de 2-r de todos os a
tem um sufixo de r zeros
n Aprox. 50%
dos a mapeiam para ***0
n Aprox. 25% dos a mapeiam para **00
n ....
44
+
Aproximação FM – Intuição (2)
45
+
Aproximação FM – Intuição (3)
46
n Portanto, se
o maior sufixo é r=2, ou
seja, um elemento do hashing
terminando em *100, então devem
haver 4 itens distintos
P(..1) = 2-1 * N = N/2 = 8/2 = 4
P(.10) = 2-2 * N = N/4 = 8/4 = 2
P(100) = 2-3 * N = N/8 = 8/8 = 1
+
Riscos da Aproximação FM
n Quando
R cresce, o valor
2R tende
47
a∞
n A
probabilidade reduz pela metade
quando R -> R +1, mas o valor dobra.
n Para
melhorara, pode-se usar várias
funções de hashing
n Como
combinar?
n Média?
E se um dos valores é grande?
n Mediana? Os valores são potências de 2
+
Solução
n Particionar
n Tomar
48
em amostra
as médias das amostras
n Depois
tomar as medianas das médias