Skip navigation
Use este identificador para citar ou linkar para este item: https://repositorio.ufpe.br/handle/123456789/1951
Título: Análise da Influência do Fator Distribuição Espacial dos Dados no Desempenho de Métodos de Acesso Multidimensionais
Autor(es): CIFERRI, Ricardo Rodrigues
Palavras-chave: Métodos de acesso multidimensionais; Estruturas de indexação espacial; Árvores-R; Distribuição espacial dos dados; Análise de desempenho; Técnica experimental de benchmark; Banco de dados espaciais
Data do documento: 2002
Editor: Universidade Federal de Pernambuco
Citação: Rodrigues Ciferri, Ricardo; Carolina Brandão Salgado, Ana. Análise da Influência do Fator Distribuição Espacial dos Dados no Desempenho de Métodos de Acesso Multidimensionais. 2002. Tese (Doutorado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2002.
Resumo: Um método de acesso multidimensional (MAM) é uma estrutura de indexação voltada ao suporte de objetos espaciais, especialmente de retângulos. O principal objetivo de um MAM é propiciar uma rápida obtenção dos objetos espaciais que satisfazem um certo relacionamento topológico, métrico ou direcional. Neste sentido, o espaço indexado é organizado de tal forma que, por exemplo, a recuperação dos retângulos de dados contidos em uma área particular requeira apenas o acesso aos retângulos próximos a esta área, em oposição à análise do conjunto completo de retângulos armazenados em memória secundária. Um MAM, portanto, é projetado como um caminho otimizado aos dados espaciais e o seu uso melhora significativamente o desempenho de sistemas gerenciadores de banco de dados espaciais no processamento de consultas. Nesta tese, nós investigamos o desempenho de um conjunto de MAM, a maioria dos quais tem sido identificado na literatura como um MAM muito eficiente no suporte a consultas espaciais de seleção. Este grupo consiste dos seguintes métodos de acesso: R-tree, R-tree Greene, R+-tree, Hilbert R-tree, SR-tree e três variantes da R* -tree chamadas de R* -tree CR (i.e., close reinsert), de R* -tree FR (isto é, far reinsert) e de R* -tree WR (isto é, without reinsertion). A comparação do desempenho destes MAM foi realizada visando-se analisar prioritariamente a influência do fator distribuição espacial dos dados. Neste sentido, nós propusemos uma metodologia de avaliação de desempenho que permite a geração de um conjunto de tipos de distribuição espacial com diferentes características, as quais tornam possível que a influência do fator distribuição espacial dos dados seja analisada sob diferentes perspectivas, desde uma fraca até uma forte influência. Por meio de diversos testes de desempenho, nós observamos de que forma a distribuição espacial dos dados afetou os custos de inserção e de armazenamento de novas entradas no índice espacial, além do custo de point queries, intersection range queries, enclosure range queries e containment range queries. Com relação a estas consultas espaciais de seleção, os resultados de desempenho mostraram que a R+-tree foi a melhor estrutura de indexação espacial para poin queries e enclosure range queries, ao passo que as variantes da R* -tree produziram os melhores resultados de desempenho para intersection e containment range queries. Por outro lado, os métodos Hilbert R-tree e SR-tree geraram um baixo desempenho para as quatro consultas espaciais investigadas. No entanto, em testes de desempenho adicionais, os quais modificaram tanto o tamanho quanto o formato dos retângulos de dados, os métodos de acesso Hilbert R-tree e SR-tree geraram resultados competitivos, particularmente para intersection e containment range queries
URI: https://repositorio.ufpe.br/handle/123456789/1951
Aparece na(s) coleção(ções):Teses de Doutorado - Ciência da Computação

Arquivos deste item:
Arquivo Descrição TamanhoFormato 
arquivo5133_1.pdf5,61 MBAdobe PDFVer/Abrir


Este arquivo é protegido por direitos autorais



Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.