Análise da Influência do Fator Distribuição Espacial dos Dados no Desempenho de Métodos de Acesso Multidimensionais

Detalhes bibliográficos
Ano de defesa: 2002
Autor(a) principal: CIFERRI, Ricardo Rodrigues
Orientador(a): SALGADO, Ana Carolina Brandão
Banca de defesa: Não Informado pela instituição
Tipo de documento: Tese
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Pernambuco
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://repositorio.ufpe.br/handle/123456789/1951
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