Manipulacao de dados multimıdia em SGBD relacionais
Profa. Dra. Maria Camila Nardini [email protected]
Centro de Matematica Computacao e Cognicao - UFABC
Santo Andre11 de julho de 2011
Maria Camila N. Barioni (UFABC) Palestra PosComp 1 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 2 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 3 / 67
Introducao
Usuário/Aplicação DBA
Compiladorde consulta
Gerenciadorde transação
CompiladorDDL
Engine de Execução
Recuperação e log
Controle de concorrência
consultas,atualizações
comandos detransações
comandosDDL
metadadosmetadados,estatísticasplano de consulta
BuffersBuffers
Execução e log concorrência
Gerenciador de re-gistro/arquivo/índice
Gerenciador de Buffer
BuffersTabela
bloqueio
requisições de registro,arquivo e índice
páginasdelog
comandos de página
escrita/leitura
dados,metadados,
índice
Gerenciador de Armazenamento
Armazena-mento
escrita/leiturapágina
estrutura em memória
componentes
fluxo de controle e dados
fluxo de dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 4 / 67
IntroducaoMotivacao
Os SGBD foram desenvolvidos para lidar com dados numericos etextuais (dados tradicionais)
Busca ⇒ baseada na propriedade de ordem total
100 < 1.000 < 10.000
A < B < C
As aplicacoes de bases de dados modernas necessitam lidar com tiposde dados complexos
Busca ⇒ baseada em similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 5 / 67
IntroducaoMotivacao
Os SGBD foram desenvolvidos para lidar com dados numericos etextuais (dados tradicionais)
Busca ⇒ baseada na propriedade de ordem total
100 < 1.000 < 10.000
A < B < C
As aplicacoes de bases de dados modernas necessitam lidar com tiposde dados complexos
Busca ⇒ baseada em similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 5 / 67
IntroducaoMotivacao
Os SGBD foram desenvolvidos para lidar com dados numericos etextuais (dados tradicionais)
Busca ⇒ baseada na propriedade de ordem total
100 < 1.000 < 10.000
A < B < C
As aplicacoes de bases de dados modernas necessitam lidar com tiposde dados complexos
Busca ⇒ baseada em similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 5 / 67
IntroducaoMotivacao
Os SGBD foram desenvolvidos para lidar com dados numericos etextuais (dados tradicionais)
Busca ⇒ baseada na propriedade de ordem total
100 < 1.000 < 10.000
A < B < C
As aplicacoes de bases de dados modernas necessitam lidar com tiposde dados complexos
Busca ⇒ baseada em similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 5 / 67
IntroducaoMotivacao
Os SGBD foram desenvolvidos para lidar com dados numericos etextuais (dados tradicionais)
Busca ⇒ baseada na propriedade de ordem total
100 < 1.000 < 10.000
A < B < C
As aplicacoes de bases de dados modernas necessitam lidar com tiposde dados complexos
Busca ⇒ baseada em similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 5 / 67
IntroducaoConsultas por Similaridade
Contribuem para a necessidade de criar um suporte para a realizacao deconsultas por similaridade em SGBDR:
O aumento da quantidade de dados de domınios complexosarmazenados em bases de dados relacionais
A integracao de metodos de mineracao de dados com SGBDR
Ponto fundamental: disponibilizacao de operacoes basicas para astecnicas de mineracao de dados existentes
ex.: deteccao de agrupamentos de dados ⇒ calculo de medidas desimilaridade entre os pares de objetos de um conjunto de dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 6 / 67
IntroducaoConsultas por Similaridade
Contribuem para a necessidade de criar um suporte para a realizacao deconsultas por similaridade em SGBDR:
O aumento da quantidade de dados de domınios complexosarmazenados em bases de dados relacionais
A integracao de metodos de mineracao de dados com SGBDR
Ponto fundamental: disponibilizacao de operacoes basicas para astecnicas de mineracao de dados existentes
ex.: deteccao de agrupamentos de dados ⇒ calculo de medidas desimilaridade entre os pares de objetos de um conjunto de dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 6 / 67
IntroducaoConsultas por Similaridade
Contribuem para a necessidade de criar um suporte para a realizacao deconsultas por similaridade em SGBDR:
O aumento da quantidade de dados de domınios complexosarmazenados em bases de dados relacionais
A integracao de metodos de mineracao de dados com SGBDR
Ponto fundamental: disponibilizacao de operacoes basicas para astecnicas de mineracao de dados existentes
ex.: deteccao de agrupamentos de dados ⇒ calculo de medidas desimilaridade entre os pares de objetos de um conjunto de dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 6 / 67
Diante disso...
Questoes importantes:
1 Como comparar dados complexos?
2 Como indexar conjuntos de dados complexos?
3 Como expressar consultas sobre esses dados no SGBD?
4 Como otimizar os algoritmos de deteccao de agrupamentos demaneira a torna-los exequıveis em SGBD?
Maria Camila N. Barioni (UFABC) Palestra PosComp 7 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 8 / 67
Conceitos FundamentaisDomınios de dados complexos
Dados de domınios complexos podem ser armazenados em um banco dedados:
1 Conjunto de atributos de domınios tradicionais
ex.: series temporais, informacoes geo-referenciadas, ...
comparacao por similaridade: aplicacao de funcao de distancia sobre osvalores dos atributos que os compoem
2 Objeto binario BLOB
ex.: imagens, trilhas de audio, ...
comparacao por similaridade: aplicacao de funcao de distancia sobreum conjunto pre-definido de caracterısticas inerentes aos dados
ex.: recuperacao de imagens por conteudo
Maria Camila N. Barioni (UFABC) Palestra PosComp 9 / 67
Conceitos FundamentaisDomınios de dados complexos
Dados de domınios complexos podem ser armazenados em um banco dedados:
1 Conjunto de atributos de domınios tradicionais
ex.: series temporais, informacoes geo-referenciadas, ...
comparacao por similaridade: aplicacao de funcao de distancia sobre osvalores dos atributos que os compoem
2 Objeto binario BLOB
ex.: imagens, trilhas de audio, ...
comparacao por similaridade: aplicacao de funcao de distancia sobreum conjunto pre-definido de caracterısticas inerentes aos dados
ex.: recuperacao de imagens por conteudo
Maria Camila N. Barioni (UFABC) Palestra PosComp 9 / 67
Conceitos FundamentaisDomınios de dados complexos
Dados de domınios complexos podem ser armazenados em um banco dedados:
1 Conjunto de atributos de domınios tradicionais
ex.: series temporais, informacoes geo-referenciadas, ...
comparacao por similaridade: aplicacao de funcao de distancia sobre osvalores dos atributos que os compoem
2 Objeto binario BLOB
ex.: imagens, trilhas de audio, ...
comparacao por similaridade: aplicacao de funcao de distancia sobreum conjunto pre-definido de caracterısticas inerentes aos dados
ex.: recuperacao de imagens por conteudo
Maria Camila N. Barioni (UFABC) Palestra PosComp 9 / 67
Conceitos FundamentaisComo representar dados complexos?
Representacao das Imagens
Imagemoriginal
Exemplos de caracterısticas visuais: cor, textura e forma
Maria Camila N. Barioni (UFABC) Palestra PosComp 10 / 67
Conceitos FundamentaisComo representar dados complexos?
Representacao das Imagens
Imagemoriginal
Extrator deCaracterísticas
Exemplos de caracterısticas visuais: cor, textura e forma
Maria Camila N. Barioni (UFABC) Palestra PosComp 10 / 67
Conceitos FundamentaisComo representar dados complexos?
Representacao das Imagens
Imagemoriginal
Vetor decaracterísticas
Extrator deCaracterísticas
x1
x2
xn
.
.
.
Exemplos de caracterısticas visuais: cor, textura e forma
Maria Camila N. Barioni (UFABC) Palestra PosComp 10 / 67
Conceitos FundamentaisComo representar dados complexos?
Representacao das Imagens
Imagemoriginal
Vetor decaracterísticas
Extrator deCaracterísticas
x1
x2
xn
.
.
. Ponto noespaço das
características
Exemplos de caracterısticas visuais: cor, textura e forma
Maria Camila N. Barioni (UFABC) Palestra PosComp 10 / 67
Conceitos FundamentaisComo representar dados complexos?
Representacao das Imagens
Imagemoriginal
Vetor decaracterísticas
Extrator deCaracterísticas
x1
x2
xn
.
.
. Ponto noespaço das
características
Exemplos de caracterısticas visuais: cor, textura e forma
Maria Camila N. Barioni (UFABC) Palestra PosComp 10 / 67
Conceitos FundamentaisComo representar dados complexos?
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Extração
x 1x 2
x n
.
.
. Extração
Extração
x 1x 2
x n
.
.
.
x 1x 2
x n
.
.
.
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Extração
x 1x 2
x n
.
.
. Extração
Extração
x 1x 2
x n
.
.
.
x 1x 2
x n
.
.
.
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Extração
x 1x 2
x n
.
.
. Extração
Extração
x 1x 2
x n
.
.
.
x 1x 2
x n
.
.
.
Menor similaridade
Maiorsimilaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Extração
x 1x 2
x n
.
.
. Extração
Extração
x 1x 2
x n
.
.
.
x 1x 2
x n
.
.
.
Menor similaridade
Maiorsimilaridade
Maispróximo
Maisdistante
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Extração
x 1x 2
x n
.
.
. Extração
Extração
x 1x 2
x n
.
.
.
x 1x 2
x n
.
.
.
Menor similaridade
Maiorsimilaridade
Maispróximo
Maisdistante
Cálculo da similaridade: função de distância
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo representar dados complexos?
Espaço multi-dimensional ou espaço métrico
Maria Camila N. Barioni (UFABC) Palestra PosComp 11 / 67
Conceitos FundamentaisComo comparar dados complexos?
Espaco Metrico
Definicao: Um espaco metrico M e definido pelo par {S, d()}, onde Sdefine o domınio dos dados e d() e uma funcao de distancia que atendeas propriedades:
Simetria: d(s1, s2) = d(s2, s1)
Nao-negatividade: 0 ≤ d(s1, s2) <∞
Desigualdade triangular: d(s1, s2) ≤ d(s1, s3) + d(s3, s2)
Calculo da Similaridade ⇒ funcao de distancia
Maria Camila N. Barioni (UFABC) Palestra PosComp 12 / 67
Conceitos FundamentaisComo comparar dados complexos?
Exemplo de funcao de distancia para domınios vetoriais:
funcao de distancia Lp (Minkowski)
d(x , y) = p
√∑ni=1 |xi − yi |p
onde n e a dimensao do espaco vetorial
Maria Camila N. Barioni (UFABC) Palestra PosComp 13 / 67
Conceitos FundamentaisComo comparar dados complexos?
Exemplo de funcao de distancia para domınios vetoriais:
funcao de distancia Lp (Minkowski)
d(x , y) = p
√∑ni=1 |xi − yi |p
onde n e a dimensao do espaco vetorial
q ξ
Manhattan
1
32
L1 1
Maria Camila N. Barioni (UFABC) Palestra PosComp 13 / 67
Conceitos FundamentaisComo comparar dados complexos?
Exemplo de funcao de distancia para domınios vetoriais:
funcao de distancia Lp (Minkowski)
d(x , y) = p
√∑ni=1 |xi − yi |p
onde n e a dimensao do espaco vetorial
q ξ
Manhattan
Euclidiana
1
32
L2
L1
1 2
1
Maria Camila N. Barioni (UFABC) Palestra PosComp 13 / 67
Conceitos FundamentaisComo comparar dados complexos?
Exemplo de funcao de distancia para domınios vetoriais:
funcao de distancia Lp (Minkowski)
d(x , y) = p
√∑ni=1 |xi − yi |p
onde n e a dimensao do espaco vetorial
q ξ
Manhattan
EuclidianaChebyshev
1
32
L 8 L2
L1
1 2 31 2
1
Maria Camila N. Barioni (UFABC) Palestra PosComp 13 / 67
Conceitos FundamentaisComo comparar dados complexos?
Exemplo de funcao de distancia para domınios nao-vetoriais:
Funcao de distancia LEDIT (x , y) ⇒ quantidade mınima de caracteresque precisam ser substituıdos, removidos ou inseridos em x , para queela se torne igual a y
Exemplos:
LEDIT (’amora’,’aroma’) = 2 (duas substituicoes)
LEDIT (’amora’,’amor’) = 1 (uma remocao)
Maria Camila N. Barioni (UFABC) Palestra PosComp 14 / 67
Conceitos FundamentaisComo consultar?
Na literatura apresentam-se:
Duas operacoes que comparam um objeto de referencia com aquelesarmazenados em uma colecao de objetos⇒ selecao
Consulta por abrangencia (Range query)
Consulta aos k-vizinhos mais proximos (k-Nearest neighbor query)
Tres operacoes que comparam pares de objetos armazenados em duascolecoes de objetos⇒ juncao
Juncao por abrangencia (Range Join)
Juncao pelos k-vizinhos mais proximos (k-Nearest Neighbors Join)
Juncao dos k-pares de vizinhos mais proximos (k-ClosestNeighbors Join)
Maria Camila N. Barioni (UFABC) Palestra PosComp 15 / 67
Conceitos FundamentaisComo consultar?
Na literatura apresentam-se:
Duas operacoes que comparam um objeto de referencia com aquelesarmazenados em uma colecao de objetos⇒ selecao
Consulta por abrangencia (Range query)
Consulta aos k-vizinhos mais proximos (k-Nearest neighbor query)
Tres operacoes que comparam pares de objetos armazenados em duascolecoes de objetos⇒ juncao
Juncao por abrangencia (Range Join)
Juncao pelos k-vizinhos mais proximos (k-Nearest Neighbors Join)
Juncao dos k-pares de vizinhos mais proximos (k-ClosestNeighbors Join)
Maria Camila N. Barioni (UFABC) Palestra PosComp 15 / 67
Conceitos FundamentaisComo consultar?
Para exemplificar:
Conjunto de dados CidadeBR
Cada tupla ⇒ nome da cidade + coordenadas geograficas
Medida de similaridade ⇒ distancia entre as cidades computada pelaaplicacao da funcao de distancia Euclidiana sobre as suas coordenadas
Maria Camila N. Barioni (UFABC) Palestra PosComp 16 / 67
Conceitos FundamentaisComo consultar? – Exemplo Selecao por Similaridade
São CarlosIbaté
Araraquara
DouradoRibeirãoBonito
Brotas ItirapinaCorumbataí
Analândia
Araras
Leme
Descalvado
(-22.02, 47.89)
Maria Camila N. Barioni (UFABC) Palestra PosComp 17 / 67
Conceitos FundamentaisComo consultar? – Exemplo Selecao por Similaridade
L 2
k = 5
São CarlosIbaté
Araraquara
DouradoRibeirãoBonito
Brotas ItirapinaCorumbataí
Analândia
Araras
Leme
Descalvado
(-22.02, 47.89)
CidadeBRkobjdNNqk c)( },{(), ><−σSeleção dos k-vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 17 / 67
Conceitos FundamentaisComo consultar? – Exemplo Selecao por Similaridade
L 2
São CarlosIbaté
Araraquara
DouradoRibeirãoBonito
Brotas ItirapinaCorumbataí
Analândia
Araras
Leme
Descalvado
(-22.02, 47.89)
k = 5
CidadeBRkobjdNNqk c)( },{(), ><−σSeleção dos k-vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 17 / 67
Conceitos FundamentaisComo consultar? – Exemplo Selecao por Similaridade
L 2
São CarlosIbaté
Araraquara
DouradoRibeirãoBonito
Brotas ItirapinaCorumbataí
Analândia
Araras
Leme
Descalvado
(-22.02, 47.89)
3.0=ξ
CidadeBRcobjdRq )( },{(), >< ξσSeleção por abrangência:
Maria Camila N. Barioni (UFABC) Palestra PosComp 17 / 67
Conceitos FundamentaisComo consultar? – Exemplo Selecao por Similaridade
L 2
São CarlosIbaté
Araraquara
DouradoRibeirãoBonito
Brotas ItirapinaCorumbataí
Analândia
Araras
Leme
Descalvado
(-22.02, 47.89)
3.0=ξ
CidadeBRcobjdRq )( },{(), >< ξσSeleção por abrangência:
Maria Camila N. Barioni (UFABC) Palestra PosComp 17 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
São PauloRio de Janeiro
Vitória
Belo Horizonte
11.0=ξ
CidadeBRCapitalSE>< ξ(),dRq
L 2
Junção por abrangência:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
São PauloRio de Janeiro
Vitória
Belo Horizonte
ξ
ξ
ξ
ξL 2
11.0=ξ
CidadeBRCapitalSE>< ξ(),dRq
Junção por abrangência:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
Rio de Janeiro
Vitória
Belo Horizonte
ξ
ξ
ξ
ξ
CapitalSE CidadeBR
São Paulo-SP São Caetano do Sul-SP
Belo Horizonte-MG
Belo Horizonte-MG
Contagem-MG
Nova Lima-MG
Rio de Janeiro-RJ Niterói-RJ
Vitória-ES
Vitória-ES
Vila Velha-ES
Cariacica-ES
11.0=ξ
CidadeBRCapitalSE>< ξ(),dRq
Junção por abrangência:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
São PauloRio de Janeiro
Vitória
Belo Horizonte
CidadeBRCapitalSE><− kdNNqk (),
k = 2
L 2
Junção pelos k-vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
São PauloRio de Janeiro
Vitória
Belo Horizonte
L 2
CidadeBRCapitalSE><− kdNNqk (),
k = 2
Junção pelos k-vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
Rio de Janeiro
Vitória
Belo Horizonte
CapitalSE CidadeBR
São Paulo-SP São Caetano do Sul-SP
Belo Horizonte-MG
Belo Horizonte-MG
Contagem-MG
Nova Lima-MG
Rio de Janeiro-RJ Niterói-RJ
Vitória-ES
Vitória-ES
Vila Velha-ES
Cariacica-ES
Rio de Janeiro-RJ Duque de Caxias-RJ
São Paulo-SP Diadema-SP
CidadeBRCapitalSE><− kdNNqk (),
k = 2
Junção pelos k-vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
São PauloRio de Janeiro
Vitória
Belo Horizonte
k = 2
CidadeBRCapitalSE><− kdCNqk (),
L 2
Junção dos k-pares de vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
São PauloRio de Janeiro
Vitória
Belo Horizonte
L 2
k = 2
CidadeBRCapitalSE><− kdCNqk (),
Junção dos k-pares de vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo consultar? – Exemplo Juncao por Similaridade
Rio de Janeiro
Vitória
Belo Horizonte
CapitalSE CidadeBR
Vitória-ES
Vitória-ES
Vila Velha-ES
Cariacica-ES
k = 2
CidadeBRCapitalSE><− kdCNqk (),
Junção dos k-pares de vizinhos mais próximos:
Maria Camila N. Barioni (UFABC) Palestra PosComp 18 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s3
s3
s10
s10
s12
s12
s8
s8
s8
s8
s9
s9
s11
s11
s4
s4
s15
s15
s14
s14
root noderoot node
s6
s6
s13
s13
index
node
index
node
leaf
node
leaf
node
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s3
s3
s10
s10
s12
s12
s8
s8
s8
s8
s9
s9
s11
s11
s4
s4
s15
s15
s14
s14
s6
s6
s13
s13
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
root noderoot node
index
node
index
node
leaf
node
leaf
node
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s3
s3
s10
s10
s12
s12
s8
s8
s8
s8
s9
s9
s11
s11
s4
s4
s15
s15
s14
s14
s6
s6
s13
s13
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
root noderoot node
index
node
index
node
leaf
node
leaf
node
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s3
s3
s10
s10
s12
s12
s8
s8
s8
s8
s9
s9
s11
s11
s4
s4
s15
s15
s14
s14
s6
s6
s13
s13
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
root noderoot node
index
node
index
node
leaf
node
leaf
node
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s3
s3
s10
s10
s12
s12
s8
s8
s8
s8
s9
s9
s11
s11
s4
s4
s15
s15
s14
s14
s6
s6
s13
s13
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
root noderoot node
index
node
index
node
leaf
node
leaf
node
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisComo indexar conjuntos de dados complexos?
Estruturas de Indexacao (Metodos de Acesso)
Sao utilizadas para agilizar a realizacao de consultas por similaridade
Para espacos metricos: Metodos de Acesso Metrico (MAM)
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s3
s3
s10
s10
s12
s12
s8
s8
s8
s8
s9
s9
s11
s11
s4
s4
s15
s15
s14
s14
s6
s6
s13
s13
s1
s1
s2
s2
s6
s6
s3
s3
s10
s10
s13
s13
s8
s8
s9
s9
s11
s11
s14
s14
s7
s7
s5
s5
s12
s12
s4
s4
s15
s15
root noderoot node
index
node
index
node
leaf
node
leaf
node
Maria Camila N. Barioni (UFABC) Palestra PosComp 19 / 67
Conceitos FundamentaisDescoberta de Conhecimento em Bases de Dados e Mineracao de Dados
Processo interativo e iterativo que envolve tres etapas:
Base deDados
Base de DadosFlat Files
ConhecimentoLimpeza e Integração
Seleção e Transformação
Mineração de Dados
Avaliação e Apresentação
Padrões
Pré-processamento Descoberta de Padrões Avaliação dos Resultados
Maria Camila N. Barioni (UFABC) Palestra PosComp 20 / 67
Conceitos FundamentaisDescoberta de Conhecimento em Bases de Dados e Mineracao de Dados
Processo interativo e iterativo que envolve tres etapas:
Base deDados
Base de DadosFlat Files
ConhecimentoLimpeza e Integração
Seleção e Transformação
Mineração de Dados
Avaliação e Apresentação
Padrões
Pré-processamento Descoberta de Padrões Avaliação dos Resultados
Maria Camila N. Barioni (UFABC) Palestra PosComp 20 / 67
Conceitos FundamentaisDescoberta de Conhecimento em Bases de Dados e Mineracao de Dados
Demanda:
Algoritmos de mineracao de dados escalaveis
Estrategia:
Disponibilizar operacoes basicas pelos SGBDExemplo
Tecnica: Deteccao de AgrupamentosOperacao basica: Calculo de medidas de similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 21 / 67
Conceitos FundamentaisDescoberta de Conhecimento em Bases de Dados e Mineracao de Dados
Demanda:
Algoritmos de mineracao de dados escalaveis
Estrategia:
Disponibilizar operacoes basicas pelos SGBDExemplo
Tecnica: Deteccao de AgrupamentosOperacao basica: Calculo de medidas de similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 21 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Deteccao de Agrupamentos
Definicao: Processo de divisao de objetos em classes (ou grupos) deobjetos similares de acordo com uma medida de similaridade
Duas categorias de algoritmos
Hierarquico
cria uma hierarquia de agrupamentos, formada por varios nıveis departicoes aninhadas de um conjunto de dados
Particionamentoconstroi um unico nıvel de particao que divide os dados em kagrupamentos representados por
Maria Camila N. Barioni (UFABC) Palestra PosComp 22 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Deteccao de Agrupamentos
Definicao: Processo de divisao de objetos em classes (ou grupos) deobjetos similares de acordo com uma medida de similaridade
Duas categorias de algoritmos
Hierarquico
cria uma hierarquia de agrupamentos, formada por varios nıveis departicoes aninhadas de um conjunto de dados
Particionamentoconstroi um unico nıvel de particao que divide os dados em kagrupamentos representados por
Centroides (k-media)Medoides (k-medoide)
Maria Camila N. Barioni (UFABC) Palestra PosComp 22 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Deteccao de Agrupamentos
Definicao: Processo de divisao de objetos em classes (ou grupos) deobjetos similares de acordo com uma medida de similaridade
Duas categorias de algoritmos
Hierarquico
cria uma hierarquia de agrupamentos, formada por varios nıveis departicoes aninhadas de um conjunto de dados
Particionamentoconstroi um unico nıvel de particao que divide os dados em kagrupamentos representados por
Centroides (k-media)Medoides (k-medoide)
Maria Camila N. Barioni (UFABC) Palestra PosComp 22 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Deteccao de Agrupamentos
Definicao: Processo de divisao de objetos em classes (ou grupos) deobjetos similares de acordo com uma medida de similaridade
Duas categorias de algoritmos
Hierarquico
cria uma hierarquia de agrupamentos, formada por varios nıveis departicoes aninhadas de um conjunto de dados
Particionamentoconstroi um unico nıvel de particao que divide os dados em kagrupamentos representados por
Centroides (k-means)Medoides (k-medoide)
Maria Camila N. Barioni (UFABC) Palestra PosComp 22 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Razoes para a escolha dos algoritmos baseados no k-medoide
Vantagens
Sao menos sensıveis quanto a presenca de outliersNao apresentam limitacoes quanto ao tipo de atributoNao dependem da ordem de entrada dos dados
Desvantagens
Apresentam um custo computacional muito elevado
⇓Estrategia de otimizacao: selecionar uma amostragem do conjuntode dados antes da realizacao do processo de agrupamento dos dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 23 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Razoes para a escolha dos algoritmos baseados no k-medoide
Vantagens
Sao menos sensıveis quanto a presenca de outliersNao apresentam limitacoes quanto ao tipo de atributoNao dependem da ordem de entrada dos dados
Desvantagens
Apresentam um custo computacional muito elevado
⇓Estrategia de otimizacao: selecionar uma amostragem do conjuntode dados antes da realizacao do processo de agrupamento dos dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 23 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Razoes para a escolha dos algoritmos baseados no k-medoide
Vantagens
Sao menos sensıveis quanto a presenca de outliersNao apresentam limitacoes quanto ao tipo de atributoNao dependem da ordem de entrada dos dados
Desvantagens
Apresentam um custo computacional muito elevado
⇓Estrategia de otimizacao: selecionar uma amostragem do conjuntode dados antes da realizacao do processo de agrupamento dos dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 23 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Razoes para a escolha dos algoritmos baseados no k-medoide
Vantagens
Sao menos sensıveis quanto a presenca de outliersNao apresentam limitacoes quanto ao tipo de atributoNao dependem da ordem de entrada dos dados
Desvantagens
Apresentam um custo computacional muito elevado
⇓
Estrategia de otimizacao: selecionar uma amostragem do conjuntode dados antes da realizacao do processo de agrupamento dos dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 23 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Razoes para a escolha dos algoritmos baseados no k-medoide
Vantagens
Sao menos sensıveis quanto a presenca de outliersNao apresentam limitacoes quanto ao tipo de atributoNao dependem da ordem de entrada dos dados
Desvantagens
Apresentam um custo computacional muito elevado
⇓Estrategia de otimizacao: selecionar uma amostragem do conjuntode dados antes da realizacao do processo de agrupamento dos dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 23 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Objetivo:
encontrar um conjunto de agrupamentos nao sobrepostos de modoque cada agrupamento possua um objeto representante (medoide)
Passos principais:
Inicializacao
seleciona-se um conjunto inicial de k medoides
Avaliacao
uma funcao de pontuacao, baseada na soma da distancia total entre osobjetos nao selecionados e seus medoides e minimizada
Quanto menor a soma das distancias entre os medoides e todos os outrosobjetos de seus agrupamentos, melhor o resultado do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 24 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Objetivo:
encontrar um conjunto de agrupamentos nao sobrepostos de modoque cada agrupamento possua um objeto representante (medoide)
Passos principais:
Inicializacao
seleciona-se um conjunto inicial de k medoides
Avaliacao
uma funcao de pontuacao, baseada na soma da distancia total entre osobjetos nao selecionados e seus medoides e minimizada
Quanto menor a soma das distancias entre os medoides e todos os outrosobjetos de seus agrupamentos, melhor o resultado do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 24 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Exemplo abordagem k-medoide
Algoritmos utilizados no trabalhoAbordagem K-medóide
Y
V Sessão de Demos - XXIII SBBD 5
XMaria Camila N. Barioni (UFABC) Palestra PosComp 25 / 67
Conceitos FundamentaisDeteccao de agrupamentos
k medoides iniciais sao escolhidos aleatoriamente
Algoritmos utilizados no trabalhoAbordagem K-medóide
m1
Y2m2
V Sessão de Demos - XXIII SBBD 6
X
Maria Camila N. Barioni (UFABC) Palestra PosComp 25 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Os objetos sao atribuidos aos medoides mais proximos
Algoritmos utilizados no trabalhoAbordagem K-medóide
m1
Y2m2
V Sessão de Demos - XXIII SBBD 7
XMaria Camila N. Barioni (UFABC) Palestra PosComp 25 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Muda-se os medoides para os objetos centrais de cada agrupamento
Algoritmos utilizados no trabalhoAbordagem K-medóide
Y m2m2
m1
V Sessão de Demos - XXIII SBBD 8
XMaria Camila N. Barioni (UFABC) Palestra PosComp 25 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Atualizam-se os objetos mais proximos dos novos medoides
Algoritmos utilizados no trabalhoAbordagem K-medóide
Y m2m2
m1
V Sessão de Demos - XXIII SBBD 9
XMaria Camila N. Barioni (UFABC) Palestra PosComp 25 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Novos medoides sao calculados. Repete-se ate estabilizar
Algoritmos utilizados no trabalhoAbordagem K-medóide
Y m2m2
m1
V Sessão de Demos - XXIII SBBD 9
XMaria Camila N. Barioni (UFABC) Palestra PosComp 25 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Algoritmos mais conhecidos:
PAM (Partitioning Around Medoids)
Melhor qualidade
Maior custo computacional⇒ O(k(N − k)2)
CLARA (Clustering LARge Applications)
Baseado em amostragem⇒ O(ks2 + k(N − k))Conjunto de dados aumenta⇒ qualidade degrada
CLARANS (Clustering Large Applications based upon RANdomizedSearch)
Baseado em busca aleatoria
Complexidade computacional⇒ O(N2)
Maria Camila N. Barioni (UFABC) Palestra PosComp 26 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Algoritmos mais conhecidos:
PAM (Partitioning Around Medoids)
Melhor qualidade
Maior custo computacional⇒ O(k(N − k)2)
CLARA (Clustering LARge Applications)
Baseado em amostragem⇒ O(ks2 + k(N − k))Conjunto de dados aumenta⇒ qualidade degrada
CLARANS (Clustering Large Applications based upon RANdomizedSearch)
Baseado em busca aleatoria
Complexidade computacional⇒ O(N2)
Maria Camila N. Barioni (UFABC) Palestra PosComp 26 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Algoritmos mais conhecidos:
PAM (Partitioning Around Medoids)
Melhor qualidade
Maior custo computacional⇒ O(k(N − k)2)
CLARA (Clustering LARge Applications)
Baseado em amostragem⇒ O(ks2 + k(N − k))Conjunto de dados aumenta⇒ qualidade degrada
CLARANS (Clustering Large Applications based upon RANdomizedSearch)
Baseado em busca aleatoria
Complexidade computacional⇒ O(N2)
Maria Camila N. Barioni (UFABC) Palestra PosComp 26 / 67
Conceitos FundamentaisDeteccao de agrupamentos
Algoritmos mais conhecidos:
PAM (Partitioning Around Medoids)
Melhor qualidade
Maior custo computacional⇒ O(k(N − k)2)
CLARA (Clustering LARge Applications)
Baseado em amostragem⇒ O(ks2 + k(N − k))Conjunto de dados aumenta⇒ qualidade degrada
CLARANS (Clustering Large Applications based upon RANdomizedSearch)
Baseado em busca aleatoria
Complexidade computacional⇒ O(N2)
Maria Camila N. Barioni (UFABC) Palestra PosComp 26 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 27 / 67
Suportando Consultas por Similaridade em SQLDomınios de dados complexos
Os domınios de objetos complexos podem ser separados em:
PARTICULATE
Tipo de objeto: composto por uma colecao de atributos tradicionais
Forma de comparacao: os valores armazenados nos atributostradicionais sao utilizados para calcular a distancia entre cada par deobjetos complexos
MONOLITHIC
Tipo de objeto: armazenado como um unico objeto binario BLOB(atributo indivisıvel)
Forma de comparacao: e necessario aplicar algoritmos de extracao decaracterısticas sobre eles
Maria Camila N. Barioni (UFABC) Palestra PosComp 28 / 67
Suportando Consultas por Similaridade em SQLDomınios de dados complexos
Os domınios de objetos complexos podem ser separados em:
PARTICULATE
Tipo de objeto: composto por uma colecao de atributos tradicionais
Forma de comparacao: os valores armazenados nos atributostradicionais sao utilizados para calcular a distancia entre cada par deobjetos complexos
MONOLITHIC
Tipo de objeto: armazenado como um unico objeto binario BLOB(atributo indivisıvel)
Forma de comparacao: e necessario aplicar algoritmos de extracao decaracterısticas sobre eles
Maria Camila N. Barioni (UFABC) Palestra PosComp 28 / 67
Suportando Consultas por Similaridade em SQLDomınios de dados complexos
Os domınios de objetos complexos podem ser separados em:
PARTICULATE
Tipo de objeto: composto por uma colecao de atributos tradicionais
Forma de comparacao: os valores armazenados nos atributostradicionais sao utilizados para calcular a distancia entre cada par deobjetos complexos
MONOLITHIC
Tipo de objeto: armazenado como um unico objeto binario BLOB(atributo indivisıvel)
Forma de comparacao: e necessario aplicar algoritmos de extracao decaracterısticas sobre eles
Maria Camila N. Barioni (UFABC) Palestra PosComp 28 / 67
Suportando Consultas por Similaridade em SQLTipos de dados complexos
Para realizar consultas por similaridade em domınios complexos
E necessario definir cada domınio onde a similaridade sera medidacomo um novo tipo de dados
Novos tipos de dados
PARTICULATE PARTICULATE
MONOLITHICSTILLIMAGE
AUDIO
PARTICULATE PARTICULATE
MONOLITHICSTILLIMAGE
AUDIO
Maria Camila N. Barioni (UFABC) Palestra PosComp 29 / 67
Suportando Consultas por Similaridade em SQL
Passos para a realizacao de consultas por similaridade em SQL
DDL
1 Definir medidas de similaridade (Metricas)
2 Especificar tipos de dados complexos na definicao de tabelas
3 Associar atributos complexos com medidas de similaridade
4 Definir ındices (opcional)
DML
5 Popular/atualizar a base de dados
6 Especificar consultas
Maria Camila N. Barioni (UFABC) Palestra PosComp 30 / 67
Suportando Consultas por Similaridade em SQLDefinir medidas de similaridade – Metricas
Novos comandos
CREATE METRIC
ALTER METRIC
DROP METRIC
Exemplos:
CREATE METRIC Euclidiana2D USING LP2 FOR PARTICULATE
(Latitude FLOAT, Longitude FLOAT);
CREATE METRIC Histograma USING LP1 FOR STILLIMAGE
(HistogramaEXT (HistogramaC AS Histo));
Maria Camila N. Barioni (UFABC) Palestra PosComp 31 / 67
Suportando Consultas por Similaridade em SQLDefinir medidas de similaridade – Metricas
Novos comandos
CREATE METRIC
ALTER METRIC
DROP METRIC
Exemplos:
CREATE METRIC Euclidiana2D USING LP2 FOR PARTICULATE
(Latitude FLOAT, Longitude FLOAT);
CREATE METRIC Histograma USING LP1 FOR STILLIMAGE
(HistogramaEXT (HistogramaC AS Histo));
Maria Camila N. Barioni (UFABC) Palestra PosComp 31 / 67
Suportando Consultas por Similaridade em SQLEspecificar tipos de dados complexos na definicao de tabelas – Exemplos
PARTICULATE
CREATE TABLE CidadeBR (
Nome CHAR(30) PRIMARY KEY,
Lat FLOAT,
Longit FLOAT,
Coordenada PARTICULATE,
...);
MONOLITHIC
CREATE TABLE Paisagem (
Id INTEGER PRIMARY KEY,
Local CHAR(20),
Fotografo CHAR(30),
Foto STILLIMAGE,
... );
Nome Lat Longit Coordenada
São Carlos-SP -22.02 47.89 1203
Id Local Fotografo Foto
Cristo Redentor -
RJHumberto196
Nome Lat Longit Coordenada
São Carlos-SP -22.02 47.89 1203
Id Local Fotografo Foto
Cristo Redentor -
RJHumberto196
Maria Camila N. Barioni (UFABC) Palestra PosComp 32 / 67
Suportando Consultas por Similaridade em SQLEspecificar tipos de dados complexos na definicao de tabelas – Exemplos
PARTICULATE
CREATE TABLE CidadeBR (
Nome CHAR(30) PRIMARY KEY,
Lat FLOAT,
Longit FLOAT,
Coordenada PARTICULATE,
...);
MONOLITHIC
CREATE TABLE Paisagem (
Id INTEGER PRIMARY KEY,
Local CHAR(20),
Fotografo CHAR(30),
Foto STILLIMAGE,
... );
Nome Lat Longit Coordenada
São Carlos-SP -22.02 47.89 1203
Id Local Fotografo Foto
Cristo Redentor -
RJHumberto196
Nome Lat Longit Coordenada
São Carlos-SP -22.02 47.89 1203
Id Local Fotografo Foto
Cristo Redentor -
RJHumberto196
Maria Camila N. Barioni (UFABC) Palestra PosComp 32 / 67
Suportando Consultas por Similaridade em SQLEspecificar tipos de dados complexos na definicao de tabelas – Exemplos
PARTICULATE
CREATE TABLE CidadeBR (
Nome CHAR(30) PRIMARY KEY,
Lat FLOAT,
Longit FLOAT,
Coordenada PARTICULATE,
...);
MONOLITHIC
CREATE TABLE Paisagem (
Id INTEGER PRIMARY KEY,
Local CHAR(20),
Fotografo CHAR(30),
Foto STILLIMAGE,
... );
Nome Lat Longit Coordenada
São Carlos-SP -22.02 47.89 1203
Id Local Fotografo Foto
Cristo Redentor -
RJHumberto196
Nome Lat Longit Coordenada
São Carlos-SP -22.02 47.89 1203
Id Local Fotografo Foto
Cristo Redentor -
RJHumberto196
Maria Camila N. Barioni (UFABC) Palestra PosComp 32 / 67
Suportando Consultas por Similaridade em SQLAssociar atributos complexos com medidas de similaridade
A definicao de como comparar pares de dados de tipos complexos eexpressa como uma restricao no comando CREATE TABLE:
Restricao de coluna
Restricao de tabela
Maria Camila N. Barioni (UFABC) Palestra PosComp 33 / 67
Suportando Consultas por Similaridade em SQLAssociar atributos complexos com medidas de similaridade – Exemplo
PARTICULATE:
CREATE METRIC Euclidiana2D USING LP2
FOR PARTICULATE (Latitude FLOAT,
Longitude FLOAT);
CREATE TABLE CidadeBR (
Nome CHAR(30) PRIMARY KEY,
Lat FLOAT,
Longit FLOAT,
Coordenada PARTICULATE,
METRIC (Coordenada) REFERENCES (Lat AS Latitude,
Longit AS Longitude)
USING (Euclidiana2D),
... );
Maria Camila N. Barioni (UFABC) Palestra PosComp 34 / 67
Suportando Consultas por Similaridade em SQLAssociar atributos complexos com medidas de similaridade – Exemplo
MONOLITHIC:
CREATE METRIC Histograma USING LP1
FOR STILLIMAGE (HistogramaEXT (HistogramaC AS Histo));
CREATE METRIC Textura USING LP1
FOR STILLIMAGE (TexturaEXT (TexturaC AS Text));
CREATE TABLE Paisagem (
Id INTEGER PRIMARY KEY,
Local CHAR(20),
Fotografo CHAR(30),
Foto STILLIMAGE METRIC USING (Histograma DEFAULT, Textura),
... );
Maria Camila N. Barioni (UFABC) Palestra PosComp 35 / 67
Suportando Consultas por Similaridade em SQLDefinir ındices (opcional)
Consultas por similaridade podem ser realizadas mais rapidamente seforem criados ındices sobre os atributos complexos
Metodos de acesso metrico (MAM)
Exemplos:
PARTICULATE:
CREATE INDEX Geografia ON CidadeBR (Coordenada)
REFERENCES (Lat AS Latitute, Longit AS Longitude)
USING Euclidiana2D;
MONOLITHIC:
CREATE INDEX FotoPaisagem ON Paisagem (Foto)
USING Histograma;
Maria Camila N. Barioni (UFABC) Palestra PosComp 36 / 67
Suportando Consultas por Similaridade em SQLDefinir ındices (opcional)
Consultas por similaridade podem ser realizadas mais rapidamente seforem criados ındices sobre os atributos complexos
Metodos de acesso metrico (MAM)
Exemplos:
PARTICULATE:
CREATE INDEX Geografia ON CidadeBR (Coordenada)
REFERENCES (Lat AS Latitute, Longit AS Longitude)
USING Euclidiana2D;
MONOLITHIC:
CREATE INDEX FotoPaisagem ON Paisagem (Foto)
USING Histograma;
Maria Camila N. Barioni (UFABC) Palestra PosComp 36 / 67
Suportando Consultas por Similaridade em SQLPopular/atualizar a base de dados
Para a sintaxe do comando INSERT nao foi necessario nenhumaalteracao
A sintaxe dos comandos UPDATE e DELETE necessitam de novasconstrucoes para expressar predicados por similaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 37 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Comando SELECT
Novas construcoes para predicados por similaridade
Selecoes e juncoes por similaridade⇒ clausula WHERE
Juncoes por similaridade⇒ clausula FROM
Novas construcoes para suportar a analise de agrupamento porsimilaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 38 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Comando SELECT
Novas construcoes para predicados por similaridade
Selecoes e juncoes por similaridade⇒ clausula WHERE
Juncoes por similaridade⇒ clausula FROM
Novas construcoes para suportar a analise de agrupamento porsimilaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 38 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Comando SELECT
Novas construcoes para predicados por similaridade
Selecoes e juncoes por similaridade⇒ clausula WHERE
Juncoes por similaridade⇒ clausula FROM
Novas construcoes para suportar a analise de agrupamento porsimilaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 38 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Comando SELECT
Novas construcoes para predicados por similaridade
Selecoes e juncoes por similaridade⇒ clausula WHERE
Juncoes por similaridade⇒ clausula FROM
Novas construcoes para suportar a analise de agrupamento porsimilaridade
Maria Camila N. Barioni (UFABC) Palestra PosComp 38 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Comando SELECT
Sintaxe basica para expressar selecoes por similaridade:
<atributo> NEAR <valor>
[STOP AFTER <k >]
[RANGE <ξ>]
Maria Camila N. Barioni (UFABC) Palestra PosComp 39 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Exemplos de selecoes por similaridade:
PARTICULATE:
SELECT * FROM CidadeBR
WHERE Coordenada NEAR (-22.02 AS Latitude,
47.89 AS Longitude) RANGE 2;
SELECT Nome FROM CidadeBR
WHERE Coordenada NEAR (SELECT Lat AS Latitude,
Longit AS Longitude
FROM CidadeBR
WHERE Nome = ‘S~ao Carlos-SP’)
STOP AFTER 5;
Maria Camila N. Barioni (UFABC) Palestra PosComp 40 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Exemplos de selecoes por similaridade:
MONOLITHIC:
SELECT * FROM Paisagem
WHERE Foto NEAR ‘c:\img09.jpg’ STOP AFTER 5;
SELECT * FROM Paisagem
WHERE Foto NEAR (SELECT Foto FROM Paisagem
WHERE Id = 123) STOP AFTER 5;
Maria Camila N. Barioni (UFABC) Palestra PosComp 41 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Sintaxe basica para expressar juncoes por similaridade na clausulaWHERE:
<tabela1>‘.’<atributo1> NEAR [ANY] <tabela2>‘.’<atributo2>
[STOP AFTER <k >] [RANGE <ξ>]
Tipos de construcoes:
T1.atr1 NEAR T2.atr2 RANGE ξ⇒ juncao por abrangencia
T1.atr1 NEAR T2.atr2 STOP AFTER k ⇒ juncao pelos k-vizinhosmais proximos
T1.atr1 NEAR ANY T2.atr2 STOP AFTER k ⇒ juncao dos k-paresde vizinhos mais proximos
Maria Camila N. Barioni (UFABC) Palestra PosComp 42 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Sintaxe basica para expressar juncoes por similaridade na clausulaWHERE:
<tabela1>‘.’<atributo1> NEAR [ANY] <tabela2>‘.’<atributo2>
[STOP AFTER <k >] [RANGE <ξ>]
Tipos de construcoes:
T1.atr1 NEAR T2.atr2 RANGE ξ⇒ juncao por abrangencia
T1.atr1 NEAR T2.atr2 STOP AFTER k ⇒ juncao pelos k-vizinhosmais proximos
T1.atr1 NEAR ANY T2.atr2 STOP AFTER k ⇒ juncao dos k-paresde vizinhos mais proximos
Maria Camila N. Barioni (UFABC) Palestra PosComp 42 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Exemplo de juncao por similaridade:
São PauloRio de Janeiro
Vitória
Belo Horizonte
ξ
ξ
ξ
ξ
11.0=ξ
CidadeBRCapitalSE>< ξ(),dRq
L 2
Maria Camila N. Barioni (UFABC) Palestra PosComp 43 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Exemplo de juncao por similaridade:
São PauloRio de Janeiro
Vitória
Belo Horizonte
ξ
ξ
ξ
ξ
11.0=ξ
CidadeBRCapitalSE>< ξ(),dRq
L 2
SELECT * FROM CapitalSE, CidadeBRWHERE CapitalSE.Coordenada NEAR
CidadeBR.Coordenada RANGE 0.11;
Maria Camila N. Barioni (UFABC) Palestra PosComp 43 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Sintaxe para expressar juncoes por similaridade na clausula FROM:
<tabela1> {RANGE|NEAREST|CLOSEST} JOIN <tabela2>
ON <nome atr complexo1> {NEAR|FAR}<nome atr complexo2>
[STOP AFTER <k >] [RANGE <ξ>]
Maria Camila N. Barioni (UFABC) Palestra PosComp 44 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Sintaxe para expressar juncoes por similaridade na clausula FROM:
<tabela1> {RANGE|NEAREST|CLOSEST} JOIN <tabela2>
ON <nome atr complexo1> {NEAR|FAR}<nome atr complexo2>
[STOP AFTER <k >] [RANGE <ξ>]
Maria Camila N. Barioni (UFABC) Palestra PosComp 44 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Sintaxe para expressar operacoes de agrupamento por similaridade:
Como resultado do processo de deteccao de agrupamentos
relacao de agrupamentos encontrados⇒ Cluster
relacao que associa cada objeto do conjunto de dados ao objetocentral de seu agrupamento⇒ Clustering
Exemplos:
Para mostrar os agrupamentos de cada instancia do atributo Foto databela Paisagem resultantes do processo Pam FP
SELECT * FROM Clustering(Pam FP);
Para mostrar todos os agrupamentos de um atributo Foto resultantesdo processo Pam FP
SELECT * FROM Cluster(Pam FP);
Maria Camila N. Barioni (UFABC) Palestra PosComp 45 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Sintaxe para expressar operacoes de agrupamento por similaridade:
Como resultado do processo de deteccao de agrupamentos
relacao de agrupamentos encontrados⇒ Cluster
relacao que associa cada objeto do conjunto de dados ao objetocentral de seu agrupamento⇒ Clustering
Exemplos:
Para mostrar os agrupamentos de cada instancia do atributo Foto databela Paisagem resultantes do processo Pam FP
SELECT * FROM Clustering(Pam FP);
Para mostrar todos os agrupamentos de um atributo Foto resultantesdo processo Pam FP
SELECT * FROM Cluster(Pam FP);
Maria Camila N. Barioni (UFABC) Palestra PosComp 45 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Para parametrizar as operacoes de agrupamento por similaridade epreciso definir:
1 A metrica que deve ser utilizada
2 O numero de agrupamentos k
3 Qual algoritmo de deteccao de agrupamentos utilizar
Sintaxe:
SET CLUSTERING <nome processo>
METHOD <nome metodo>,
METRIC <nome metrica>,
K <valor inteiro>
ON <nome tabela>.<nome atributo>;
Maria Camila N. Barioni (UFABC) Palestra PosComp 46 / 67
Suportando Consultas por Similaridade em SQLEspecificar consultas
Para parametrizar as operacoes de agrupamento por similaridade epreciso definir:
1 A metrica que deve ser utilizada
2 O numero de agrupamentos k
3 Qual algoritmo de deteccao de agrupamentos utilizar
Sintaxe:
SET CLUSTERING <nome processo>
METHOD <nome metodo>,
METRIC <nome metrica>,
K <valor inteiro>
ON <nome tabela>.<nome atributo>;
Maria Camila N. Barioni (UFABC) Palestra PosComp 46 / 67
Suportando Consultas por Similaridade em SQL
A sintaxe apresentada permite
Combinar predicados por similaridade
entre sicom predicados tradicionais
Consultar por similaridade qualquer conjunto de objetos complexospara o qual seja possıvel definir uma medida de similaridade
domınio MONOLITHICdomınio PARTICULATE
Otimizar consultas por similaridade
Especificar consultas sobre o resultado de processos de agrupamentopor similaridade
⇓baixo impacto na sintaxe da linguagem
Maria Camila N. Barioni (UFABC) Palestra PosComp 47 / 67
Suportando Consultas por Similaridade em SQL
A sintaxe apresentada permite
Combinar predicados por similaridade
entre sicom predicados tradicionais
Consultar por similaridade qualquer conjunto de objetos complexospara o qual seja possıvel definir uma medida de similaridade
domınio MONOLITHICdomınio PARTICULATE
Otimizar consultas por similaridade
Especificar consultas sobre o resultado de processos de agrupamentopor similaridade
⇓baixo impacto na sintaxe da linguagem
Maria Camila N. Barioni (UFABC) Palestra PosComp 47 / 67
Suportando Consultas por Similaridade em SQL
A sintaxe apresentada permite
Combinar predicados por similaridade
entre sicom predicados tradicionais
Consultar por similaridade qualquer conjunto de objetos complexospara o qual seja possıvel definir uma medida de similaridade
domınio MONOLITHICdomınio PARTICULATE
Otimizar consultas por similaridade
Especificar consultas sobre o resultado de processos de agrupamentopor similaridade
⇓baixo impacto na sintaxe da linguagem
Maria Camila N. Barioni (UFABC) Palestra PosComp 47 / 67
Suportando Consultas por Similaridade em SQL
A sintaxe apresentada permite
Combinar predicados por similaridade
entre sicom predicados tradicionais
Consultar por similaridade qualquer conjunto de objetos complexospara o qual seja possıvel definir uma medida de similaridade
domınio MONOLITHICdomınio PARTICULATE
Otimizar consultas por similaridade
Especificar consultas sobre o resultado de processos de agrupamentopor similaridade
⇓baixo impacto na sintaxe da linguagem
Maria Camila N. Barioni (UFABC) Palestra PosComp 47 / 67
Suportando Consultas por Similaridade em SQL
A sintaxe apresentada permite
Combinar predicados por similaridade
entre sicom predicados tradicionais
Consultar por similaridade qualquer conjunto de objetos complexospara o qual seja possıvel definir uma medida de similaridade
domınio MONOLITHICdomınio PARTICULATE
Otimizar consultas por similaridade
Especificar consultas sobre o resultado de processos de agrupamentopor similaridade
⇓baixo impacto na sintaxe da linguagem
Maria Camila N. Barioni (UFABC) Palestra PosComp 47 / 67
Suportando Consultas por Similaridade em SQL
A sintaxe apresentada permite
Combinar predicados por similaridade
entre sicom predicados tradicionais
Consultar por similaridade qualquer conjunto de objetos complexospara o qual seja possıvel definir uma medida de similaridade
domınio MONOLITHICdomınio PARTICULATE
Otimizar consultas por similaridade
Especificar consultas sobre o resultado de processos de agrupamentopor similaridade
⇓baixo impacto na sintaxe da linguagem
Maria Camila N. Barioni (UFABC) Palestra PosComp 47 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 48 / 67
Algoritmo PAM-SLIM
Algoritmo desenvolvido:
PAM-SLIM
Melhora a eficiencia dos algoritmos de agrupamento baseados nok-medoid
Utilizando MAM para selecionar um sub-conjunto de objetos relevantes
Obtem agrupamentos com qualidade comparavel
Maria Camila N. Barioni (UFABC) Palestra PosComp 49 / 67
Algoritmo PAM-SLIM
Algoritmo desenvolvido:
PAM-SLIM
Melhora a eficiencia dos algoritmos de agrupamento baseados nok-medoid
Utilizando MAM para selecionar um sub-conjunto de objetos relevantes
Obtem agrupamentos com qualidade comparavel
Maria Camila N. Barioni (UFABC) Palestra PosComp 49 / 67
Algoritmo PAM-SLIM
Algoritmo desenvolvido:
PAM-SLIM
Melhora a eficiencia dos algoritmos de agrupamento baseados nok-medoid
Utilizando MAM para selecionar um sub-conjunto de objetos relevantes
Obtem agrupamentos com qualidade comparavel
Maria Camila N. Barioni (UFABC) Palestra PosComp 49 / 67
Algoritmo PAM-SLIM
Estrategia:
Realiza uma amostragem nos dados considerando certascaracterısticas dos MAM (Slim-tree)
Divide o espaco de dados hierarquicamente em regioes atribuindo umrepresentante para cada regiao
Os centros dos nos podem ser vistos como centros naturais das regioesque eles representam
O centro de uma sub-arvore pode ser considerado como centro demassa dos objetos armazenados nela
⇓Apenas os objetos de um determinado nıvel podem ser consideradospara a realizacao do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 50 / 67
Algoritmo PAM-SLIM
Estrategia:
Realiza uma amostragem nos dados considerando certascaracterısticas dos MAM (Slim-tree)
Divide o espaco de dados hierarquicamente em regioes atribuindo umrepresentante para cada regiao
Os centros dos nos podem ser vistos como centros naturais das regioesque eles representam
O centro de uma sub-arvore pode ser considerado como centro demassa dos objetos armazenados nela
⇓Apenas os objetos de um determinado nıvel podem ser consideradospara a realizacao do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 50 / 67
Algoritmo PAM-SLIM
Estrategia:
Realiza uma amostragem nos dados considerando certascaracterısticas dos MAM (Slim-tree)
Divide o espaco de dados hierarquicamente em regioes atribuindo umrepresentante para cada regiao
Os centros dos nos podem ser vistos como centros naturais das regioesque eles representam
O centro de uma sub-arvore pode ser considerado como centro demassa dos objetos armazenados nela
⇓Apenas os objetos de um determinado nıvel podem ser consideradospara a realizacao do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 50 / 67
Algoritmo PAM-SLIM
Estrategia:
Realiza uma amostragem nos dados considerando certascaracterısticas dos MAM (Slim-tree)
Divide o espaco de dados hierarquicamente em regioes atribuindo umrepresentante para cada regiao
Os centros dos nos podem ser vistos como centros naturais das regioesque eles representam
O centro de uma sub-arvore pode ser considerado como centro demassa dos objetos armazenados nela
⇓Apenas os objetos de um determinado nıvel podem ser consideradospara a realizacao do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 50 / 67
Algoritmo PAM-SLIM
Estrategia:
Realiza uma amostragem nos dados considerando certascaracterısticas dos MAM (Slim-tree)
Divide o espaco de dados hierarquicamente em regioes atribuindo umrepresentante para cada regiao
Os centros dos nos podem ser vistos como centros naturais das regioesque eles representam
O centro de uma sub-arvore pode ser considerado como centro demassa dos objetos armazenados nela
⇓
Apenas os objetos de um determinado nıvel podem ser consideradospara a realizacao do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 50 / 67
Algoritmo PAM-SLIM
Estrategia:
Realiza uma amostragem nos dados considerando certascaracterısticas dos MAM (Slim-tree)
Divide o espaco de dados hierarquicamente em regioes atribuindo umrepresentante para cada regiao
Os centros dos nos podem ser vistos como centros naturais das regioesque eles representam
O centro de uma sub-arvore pode ser considerado como centro demassa dos objetos armazenados nela
⇓Apenas os objetos de um determinado nıvel podem ser consideradospara a realizacao do agrupamento
Maria Camila N. Barioni (UFABC) Palestra PosComp 50 / 67
Algoritmo PAM-SLIM
Estrategia:
Uma Slim-tree representa a divisao do espaco de dados com umagranularidade que cresce da raiz para as folhas
Questao:
Qual o nıvel da arvore possui informacoes sobre a distribuicao dosdados suficientes para gerar um agrupamento mais rapido e comqualidade razoavel?
Maria Camila N. Barioni (UFABC) Palestra PosComp 51 / 67
Algoritmo PAM-SLIM
Estrategia:
Uma Slim-tree representa a divisao do espaco de dados com umagranularidade que cresce da raiz para as folhas
Questao:
Qual o nıvel da arvore possui informacoes sobre a distribuicao dosdados suficientes para gerar um agrupamento mais rapido e comqualidade razoavel?
Maria Camila N. Barioni (UFABC) Palestra PosComp 51 / 67
Algoritmo PAM-SLIM
s1
s1
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s6
s6
s3
s3
s3
s3
s10
s10
s10
s10
s12
s12
s13
s13
s8
s8
s8
s8
s8
s8
s9
s9
s9
s9
s11
s11
s11
s11
s4
s4
s15
s15
s14
s14
s14
s14
nó raiznó raiz
s7
s7
s5
s5
s6
s6
s12
s12
s13
s13
s4
s4
s15
s15
nós
índice
nós
índice
nós
folha
nós
folha
Maria Camila N. Barioni (UFABC) Palestra PosComp 52 / 67
Algoritmo PAM-SLIM
s1
s1
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s6
s6
s3
s3
s3
s3
s10
s10
s10
s10
s12
s12
s13
s13
s8
s8
s8
s8
s8
s8
s9
s9
s9
s9
s11
s11
s11
s11
s4
s4
s15
s15
s14
s14
s14
s14
nó raiznó raiz
s7
s7
s5
s5
s6
s6
s12
s12
s13
s13
s4
s4
s15
s15
nós
índice
nós
índice
nós
folha
nós
folha
⇐
Maria Camila N. Barioni (UFABC) Palestra PosComp 52 / 67
Algoritmo PAM-SLIM
s1
s1
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s6
s6
s3
s3
s3
s3
s10
s10
s10
s10
s12
s12
s13
s13
s8
s8
s8
s8
s8
s8
s9
s9
s9
s9
s11
s11
s11
s11
s4
s4
s15
s15
s14
s14
s14
s14
nó raiznó raiz
s7
s7
s5
s5
s6
s6
s12
s12
s13
s13
s4
s4
s15
s15
nós
índice
nós
índice
nós
folha
nós
folha⇐Maria Camila N. Barioni (UFABC) Palestra PosComp 52 / 67
Algoritmo PAM-SLIM
s1
s1
s1
s1
s1
s1
s1
s1
s2
s2
s2
s2
s2
s2
s7
s7
s7
s7
s7
s7
s5
s5
s5
s5
s6
s6
s6
s6
s6
s6
s3
s3
s3
s3
s10
s10
s10
s10
s12
s12
s13
s13
s8
s8
s8
s8
s8
s8
s9
s9
s9
s9
s11
s11
s11
s11
s4
s4
s15
s15
s14
s14
s14
s14
nó raiznó raiz
s7
s7
s5
s5
s6
s6
s12
s12
s13
s13
s4
s4
s15
s15
nós
índice
nós
índice
nós
folha
nós
folha
⇐
Maria Camila N. Barioni (UFABC) Palestra PosComp 52 / 67
Algoritmo PAM-SLIM
Algoritmo:
Pre-processamentoEscolha dos parametros para a construcao da arvore
Tamanho de paginaPolıtica de escolha de sub-arvore (ChooseSubtree)
Construcao da arvore
Inicializacao
Selecao do nıvel da arvoreAtribuicao dos objetos do nıvel selecionado ao conjunto de objetos queserao utilizados no processo de agrupamento
Agrupamento
Aplicacao do PAM sobre a amostra obtida no passo anteriorAtribuicao de cada objeto do conjunto de dados todo aos medoidesselecionados pelo PAM
Maria Camila N. Barioni (UFABC) Palestra PosComp 53 / 67
Algoritmo PAM-SLIM
Algoritmo:
Pre-processamentoEscolha dos parametros para a construcao da arvore
Tamanho de paginaPolıtica de escolha de sub-arvore (ChooseSubtree)
Construcao da arvore
Inicializacao
Selecao do nıvel da arvoreAtribuicao dos objetos do nıvel selecionado ao conjunto de objetos queserao utilizados no processo de agrupamento
Agrupamento
Aplicacao do PAM sobre a amostra obtida no passo anteriorAtribuicao de cada objeto do conjunto de dados todo aos medoidesselecionados pelo PAM
Maria Camila N. Barioni (UFABC) Palestra PosComp 53 / 67
Algoritmo PAM-SLIM
Algoritmo:
Pre-processamentoEscolha dos parametros para a construcao da arvore
Tamanho de paginaPolıtica de escolha de sub-arvore (ChooseSubtree)
Construcao da arvore
Inicializacao
Selecao do nıvel da arvoreAtribuicao dos objetos do nıvel selecionado ao conjunto de objetos queserao utilizados no processo de agrupamento
Agrupamento
Aplicacao do PAM sobre a amostra obtida no passo anteriorAtribuicao de cada objeto do conjunto de dados todo aos medoidesselecionados pelo PAM
Maria Camila N. Barioni (UFABC) Palestra PosComp 53 / 67
Algoritmo PAM-SLIM
Algoritmo:
Pre-processamentoEscolha dos parametros para a construcao da arvore
Tamanho de paginaPolıtica de escolha de sub-arvore (ChooseSubtree)
Construcao da arvore
Inicializacao
Selecao do nıvel da arvoreAtribuicao dos objetos do nıvel selecionado ao conjunto de objetos queserao utilizados no processo de agrupamento
Agrupamento
Aplicacao do PAM sobre a amostra obtida no passo anteriorAtribuicao de cada objeto do conjunto de dados todo aos medoidesselecionados pelo PAM
Maria Camila N. Barioni (UFABC) Palestra PosComp 53 / 67
Algoritmo PAM-SLIMResultados alcancados
Algoritmos considerados
PAM, CLARA, CLARANS, PAM-SLIM-MD e PAM-SLIM-MO
Medidas utilizadas
Qualidade
Distancia media do agrupamento resultante
Eficiencia computacional
Numero de calculos de distancia
Conjuntos de dados considerados
Oito sinteticos e um real
Maria Camila N. Barioni (UFABC) Palestra PosComp 54 / 67
Algoritmo PAM-SLIMResultados alcancados
Mostra dos resultados obtidos
Tempo de execucao do PAM, CLARANS, CLARA e PAM-SLIM(horas:minutos:segundos)
Conjunto PAM CLARANS CLARA PAM-SLIM- PAM-SLIM-de dados MD MO
Sint10 5k 00:42:48 00:01:31 00:00:01 00:00:04 00:00:02Sint10 10k 07:49:42 00:07:18 00:00:06 00:00:10 00:00:05Sint10 15k 21:27:41 00:23:03 00:00:20 00:00:33 00:00:15Sint10 20k 43:44:47 00:44:10 00:00:47 00:01:14 00:00:39
Maria Camila N. Barioni (UFABC) Palestra PosComp 55 / 67
Algoritmo PAM-SLIMResultados alcancados
Mostra dos resultados obtidos
Tempo de execucao do PAM, CLARANS, CLARA e PAM-SLIM(horas:minutos:segundos)
Conjunto PAM CLARANS CLARA PAM-SLIM- PAM-SLIM-de dados MD MO
Sint10 5k 00:42:48 00:01:31 00:00:01 00:00:04 00:00:02Sint10 10k 07:49:42 00:07:18 00:00:06 00:00:10 00:00:05Sint10 15k 21:27:41 00:23:03 00:00:20 00:00:33 00:00:15Sint10 20k 43:44:47 00:44:10 00:00:47 00:01:14 00:00:39
Nota: a diminuicao da qualidade do agrupamento variou apenas entre7,4% e 11,8%
Maria Camila N. Barioni (UFABC) Palestra PosComp 55 / 67
Algoritmo PAM-SLIM
Estrategia de otimizacao
Leva em consideracao a vizinhanca dos medoides retornados no passode agrupamento para refinar o processamento do mesmo
Propriedade interessante ⇒ seu custo e funcao da quantidade devizinhos que se solicita explorar
Nos experimentos realizados: agrupamentos de qualidade no maximo7,6% inferior, mas que sao obtidos ate 1.500 vezes mais rapidamente
medóides PAM-SLIM
medóides PAM
elementos do conj. de dados
Maria Camila N. Barioni (UFABC) Palestra PosComp 56 / 67
Algoritmo PAM-SLIMConsideracoes Finais
A estrategia adotada pelo algoritmo
Pode ser eficientemente aplicada para agrupar tanto conjuntos dedados multi-dimensionais quanto adimensionais (armazenados emdisco)
Apresenta uma relacao adequada de custo-benefıcio entre tempo deexecucao e qualidade do agrupamento obtido
Maria Camila N. Barioni (UFABC) Palestra PosComp 57 / 67
Algoritmo PAM-SLIMConsideracoes Finais
A estrategia adotada pelo algoritmo
Pode ser eficientemente aplicada para agrupar tanto conjuntos dedados multi-dimensionais quanto adimensionais (armazenados emdisco)
Apresenta uma relacao adequada de custo-benefıcio entre tempo deexecucao e qualidade do agrupamento obtido
Maria Camila N. Barioni (UFABC) Palestra PosComp 57 / 67
Algoritmo PAM-SLIMConsideracoes Finais
A estrategia adotada pelo algoritmo
Pode ser eficientemente aplicada para agrupar tanto conjuntos dedados multi-dimensionais quanto adimensionais (armazenados emdisco)
Apresenta uma relacao adequada de custo-benefıcio entre tempo deexecucao e qualidade do agrupamento obtido
Maria Camila N. Barioni (UFABC) Palestra PosComp 57 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 58 / 67
SIREN
Arquitetura do SIREN
Base daAplicação
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SQL
SGBDR
Dicionáriode Dados
SIREN
Extrator deCaracterísticas
Indexador(Arboretum)
Interpretador de Comandos
Programa de Aplicação
Método de AcessoMétrico (MAM)
Maria Camila N. Barioni (UFABC) Palestra PosComp 59 / 67
Prototipo SIREN
Alem de adicionar novas construcoes na linguagem SQL foi necessario
Estender o dicionario de dados do SGBD para armazenar informacoescomo:
quais extratores de caracterısticas sao utilizados nas metricas
quais atributos tradicionais compoem cada atributo PARTICULATE
quais metricas estao disponıveis para cada domınio complexo
quais sao os atributos de domınios complexos armazenados em cadarelacao
quais metricas estao associadas a cada atributo complexo
Considerar os requisitos especiais de armazenamento dos dados dostipos STILLIMAGE e AUDIO
e preciso armazenar tambem as caracterısticas associadas a eles
Maria Camila N. Barioni (UFABC) Palestra PosComp 60 / 67
Prototipo SIREN
Alem de adicionar novas construcoes na linguagem SQL foi necessario
Estender o dicionario de dados do SGBD para armazenar informacoescomo:
quais extratores de caracterısticas sao utilizados nas metricas
quais atributos tradicionais compoem cada atributo PARTICULATE
quais metricas estao disponıveis para cada domınio complexo
quais sao os atributos de domınios complexos armazenados em cadarelacao
quais metricas estao associadas a cada atributo complexo
Considerar os requisitos especiais de armazenamento dos dados dostipos STILLIMAGE e AUDIO
e preciso armazenar tambem as caracterısticas associadas a eles
Maria Camila N. Barioni (UFABC) Palestra PosComp 60 / 67
Prototipo SIREN
Alem de adicionar novas construcoes na linguagem SQL foi necessario
Estender o dicionario de dados do SGBD para armazenar informacoescomo:
quais extratores de caracterısticas sao utilizados nas metricas
quais atributos tradicionais compoem cada atributo PARTICULATE
quais metricas estao disponıveis para cada domınio complexo
quais sao os atributos de domınios complexos armazenados em cadarelacao
quais metricas estao associadas a cada atributo complexo
Considerar os requisitos especiais de armazenamento dos dados dostipos STILLIMAGE e AUDIO
e preciso armazenar tambem as caracterısticas associadas a eles
Maria Camila N. Barioni (UFABC) Palestra PosComp 60 / 67
Prototipo SIREN
Esquema de armazenamento dos novos tipos de dados complexos
ID
Imagem
C A
C z
2050
...
...
...
...Cara
cterís
ticas
extraíd
as daim
agem
BLOB
x1
101 xyz 1001...
...
...............
STILLIMAGE
x2 x3 xn
2050
AUDIO
ID
AUDIO
C A
C z
1001
...
...
...
...Cara
cterís
ticas
extraíd
as doáud
io
BLOB
y1
22
...
y2
125
...
y3
50.5
...
y4
75
...
y5
33
... ...
ym
12.8
...
...
...
PARTICULATE
Maria Camila N. Barioni (UFABC) Palestra PosComp 61 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Comando SELECT enviado pela aplicacao:
SELECT Fotografo, Foto
FROM Paisagem
WHERE Foto NEAR ‘D:\FotosPaisagem\img09.jpg’ [C5.1]BY Textura STOP AFTER 5;
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
2
consulta à base da aplicação
e ao dicionário de dados do
SIREN
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
2 3consulta à base da aplicação
e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
42 3
imagemde consultaconsulta à base
da aplicação e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
4 52 3
imagemde consulta
vetor de característicasconsulta à base
da aplicação e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
4 5 62 3
imagemde consulta
vetor de características
vetor de característicasda imagem de
consulta e parâmetros da
operação
consulta à base da aplicação
e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
4 5 6 72 3
imagemde consulta
vetor de características
identificadoresdas imagens
vetor de característicasda imagem de
consulta e parâmetros da
operação
consulta à base da aplicação
e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
4 5 6 72 3
8
imagemde consulta
vetor de características
identificadoresdas imagens
vetor de característicasda imagem de
consulta e parâmetros da
operaçãocomandoreescrito
consulta à base da aplicação
e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1
4 5 6 72 3
8 9
imagemde consulta
vetor de características
identificadoresdas imagens
vetor de característicasda imagem de
consulta e parâmetros da
operaçãocomandoreescrito
resultado final do comando
consulta à base da aplicação
e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Base da Aplicação
Método de Acesso Métrico (MAM)
SIREN - SImilarity Retrieval ENgine
SQL Padrão/SQL Estendido
SGBDR
Dicionário de Dados
SIREN
Extrator de Características
Interpretador de Comandos
Programa de Aplicação
1 10
resultado final do comando
4 5 6 72 3
8 9
imagemde consulta
vetor de características
identificadoresdas imagens
vetor de característicasda imagem de
consulta e parâmetros da
operaçãocomandoreescrito
resultado final do comando
consulta à base da aplicação
e ao dicionário de dados do
SIREN
resultado da consulta
Indexador (Arboretum)
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Prototipo SIRENExemplo do processamento de uma consulta
Comando SELECT enviado pela aplicacao:
SELECT Fotografo, Foto
FROM Paisagem
WHERE Foto NEAR ‘D:\FotosPaisagem\img09.jpg’ [C5.1]BY Textura STOP AFTER 5;
Comando SELECT reescrito pelo SIREN:
SELECT Fotografo, IPV$Paisagem Foto.Image AS Foto
FROM Paisagem JOIN IPV$Paisagem Foto
ON Paisagem.Foto = IPV$Paisagem Foto.Image id
WHERE Foto IN ( 7896, 7912, 9669, 9668, 9675 );
Maria Camila N. Barioni (UFABC) Palestra PosComp 62 / 67
Pontos que ainda precisam ser explorados...
Qualidade semantica dos resultados retornados por uma consulta
Eficiencia de algoritmos de consulta
Flexibilidade na arquitetura dos sistemas disponıveis
...
Maria Camila N. Barioni (UFABC) Palestra PosComp 63 / 67
Roteiro
1 Introducao
2 Conceitos Fundamentais
3 Suportando Consultas por Similaridade em SQL
4 Algoritmo PAM-SLIM
5 Prototipo SIREN
6 Referencias
Maria Camila N. Barioni (UFABC) Palestra PosComp 64 / 67
Referencias
BARIONI, M. C. N.; RAZENTE, H.; TRAINA, A. J. M.; TRAINA JR, C.“SIREN: A Similarity Retrieval Engine For Complex Data” (2006). In:Demonstration Session of the 32nd International Conference on Very LargeData Bases (VLDB), v. 1., p. 1155-1158, Seul.
BARIONI, M. C. N.; RAZENTE, H.; TRAINA, A. J. M.; TRAINA JR, C.“Accelerating k-medoid-based algorithms through metric access methods”.Journal of Systems and Software, v. 81/3, p. 343-355, marco de 2008.Disponıvel online em 05 de julho de 2007. DOI:http://dx.doi.org/10.1016/j.jss.2007.06.019
BARIONI, M. C. N.; RAZENTE, H. L.; TRAINA, A. J. M.; TRAINA JR, C.
“Seamlessly integrating similarity queries in SQL”. Software, Practice &
Experience, v. 39, p. 355-384, 2009. Disponıvel online em 27 de agosto de
2008. DOI: http://dx.doi.org/10.1016/j.jss.2007.06.019
Maria Camila N. Barioni (UFABC) Palestra PosComp 65 / 67
Referencias
BARIONI, M. C. N.; KASTER, D. ; RAZENTE, H. L.; TRAINA, A. J. M.;TRAINA-JR, C. “Querying Multimedia Data by Similarity in RelationalDBMS”. In: Li Yan (Northeastern University, China); Zongmin Ma(Northeastern University, China). (Org.). Advanced Database QuerySystems: Techniques, Applications and Technologies. : IGI Global, 2011, v., p. 1-33.
BARIONI, M. C. N. “Operacoes de consulta por similaridade em grandesbases de dados complexos” (2006). Tese de Doutorado, ICMC/USP, SaoCarlos, 145p. Disponıvel online: http://www.teses.usp.br/.
Maria Camila N. Barioni (UFABC) Palestra PosComp 66 / 67
Manipulacao de dados multimıdia em SGBD relacionais
Profa. Dra. Maria Camila Nardini [email protected]
Centro de Matematica Computacao e Cognicao - UFABC
Santo Andre11 de julho de 2011
Maria Camila N. Barioni (UFABC) Palestra PosComp 67 / 67