Information about Assessment Criteria

A MM-tree (Main Memory Metric-tree) (POLA et al., 2007) é um MAM dinâmico e foi desenvolvido visando atender a necessidade de responder rapidamente as consultas por similaridade sobre conjuntos de dados em espaços métricos que possam ser mantidos em memória primária.

Estrutura de Dados

A base de construção da estrutura MM-tree é recursivamente dividir o espaço em quatro regiões distintas utilizando dois elementos s1 e s2 (chamados de pivôs)

para representá-las. Cada elemento inserido si é associado a uma única região. A

e os pivôs representantes do nó como indicado na Tabela 2.1 onde r é a distância entre os pivôs, ou seja, r = d(s1, s2).

Tabela 2.1: MM-tree - Regiões do nó

d(si, s1) r d(si, s2) r Região < < I < ≥ II ≥ < III ≥ ≥ IV

Todos os nós da MM-tree têm a mesma estrutura, que é definida como segue:

Nó MM-Tree = [s1,s2, d(s1, s2), Ptr1, Ptr2, Ptr3, Ptr4]

Onde s1 e s2 são os pivôs, d(s1, s2) é a distância entre os pivôs e Ptr1, Ptr2,

Ptr3, Ptr4 são os ponteiros para as quatro regiões que armazenam os elementos

filhos no nó, determinadas pela Tabela 2.1. Cada nó possui apenas dois elementos, os mesmos que são utilizados como representantes de suas regiões.

Vale ainda observar que s1 e s2 não são os elementos e sim os vetores de

característica que os representam. Por exemplo, em imagens não serão indexados os pixels e sim o vetor da característica de interesse, por exemplo, o vetor contendo o histograma de cores.

Uma ilustração desta estrutura pode ser observada na Figura 2.5.

Na Figura 2.5, no plano superior pode-se observar a representação gráfica dos elementos no espaço, e no plano inferior pode-se observar a estrutura dos nós da MM-tree. Na representação gráfica do espaço verificamos os pivôs a e b e o raio

r entre eles, ou seja, a distância d(a,b). O raio centrado em cada pivô determina a

área circular de sua abrangência. A intersecção das áreas cobertas por cada pivô configura as regiões hierarquicamente subordinadas a estes pivôs conforme descrito na Tabela 2.1.

Na representação da estrutura de um nó MM-tree pode-se observar a hierarquia gerada, contendo no primeiro nível os pivôs a e b, o valor do raio r entre eles, ou seja, a distância d(a,b), e os ponteiros para as quatro regiões subordinadas. No segundo nível verificamos os nós correspondentes aos elementos filhos c, d, e, f,

g, e h.

Inserção

É importante observar que a MM-tree é uma estrutura dinâmica, e inserções podem ocorrer a qualquer momento.

A inserção de elementos na MM-tree sempre é feita apenas em nós folhas. A partir da raiz e utilizando a Tabela 2.1 de determinação de regiões, o algoritmo de inserção percorre a estrutura hierárquica procurando pelo nó apropriado para armazenar o novo elemento. Assim, a cada nó visitado, o algoritmo utiliza as informações armazenadas do nó para consultar a Tabela 2.1 e determinar qual caminho percorrer (i.e., qual região o elemento deve ser inserido e, portanto, qual sub-árvore percorrer). Este procedimento é executado até que se encontre um nó folha para a inserção. Caso o elemento já se encontre na estrutura o algoritmo de inserção é interrompido de maneira a evitar duplicidade de elementos.

Um fator a ser considerado em operações de inserção, principalmente em estruturas dinâmicas em que a inserção pode ser feita após a construção da hierarquia, é o controle do balanceamento da estrutura. As buscas em árvores desbalanceadas na altura produzem um comportamento imprevisível. Para isso, a MM-tree possui um algoritmo apropriado para manter a estrutura balanceada tanto quanto possível.

O algoritmo de semi-balanceamento da MM-tree atua somente nos nós em que a inserção irá ocorrer, ou seja, nos nós folha. A Figura 2.6 e a Figura 2.7 ilustram o funcionamento deste algoritmo.

Figura 2.6: MM-tree - Algoritmo de semi-balanceamento: Situação inicial

Figura 2.7: MM-tree: Algoritmo de semi-balanceamento: Situação final

O plano esquerdo da Figura 2.6 ilustra a inserção de um novo elemento – o elemento h - sem a aplicação do algoritmo de semi-balanceamento. Embora havendo espaço nos nós, o raio dos atuais pivôs determina (através da Tabela 2.1) que esta inserção crie um novo nível hierárquico na estrutura.

Na Figura 2.7, pode-se visualizar o resultado da aplicação do algoritmo de semi-balanceamento. Os pivôs a e b foram trocados pelos pivôs e e d. Os demais elementos foram realocados conforme a Tabela 2.1 de determinação de regiões e não foi mais necessária a criação de um novo nível hierárquico.

Quando houver espaço em nós irmãos, e for identificada a necessidade de criação de um novo nível hierárquico, o algoritmo executa uma análise combinatória de todos os elementos da hierarquia, determinando novos pivôs. Os pivôs são escolhidos de maneira a se evitar a criação de um novo nível hierárquico, determinando um melhor arranjo dos elementos. Se a análise combinatória não puder determinar um melhor arranjo, cria-se um novo nível hierárquico.

Busca

Além das consultas pontuais, a MM-tree responde às consultas Range Query

(RQ) e também às consultas K-vizinhos mais próximos (KNNQ). Esta seção

abordará estas consultas.

Os dois algoritmos de consulta se utilizam da mesma informação para determinar quais regiões intersectam a região de consulta. Esta intersecção é determinada através da Tabela 2.2.

Os parâmetros da consulta RQ são o elemento base para a consulta sq e o

raio rq. Em cada nó visitado, se a distância de sq ao pivô for menor que rq então o

pivô é adicionado ao conjunto da resposta. A seguir, o algoritmo visita as regiões, subordinadas ao pivô, em que há interseção do raio rq seguindo a Tabela 2.2 de

regiões do nó MM-tree.

Tabela 2.2: MM-tree - Determinação do caminho de busca

Região I (d(sq, s2) < rq + r) (d(sq, s1) < rq + r) Região II (d(sq, s2) + rq ≥ r) (d(sq, s1) < rq + r) Região III (d(sq, s2) < rq + r) (d(sq, s1) + rq ≥ r) Região IV (d(sq, s2) < rq ≥ r) (d(sq, s1) + rq ≥ r)

Na consulta KNNQ o raio de consulta é dinâmico. Os parâmetros desta consulta são o elemento base para a consulta sq, e a quantidade desejada k de

elementos mais próximos ao elemento base. O algoritmo trabalha com duas informações dinâmicas: o raio rq e uma lista de elementos que farão parte da

resposta. Inicia a partir da raiz da hierarquia com o valor de raio rq = ∞, e com lista

vazia. Cada vez que é encontrado um elemento mais próximo de sq, ou seja,

encontrado um elemento cuja distância esteja entre os K elementos mais próximos, o raio dinâmico é reduzido. Isso ocorre pela eliminação do elemento mais distante na lista (k-ésimo elemento) e a recomputação do raio com base no novo elemento

inserido na lista. O raio passa a ser a distância do elemento mais distante na lista ao elemento base. Assim como o algoritmo da consulta RQ, o algoritmo KNNQ também consulta a tabela de sobreposições em busca das intersecções que deve continuar percorrendo.