Begrepene som mangler

Entrada: Grupo de consultas �, raio de abrangência � e nó ����

Saída: Resultado � contendo listas de sequências com distância menor ou igual que �

para as respectivas consultas

1: _{� ⊂ � ⊂ ¶♢} ◁ Inicializa pilha �

2: �G ⊂ cria container(�, �) ◁ Cria container para um grupo de consultas

3: insere pilha(�, ����)

4: enquanto pilha vazia(� ) é falso faça 5: _{�ó ⊂ remove pilha(� )}

6: se �ó é diretório então

7: para todo ��� ∈ objetos(�ó) tal que container(���) sobrepõe �G faça

8: insere pilha(�, filho(���)) 9: senão se �ó é folha então

10: para todo ��� ∈ objetos(�ó) faça

11: para 1 ⊘ � ⊘ ♣�♣ faça

12: se ����(�i, sequência(���)) ⊘ � então

13: Insira sequência(���) em �i

14: retorna � ◁ Retorna listas de sequências

Para isso é necessário que a representação forneça uma medida lower bounding, como apresentado no Capítulo 2. Dessa maneira, primeiramente, indexam-se referências para as sequências originais utilizando-se as representações como chaves. Posteriormente, em uma busca por abrangência, buscam-se referências de sequências candidatas por meio da representação reduzida da sequência de consulta e, posteriormente, aplica-se uma etapa de pós-processamento para recuperar e descartar aquelas que não fazem parte de algum resultado.

6.2 Estratégias de Agrupamento de Consultas

Nesta seção são apresentadas cinco estratégias de agrupamento de consulta para realização de buscas por similaridade em lote. Essas estratégias foram adaptadas a partir de trabalhos relacionados que agruparam sequências em outros contextos, tais como, na etapa de indexação de subsequências (FALOUTSOS; RANGANATHAN; MANOLOPOULOS, 1994). A primeira estratégia é aquela que cria somente um grupo contendo todas as sequências de consulta. Neste trabalho, essa estratégia é referenciada como estratégia

Single Grouping (SG). Além dessa estratégia, avaliaram-se outras quatro, descritas nas

seções seguintes, para verificar a importância do método de agrupamento de consultas para o processamento de consultas por similaridade em lote, sendo elas: � -Random

Grouping (NRG), Maximum Capacity Grouping (MCG), Adaptive Grouping (AG), �- Medoids Grouping (KMG).

6.2.1 Estratégia N-Random Grouping

Dados um conjunto de sequências de consulta e uma quantidade de grupos � , a estratégia � -Random Grouping (NRG) escolhe aleatoriamente � sequências para iniciar grupos e depois insere as sequências restantes nos grupos cujas sequências sejam as mais similares. A escolha do grupo de uma sequência é feita da seguinte maneira: para cada um dos � grupos, mantém-se um container que delimita suas sequências, inicialmente apenas uma sequência escolhida aleatoriamente. Posteriormente, cada consulta restante é inserida no grupo cujo container associado seja o melhor, expandindo-o se necessário. O melhor container é aquele que abrange totalmente a nova sequência ou, caso não exista, é aquele que ofereça o menor aumento de seu volume. Em caso de empate, escolhe-se aquele que tenha o menor volume.

6.2.2 Estratégia Maximum Capacity Grouping

A estratégia Maximum Capacity Grouping (MCG) limita a quantidade de sequências pertencentes a um grupo em vez de escolher uma quantidade fixa de grupos. Nessa estratégia não se utilizam heurísticas para formar grupos mais compactos. Dado um conjunto de sequências de consulta e a quantidade máxima � de sequências, primeiramente cria-se um novo grupo, e, posteriormente, tenta-se inserir as próximas � sequências. Caso ainda existam sequências sem grupo, cria-se um novo grupo e repete-se o processo. Esse processo é realizado até que todas as sequências de consulta pertençam a algum grupo.

6.2.3 Estratégia Adaptive Grouping

Em (FALOUTSOS; RANGANATHAN; MANOLOPOULOS, 1994), os autores empre- garam uma técnica para agrupar pontos �-dimensionais em Minimum Bounding Rectan-

gle (MBR) durante a operação de inserção em �-Trees. Dado um conjunto de pontos,

primeiramente, essa técnica cria um novo MBR. Depois, é verificado se os pontos restantes devem ser incluídos no último MBR criado ou em ou novo MBR. Para isso, calcula-se o custo marginal ��R-tree =︀di=1(�i+ 0.5)/�, onde �i é a largura da �-ésima dimensão de

um MBR e � é a quantidade de pontos no MBR. Dessa maneira, inclui-se um próximo ponto no MBR atual caso o custo marginal após a sua inserção seja inferior ou igual ao custo marginal anterior e, caso contrário, insere-se em um novo MBR.

A estratégia Adaptive Grouping (AG) é uma adaptação da técnica utilizada em (FA- LOUTSOS; RANGANATHAN; MANOLOPOULOS, 1994) para o contexto de agrupa- mento de sequências. Diferente da técnica anterior, na estratégia AG, verificam-se todos os containers criados até o momento para a inserção de uma nova sequência de consulta e não somente o último criado. Além disso, no caso de � -Trees, o custo marginal é dado por ��M -tree = (� + 0.5)d/�, onde � é o raio de uma esfera, � é a dimensão suposta do

82 Capítulo 6. Agrupamento de Sequências Numéricas para Buscas por Similaridade em Lote

espaço e � a quantidade de sequências nesse grupo. Esse custo é justificável pois seu valor cresce proporcionalmente ao volume da esfera, assim como o custo marginal ��R-trees.

O Algoritmo 21 implementa a estratégia AG. Dado um conjunto de sequências de consulta � = ⟨�1, �2, . . . , �N⟩, retornam-se grupos de sequências similares de modo que

não seja possível adicionar mais sequências a algum grupo sem que seu custo marginal aumente. Primeiramente, inicializam-se um conjunto de grupos � e um conjunto de

containers �. Posteriormente, cria-se o primeiro grupo contendo �1 e adiciona-se a �.

Depois, a partir de �1 cria-se um novo container, associado a �1, e insere-se em �. Para

cada sequência restante �i, avalia-se o custo marginal de cada container ao adicioná-la

a um dos grupos previamente criados. Se o custo marginal de um dos containers, após a sua expansão, for menor ou igual que seu custo marginal anterior, adiciona-se �i no

grupo correspondente e atualiza-se o seu container. Caso contrário, cria-se um novo grupo contendo �i e associa-se a um novo container criado a partir de �i. Esse procedimento é

realizado até que todas as sequências pertençam a algum grupo.

Algoritmo 21 Estratégia Adaptive Grouping