SUMÁRIO

1 Introdução

2 Objetivos do Trabalho 5

2.1 Estado da Arte

2.2 Algoritmos Paralelos

2.2.1 Modelo de Computação Paralela

3 Construção da Árvore 9

3.1 Construção da Árvore Local

3.1.1 Método Sort-Based

3.1.2 Método Median-Based

3.1.3 Método Bucket-Based

3.1.4 Resultados Experimentais da Literatura

3.2 Construção Paralela da Árvore para os log p Níveis

3.2.1 Método Sort-Based

3.2.2 Método Median-Based

3.2.3 Método Bucket-Based

3.2.4 Resultados Experimentais da Literatura

3.3 Construção Global da Árvore

3.4 Aplicações

4 Conclusões

Resumo

Árvore de busca binária multidimensional (abreviada por árvore k - d) é uma estrutura de dados usada para a organização e manipulação de dados espaciais. Esta estrutura de dados é usada em muitas aplicações, sendo que as principais são: particionamento de grafos, aplicações hierárquicas tais como dinâmica molecular e simulações n - body (agrupamento de objetos fisicamente próximos), banco de dados, computação geométrica, entre muitas outras. Este trabalho estuda formas eficientes de construir tal estrutura de dados. São apresentados vários métodos e em quais situações cada um deles melhor se aplica.

Introdução

A árvore k - d, ou árvore de busca binária k-dimensional, é um tipo de estrutura de dados que permite um processamento eficiente de chaves multidimensionais e foi proposta por Bentley em 1975 [DJzC00], e desde então vem sendo testada e sofrendo vários tipos de modificações, na maioria das vezes com o objetivo de obter um melhor desempenho [Pro97]. A árvore k - d é basicamente um tipo de Árvore Binária de Pesquisa (BST) que divide os pontos em parcelas menores mais viáveis (buckets). Minimizando, assim, o número dos pontos que necessitam ser procurados.

A árvore k - d difere da BST pelo fato de que cada nível da árvore k - d se ramifica baseada numa pesquisa de chave para o nível, chamado discriminador. Definimos o discriminador no nível i como sendo i mod k para k dimensões. Por exemplo, podemos armazenar dados de coordenadas (x,y). Neste caso, k é 2 (há duas coordenadas), com a coordenada x definida arbitrariamente como chave 0, e a coordenada y como chave 1. Para cada nível, o discriminador alterna entre x e y. Portanto, um nodo N, do nível 0 (raiz) teria em sua sub-árvore esquerda apenas nodos cujos valores de x são menores que Nx,.(…).

Trabalho Completo: Um estudo sobre a construção paralela de árvores de busca binária multidimensional