Recuperação de
dados por Conteúdo
Slim-Trees
Slim - Motivações
Método eficiente de armazenamento e
recuperação de informação por meio de
similaridade
 Informações não possuem relações de
ordem total

Métodos de acesso métrico
Função de dissimilaridade:
d(Oi, Oj)
 fixed query tree; mvp-tree; vp-tree; GNAT :
estáticas;
 M-Tree, Slim-tree: Dinâmicas

Consulta por abrangência
O = {O1, O2, ..., On} pertence a D
d()
Q?
r(Q)

range(Q, r(Q)) => Seleciona Oi
dentro da distancia r(Q) de Q

Encontre as estrelas que estão até 10 anos-luz
do Sol
Consulta k-NN
O = {O1, O2, ..., On} pertence a D
d()
Q?
K

K-NN(Q) => Seleciona os K
objetos mais próximos de Q

Selecione as 5 estrelas mais
próximas do Sol : 5-NN(Sol)
Slim-tree - Definição
Caetano Traina Jr. – ICMC/SC (2000)
 Estrutura dinâmica (permite inserções
após sua criação);
 Balanceada;
 Performance superior à M-trees
 Páginas (nós) de tamanho fixo, que
armazenam no máximo C objetos;
Slim-tree – Nós internos
• Sc: Objeto Centro da subárvore
apontada por Ptrc
•d(Sc, Srep): Distância entre Sc e o
objeto representado;
•Ptrc: Nó raiz da subárvore que contém
centro Sc;
•Rc: Raio de cobertura da região;
•#Ent: Número de nós contido em Ptrc
Slim-tree – Nós folha
•Sc: Objeto que o nó armazena
•Oid: Identificador do nó
•d(): Distancia entre Sc e o objeto central
Slim-tree - Exemplo
Slim-tree - Distâncias
Slim-tree - Inserção
A partir da raiz, busca nó que possa
receber objeto
 Se não encontra este nó

 selecionar
nó com centro mais próximo do
objeto

Se quantidade de nós > 1

Random | MidDist | Minoccup
Slim-tree - Splitting




Nó escolhido com taxa de ocupação máxima
Random: seleção aleatória de um par de objetos e
redistribuição dos outros objetos em função destes;
minMax: par de objetos que minimiza o raio de cobertura
da sub-árvore => O(C3)
MST: Remove o arco mais longo da arvore do caminho
mínimo => O(C2 log C)
Slim-trees - Sobreposição


Nós diferentes recaem sobre uma mesma
região => reduz performance nas buscas
Absolute-fat-factor: Calcula quantidade de
objetos cobertos por múltiplas regiões
 Não
permite o cálculo para arvores diferentes que
representam um mesmo domínio

Relative-fat-factor: Conta nós acessados para
responder a uma consulta
Slim-trees – Slim down
Análise dos fatores de sobreposição
permite aplicar algoritmo
 Reorganizar uma árvore já construída de
forma a otimizar as buscas e reduzir o
consumo de espaço em disco
