AnÃlise da InfluÃncia do Fator DistribuiÃÃo Espacial dos Dados no Desempenho de MÃtodos de Acesso Multidimensionais

AUTOR(ES)

Ricardo Rodrigues Ciferri

DATA DE PUBLICAÇÃO

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

ASSUNTO(S)

r-trees spatial databases tÃcnica experimental de benchmark Ãrvores-r performance evaluation estruturas de indexaÃÃo espacial ciencia da computacao banco de dados espaciais anÃlise de desempenho database benchmark technique multidimensional access methods distribuiÃÃo espacial dos dados mÃtodos de acesso multidimensionais spatial index structures spatial data distribution

Documentos Relacionados

• AnÃlise da evoluÃÃo da distribuiÃÃo da renda agregada de paÃses da OECD e da AmÃrica Latina, sob a influÃncia da tecnologia da informaÃÃo: aplicaÃÃo do coeficiente de Gini
• AnÃlise da influÃncia da radiaÃÃo em circuitos eletrÃnicos.
• AnÃlise histolÃgica de melanÃcitos: a influÃncia da exposiÃÃo
• AvaliaÃÃo de desempenho das unidades de distribuiÃÃo de uma Diretoria Regional dos Correios utilizando a anÃlise envolvida de dados (DEA)
• AnÃlise da influÃncia do tamanho da partÃcula na flotaÃÃo da apatita em coluna