Análise da Eficiência de Métodos de Acesso Espaciais em Termos da Distribuição Espacial dos Dados

September 24, 2017 | Autor: Ricardo Ciferri | Categoria: Spatial Data, Indexation, Range Query
Share Embed


Descrição do Produto

Análise da Eficiência de Métodos de Acesso Espaciais em Termos da Distribuição Espacial dos Dados RICARDO RODRIGUES CIFERRI1 ANA CAROLINA SALGADO2 1 DIN/UEM – Departamento de Informática da Universidade Estadual de Maringá, Av. Colombo, 5790, Zona 07, 87020-900, Maringá, PR, Brasil [email protected] 2 CIn/UFPE – Centro de Informática da Universidade Federal de Pernambuco, Caixa Postal 7851, Cidade Universitária, 50732-970, Recife, PE, Brasil [email protected] Abstract. This paper investigates the performance of several spatial access methods (e.g., the Hilbert R-tree, the R-tree, the R-tree Greene, the R*-trees, the R+-tree, the SR-tree) with respect to the distribution of the indexed spatial objects. In particular, we analyze how the factor spatial data distribution affects the cost of range queries, essentially intersection. In our experiments, we explore a systematic way to generate data sets, which aims at resembling the actual distribution of spatial data in several scenarios. The main contributions of this work are: (a) the up-to-date performance results, which reveal novel performance relationships between the spatial access methods and (b) the description of a workbench turned to analyze spatial index structures. 1

Introdução

Um método de acesso espacial (MAE), também conhecido na literatura como método de acesso multidimensional, é uma estrutura de indexação voltada ao suporte de objetos espaciais, especialmente de retângulos. O principal objetivo de um MAE é propiciar uma rápida obtenção dos objetos espaciais que satisfazem um determinado relacionamento topológico, métrico ou direcional. Neste sentido, o espaço indexado é organizado de tal forma que, por exemplo, a recuperação dos objetos espaciais contidos em uma área particular requeira apenas o acesso aos objetos próximos a esta área, em oposição à análise do conjunto completo de objetos armazenados em memória secundária. Pode-se dizer, portanto, que um MAE é projetado como um caminho otimizado aos dados e o seu uso melhora significativamente o desempenho de sistemas gerenciadores de banco de dados (SGBD) espaciais no processamento de consultas. Neste artigo, nós investigamos o desempenho de um conjunto de métodos de acesso, a maioria dos quais tem sido identificado na literatura como um MAE muito eficiente no suporte às consultas espaciais de seleção (i.e. point queries e range queries). Este grupo consiste dos métodos: Rtree [9], R-tree Greene [7], R+-tree [14], Hilbert R-tree [10], SR-tree [11] e três variantes da R*-tree [1] denominadas respectivamente de R*-tree CR (i.e. close reinsert), de R*-tree FR (i.e. far reinsert) e de R*-tree WR (i.e. without reinsertion). Em especial, a comparação do desempenho destes métodos é realizada visando analisar a influência do fator distribuição espacial dos dados no desempenho dos MAE. Desta forma, nós utilizamos diferentes tipos de distribuição para comparar o desempenho dos métodos. A metodologia utilizada para a geração de um conjunto de

tipos de distribuição espacial dos dados contendo diferentes características é descrita em Ciferri et al. [3]. Resumidamente, a geração de uma certa distribuição de dados é efetuada em três passos. Em primeiro lugar, define-se a localização coletiva dos dados, através da escolha de uma subclasse de localização. Em um segundo passo, determina-se a organização dos dados, através da escolha de uma classe de organização. Finalmente, os pontos relativos à distribuição são gerados segundo a classe de organização escolhida dentro dos limites fixados pela subclasse de localização. Os retângulos são construídos a partir destes pontos (i.e. seus centróides) de acordo com as suas propriedades de extensão espacial (e.g. tamanho e formato). Este trabalho estende a investigação realizada anteriormente em [3], tanto pela inclusão de novos métodos de acesso (i.e. SR-tree e Hilbert R-tree) quanto por utilizar um maior número de tipos de distribuição (i.e. 24 x 21) e principalmente por utilizar uma quantidade significativamente maior de amostras de dados (i.e 960 contra 21 amostras de nosso trabalho anterior). Ademais, as propriedades dos dados espaciais foram reajustadas de forma a reproduzir fielmente as características encontradas em conjuntos de dados reais de aplicações geográficas de telecomunicações. De acordo com o nosso conhecimento, ainda não consta na literatura uma análise tão abrangente do fator distribuição espacial dos dados tampouco uma análise conjunta dos referidos MAE. Uma completa descrição dos algoritmos e da estrutura de dados dos MAE pode ser encontrada nos artigos que propuseram cada uma das estruturas de indexação ([1], [7], [9], [10], [11], [14]), assim como nos extensivos levantamentos bibliográficos feitos por Cox Junior [4], Gaede e

Günther [5], Carneiro [2] e Gatti [6]. Nós não realiza-mos quaisquer descrição destes métodos, apenas informa-mos os valores utilizados para os parâmetros de ajuste da estrutura de dados, pois estes influenciam diretamente no desempenho dos MAE. Em especial, nós usamos o valor de m = 40% * M como o número mínimo de entradas por nó (folha ou não-folha) para a R-tree, a R-tree Greene, a SR-tree, a Hilbert R-tree e as três variantes da R*-tree. O parâmetro M é determinado pelo tamanho da página de disco e consiste do número máximo de entradas por nó. Nós fixamos o valor de p para 30% * M para os métodos R*-tree CR, R*-tree FR e SR-tree. Este parâmetro define o número de entradas a serem reinseridas na estrutura de indexação espacial durante o tratamento de overflow.

minantes de desempenho (tipo de dado, tipo de consulta, tamanho dos objetos, distribuição espacial e dinâmica dos dados). Em particular, foram analisados os métodos de acesso R-tree, R-tree Greene, R+-tree, R*-tree CR e WR. Carneiro [2] estendeu a estratégia proposta em [4] visando à utilização de dados reais representativos para aplicações de gerenciamento de serviços de utilidade pública.

O restante do artigo é estruturado do seguinte modo. A próxima seção efetua uma revisão bibliográfica de trabalhos correlatos. A seção 3 descreve as principais características de nosso ambiente de teste tanto para os dados espaciais (tais como tipos de distribuição espacial, volume de dados, formato e tamanho) quanto para as consultas da carga de trabalho (por exemplo, tipo de distribuição). Já a seção 4 realiza a análise comparativa da eficiência dos MAE com base no desempenho relativo médio destes métodos nos diversos tipos de distribuição espacial. A seção 5, por sua vez, apresenta observações adicionais sobre o desempenho dos métodos SR-tree e Hilbert R-tree. Por fim, a seção 6 apresenta as conclusões.

3

2

Trabalhos Correlatos

Guttman [9] realizou testes de desempenho voltados para a validação e para o ajuste do método de acesso R-tree. Já Kriegel et al. [12] realizaram testes específicos tanto para métodos de acesso a pontos (2-level grid file, BUDDY hash tree, BANG file e hB-tree), quanto para métodos de acesso espaciais (R-tree e PLOP hashing). O principal diferencial dos testes realizados por Greene [7] está relacionado com o fato de que os MAE analisados (R-tree, R+-tree, K-D-B-tree e 2D-ISAM) foram implementados no topo do SGDB POSTGRES através do uso de procedimentos especiais com acesso às funções da camada de abstração de métodos de acesso deste SGBD. Beckmann et al. [1] realizaram testes para ajustar, validar e comparar a estrutura proposta R*-tree com outros métodos de acesso, a saber: R-tree com algoritmos de particionamento de nó quadrático e linear, R-tree Greene e 2-level grid file. Günther e Bilmes [8], por sua vez, realizaram testes de desempenho para comparar um tipo alternativo de MAE, chamado cell tree, com os métodos de acesso R-tree Greene e R+-tree. A estratégia utilizada nos testes realizados por Cox Júnior [4] é baseada na geração sintética de arquivos de dados e de consultas a partir de um conjunto de fatores deter-

Kamel e Faloutsos [10] realizaram experimentos para comparar o método proposto Hilbert R-tree com relação aos métodos R-tree e R*-tree. Na comparação destes MAE foi utilizada a medida número de acessos a disco, a qual foi usada principalmente na coleta de resultados de desempenho relativos à intersection range queries. Ambiente de Teste

Os testes de desempenho foram executados em um microcomputador stand-alone Pentium II 400 MHz com o sistema operacional Windows 98. Este computador possuía 384 Mbytes de memória RAM e 60 Gbytes de disco. Com o intuito de comparar os resultados de desempenho coletados em nossas investigações com os resultados de desempenho reportados por outros pesquisadores, especialmente por Kriegel et al. [12], Cox Júnior [4] e Carneiro [2], o desempenho dos MAE foi medido de acordo com o número de acessos a disco. Além disto, vale destacar que cada método de acesso utilizou um buffer-pool dedicado de 256 Kbytes, ou seja, com 64 páginas de disco de 4.096 bytes. O gerenciamento do buffer-pool foi feito segundo a política LRU (least recently used). Os dados espaciais utilizados em nossos testes de desempenho foram compostos exclusivamente de retângulos, os quais foram definidos no espaço bidimensional dentro do extent [0,1)2. Os centróides dos retângulos foram geradas de forma a respeitar as propriedades do tipo corrente de distribuição espacial, isto é, os centróides foram geradas tal que estivessem contidas nos limites da correspondente subclasse de localização e agrupadas de acordo com a correspondente classe de organização. O formato dos retângulos, por sua vez, seguiram uma distribuição uniforme entre os formatos linear-x e linear-y (aproximadamente o mesmo número de retângulos foi gerado em cada formato). Contudo, enquanto para o formato linear-x nós aplicamos uma distribuição uniforme entre x = y e x = 10y [x = y .. x = 2y .. x = 10y], para o formato linear-y nós aplicamos uma distribuição não-uniforme entre y = x e y = 10x, de modo que foi gerada uma maior quantidade de formatos próximos a y = x, em detrimento dos formatos próximos a y = 10x. Considerando que um formato linear “longo e fino” corresponde ao intervalo 5,5 < F ≤ 10 (i.e. x = F * y ou y = F * x), os formatos típicos de um arquivo de dados são: linear-y (~ 26,71% dos retângulos), linear-x “longo e fino” (~ 25,38%), linear-x (~ 22,21% dos dados), quase

quadrático (~ 21,29%) e linear-y “longo e fino” (~ 4,4%). Já o tamanho (ou área) dos retângulos foi gerado de forma a apresentar um comportamento muito próximo ao verificado no conjunto de dados da cidade de Valinhos, como definido no projeto SAGRE ([2], [6]). Neste conjunto, observa-se um grande número de objetos pequenos e um reduzido número de objetos grandes. Para simular este fato, nós usamos distribuições estatísticas distintas, isto é, nós combinamos 4 distribuições exponenciais que foram ponderadas da seguinte maneira: 38% dos dados na Exp1 (0,0001%), 52% dos dados na Exp2 (0,001%), 9,7% dos dados na Exp3 (0,05%) e 0,3% dos dados na Exp4 (2%). Estas distribuições estatísticas não foram utilizadas em seqüência, mas ao contrário escolhidas arbitrariamente de acordo com as suas respectivas freqüências, à medida que ocorreu a geração sintética dos dados espaciais. Esta estratégia garantiu uma grande mistura de tamanhos nos conjuntos de dados. Em especial, a maioria dos retângulos foi gerado com tamanho próximo a 0,0001% do extent (~ 42,50% dos dados) e menor do que 0,01% do tamanho do extent (~ 90,80% dos retângulos). Tamanhos maiores do que 1% do extent são possíveis, porém raros. O maior tamanho para um certo conjunto de dados variou entre 6% e 10% do tamanho do extent. A distribuição espacial dos dados, a qual é baseada nos centróides dos retângulos, foi obtida usando a metodologia proposta em [3]. Entretanto, apenas um subconjunto dos inúmeros tipos de distribuição que podem ser gerados a partir da metodologia foram considerados em nossa investigação. No total, foram utilizados 24 tipos de distribuição espacial relacionados às subclasses de localização 2, 3, 5, 8, 14, 15, 20 e 21, e as primeira, segunda e terceira classes de organização. Para cada um dos tipos de distribuição espacial foram geradas 10 amostras de dados, baseadas em diferentes sementes de geração aleatória dos dados. A utilização de diferentes amostras (ou conjuntos) de dados para o mesmo tipo de distribuição espacial teve por objetivo eliminar casualidades e por conseguinte garantir uma análise estatística mais robusta do desempe-nho dos MAE. Ademais, nós consideramos 4 volumes de dados (i.e. 10.000, 25.000, 50.000 e 100.000). Enquanto os volumes 10k e 25k representam requisitos básicos de armazenamento em disco, os volumes de dados 50k e 100k representam requisitos mais sofisticados verificados em diversas aplicações espaciais da atualidade. No total, cada MAE indexou 960 arquivos. A figura 4 ilustra os primeiros 1.000 retângulos presentes em um arquivo de dados do tipo de distribuição T22, enquanto as figuras 2 e 3 ilus-tram os tipos de distribuição T23 e T24. Com relação à carga de trabalho, para cada arquivo de dados indexado por um certo MAE, nós executamos 4 tipos de consulta espacial de seleção: point queries (PQ),

intersection range queries (IRQ), enclosure range queries (ERQ) e containment range queries (CRQ). A execução destas consultas espaciais foi controlada em nossos testes de desempenho por arquivos de consulta específicos, cada qual composto por 1.000 consultas. A distribuição espacial dos pontos-base de point queries e das janelas de consulta seguiu uma distribuição uniforme por todo o extent. Para range queries, somente o tamanho das janelas de consulta variou, sendo fixado em 0,001% do extent para IRQ, em 0,00001% do tamanho do extent para ERQ e em 0,1% do extent para CRQ. O formato das janelas foi semelhante ao descrito para os retângulos de dados. 4

Análise Comparativa do Desempenho dos Métodos

Nesta seção, nós analisamos qualitativamente os resultados de desempenho coletados em nossos testes de desempenho, com ênfase em IRQ. As demais consultas são analisadas somente na seção 5 para os métodos SR-tree e Hilbert R-tree. A comparação do desempenho dos MAE é baseada no desempenho relativo médio. Esta escolha é muito importante, uma vez que nos permite comparar resultados de desempenho obtidos em diversos tipos de distribuição espacial sem que haja perda de informação proporcionada por um resultado absoluto muito grande (ou ainda muito pequeno) em uma certa distribuição. Especificamente, o desempenho relativo dos MAE foi normalizado em função do desempenho absoluto do método R*-tree CR. Uma completa descrição dos resultados de desempenho coletados será disponibilizada posteriormente na URL http://www.din.uem.br/~rrc/DED2001.html. A modificação do núcleo de um SGBD espacial visando a substituição do MAE corrente e/ou o acréscimo de um novo método de acesso apenas é plausível se o ganho de desempenho realmente justificar os custos de implementação gerados para incorporar a nova estrutura de indexação espacial. Estes custos geralmente não são pequenos, uma vez que podem englobar alterações em diversas partes de um SGBD, tais como estratégias de otimização de consultas e mecanismos de controle de concorrência. Para ajudar nesta decisão de modificação, um critério apropriado consiste em considerar que o ganho de desempenho propiciado pelo novo MAE deve ser (muito) maior do que o ganho de desempenho estimado com a próxima geração de processadores em alguns meses, caso contrário é mais factível a simples troca do computador do que uma modificação interna do SGBD espacial. De acordo com a lei de Moore [13], duplica-se o poder de processamento de um chip de computador a cada dezoito meses. Desta forma, nós podemos estimar que o ganho de desempenho com a próxima geração de processadores em seis meses (isto é, o tempo hábil previsto para realizar-se a referida modificação do núcleo do SGBD)

será de aproximadamente 33%. Assim, um ganho de desempenho de até 33% devido ao uso de um novo MAE definitivamente não justifica a incorporação do MAE no SGBD espacial. Segundo a nossa perspectiva, a modificação do núcleo de um SGBD espacial deve ser feita prioritariamente para um ganho de desempenho maior do que 50%, sendo que para um ganho de desempenho entre 33% < ∆% ≤ 50% deve-se também levar em considera-ção fatores adicionais, tais como técnicos, operacionais e financeiros. A análise comparativa do desempenho dos MAE, apresentada nesta seção, também baseia-se nos percentuais acima citados, que sugerem quando é viável a modificação do núcleo de um SGBD espacial, para estabelecer critérios que definam a competitividade dos métodos de acesso. Estes critérios, no entanto, são definidos com base na medida simétrica “perda de desempenho”, a qual indica qual o percentual de desempenho que um certo método de acesso é inferior a um outro MAE. Em espe-cial, o “outro MAE”1 corresponde ao método de acesso que obteve o melhor resultado de desempenho nos testes experimentais e que conseqüentemente deve ser o novo MAE escolhido para ser (possivelmente) incorporado ao SGBD espacial. Já cada um dos demais métodos pode ser visto como o MAE corrente em uma implementação particular de um SGBD espacial, o qual pode ser substituído se não for competitivo. Nós consideramos que um método é competitivo se não é recomendável a sua troca pelo MAE que obteve o melhor resultado de desempenho, isto é, quando a perda de desempenho for no máximo 24,81%. Por outro lado, quando a perda de desempenho for maior do que 33,33%, o MAE é considerado não-competitivo. De forma semelhante, o intervalo de perda de desempenho entre 24,81% < ∆% ≤ 33,33% é definido como um intervalo de transição entre MAE competitivos e não-competitivos. Um método de acesso com perda neste intervalo é pouco-competitivo. Com o intuito de diferenciar MAE mais competitivos de MAE menos competitivos, e também de diferenciar MAE com um desempenho ruim de MAE com um desempenho ainda pior, nós consideramos os intervalos ilustrados na tabela 1. Nesta tabela também são associados determinados adjetivos aos intervalos para indicar tanto a qualidade do desempenho (e.g., péssimo, ruim, mediano, bom, e ótimo desempenho) quanto a qualidade do método (e.g., muito ineficiente, regular e eficiente). A clara definição de um MAE competitivo, assim como a 1

para cada configuração de dados (i.e. cada combinação de tipo de distribuição espacial dos dados e de volume de dados, tal como T07 e 10k) é escolhido o “outro MAE” de acordo com o melhor resultado de desempenho em questão.

associação de ad-jetivos aos intervalos, evitam ambigüidades na compara-ção do desempenho dos métodos de acesso. A seguir, nós apresentamos a análise comparativa do desempenho dos MAE especificamente para intersection range queries. Por meio de uma análise do desempenho relativo dos MAE em todos os tipos de distribuição espacial (T01 a T24) em cada um dos volumes de dados (10k, 25k, 50k e 100k), nós observamos que as três variantes da R*-tree foram os métodos de acesso mais eficientes. Os desempenhos destas variantes foram muito próximos entre si, sendo que a R*-tree WR proporcionou em algumas configurações de dados um desempenho ligeiramente inferior ao das outras variantes. O desempenho relativo dos métodos R*-tree CR e R*-tree FR foi predominantemente ótimo, verificado em 78,12% das configurações de dados, e estes métodos foram competitivos em quase a totalidade das configurações (ou seja, em 92,71%). O desempenho relativo da R*-tree WR, por sua vez, foi ótimo em 62,50% das configurações de dados, e muito bom e bom, respectivamente, em 27,08% e 3,13% das configurações, sendo este método, assim como as outras variantes, pouco-competitivo e não-competitivo em apenas uma pequena fração das configurações, isto é, em 3,13% e em 4,16%. Vale ressaltar que a R*-tree CR venceu em 36 das 96 configurações de dados, enquanto que a R*-tree FR obteve o melhor resultado de desempenho em 28 configurações e a R*-tree WR em somente 5 configurações. A superioridade das R*-trees é destacada quando observa-se que estes métodos foram os vencedores em 69 configurações de dados (71,88% das configurações). Dentre os demais MAE, apenas a R+-tree e a R-tree foram o método mais eficiente em alguma outra configuração. A R+-tree, em especial, foi o quarto método de acesso mais eficiente após as variantes da R*-tree, tendo sido competitivo em 65,85% das configurações e vencido em 13,54% destas. Entretanto, nós observamos negativamente que este método foi não-competitivo em 21,95% das configurações de dados, tendo produzido um desempenho ruim e muito ruim, respectivamente, em 9,75% e 12,20% das configurações e obtido o pior desempenho em 6,25% das configurações. Nós observamos que tipos de distribuição baseados na classe de organização 2 (não-uniforme) produziram uma quantidade de resultados de desempenho pouco e não-competitivos maior do que a quantidade de resultados competitivos para o método de acesso R+-tree (i.e. 58,82% pouco e não-competitivos x 41,18% competitivos), ao passo que tipos de distribuição baseados em uma organização uniforme (i.e. classe de organização 1) produziram uma relação inversa (ou seja, 16,67% pouco e não-competitivos contra 83,33% competitivos). Nota-se, desta forma, que a classe de organização 2 degradou a competitividade da R+-tree. Nós não efetuamos testes de

desempenho com tipos de distribuição baseados na classe de organização 4 (i.e. clusters) para a R+-tree. Para este método os percentuais acima indicados incidem sobre o total de configurações testadas, no caso 41. A R-tree Greene foi o quinto método de acesso mais eficiente. A sua principal característica foi ter obtido um desempenho equilibrado que oscilou em sua grande maioria entre resultados bons e resultados ruins. Este método de acesso foi competitivo em 36,46% das configurações e igualmente não-competitivo com o mesmo percentual. Adicionalmente, este MAE obteve resultados de desempenho medianos em 27,08% das configurações de dados e alguns poucos resultados muito bons (6,25% do total). A R-tree foi inferior à R-tree Greene por duas razões. Em primeiro lugar, a R-tree foi competitiva para um percentual menor de configurações de dados, isto é, em 33,33% (versus 36,46% da R-tree Greene). Em segundo lugar, e também importante, obteve um muito maior percentual de resultados de desempenho não-competitivos, ou seja, em 62,50% das configurações de dados contra 36,46% do método R-tree Greene. Um destaque negativo da R-tree é que seus resultados de desempenho foram classificados como ruins em 50% das configurações e como muito ruins em 12,50% das configurações. Além disto, a R-tree obteve o pior desempenho em 22 configurações de dados. Por outro lado, a R-tree proporcionou um desempenho ótimo e muito bom, respectivamente, em 19,79% e 13,54% das configurações. Em particular, nós constatamos que estes resultados competitivos foram alcançados exclusivamente com tipos de distribuição baseaintervalos para perda de desempenho (MAE corrente x novo)

desempenho de um MAE com relação ao do melhor MAE

dos na classe de organização 4 (isto é, clusters), para os quais a R-tree venceu em 14 das 32 configurações. Já os métodos SR-tree e Hilbert R-tree apresentaram, em geral, um desempenho muito fraco. Como exemplo, o desempenho da SR-tree foi não-competitivo em 88,54% das configurações, sendo os seus resultados muito ruins em 39,58% das configurações de dados e péssimos em 30,21% das configurações. A Hilbert R-tree, por sua vez, foi não-competitiva em 86,46% das configurações, sendo que os seus resultados de desempenho foram classificados como muito ruins em 29,17% das configurações e como péssimos em 35,42% das configurações. Vale destacar que apenas estes dois métodos obtiveram um desempenho da categoria péssimo, o que por conseguinte implica que a perda de desempenho foi maior do que 80% com relação ao MAE que obteve o melhor resultado de desempenho. Para algumas poucas configurações estes MAE conseguiram um desempenho competitivo (para a SR-tree foi 6,25% e para a Hilbert R-tree, que foi um pouco superior, 7,29%). Os desempenhos destes métodos, apesar de pobres, foram relativamente próximos entre si, tendo estes MAE se alternado nas últimas colocações em função do volume de dados e da classe de organização. Os volumes menores favoreceram a SR-tree, ao passo que os volumes maiores beneficiaram a Hilbert R-tree. Já tipos de distribuição baseados na classe de organização 2 e 4 degradaram, respectivamente, a competitividade da SR-tree e da Hilbert R-tree. No geral, a SR-tree foi o pior método em 43,75% das configurações de dados e a Hilbert R-tree em 27,08%.

qualidade do desempenho

qualidade do MAE

competitividade do MAE e de seu desempenho

(a)

∆% ≤ 4,76%

o mesmo desempenho

ótimo

eficientíssimo

competitivo

(b)

4,76% < ∆% ≤ 16,67%

muito bom

muito eficiente

competitivo

(c)

16,67% < ∆% ≤ 24,81%

ligeiramente inferior moderadamente inferior

bom

eficiente

competitivo

(d)

24,81% < ∆% ≤ 33,33%

inferior

mediano

regular

pouco-competitivo

(e)

33,33% < ∆% ≤ 50%

muito inferior

ruim

ineficiente

não-competitivo

(f)

50% < ∆% ≤ 80%

extremamente inferior

muito ruim

muito ineficiente

não-competitivo

(g)

∆% > 80%

absurdamente inferior

péssimo

ineficientíssimo

não-competitivo

Tabela 1 Classificação do desempenho dos MAE com relação ao melhor resultado de desempenho Estes fracos resultados de desempenho para ambas a Hilbert R-tree e a SR-tree diferiram significativamente dos bons resultados de desempenho relatados por seus projetistas ([10], [11]). Com o objetivo de descobrir os motivos para esta diferença, nós realizamos testes de desempenho adicionais que são apresentados na seção 5. Por fim, vale destacar que os custos de armazenamento foram similares para os MAE (isto é, os MAM geraram um desempenho

competitivo), exceto para a R+-tree que obteve um desempenho não-competitivo. Em particular, a R+-tree produziu resultados muito ruins e péssimos. 5

Observações Adicionais sobre o Desempenho da SR-tree e da Hilbert R-tree Conforme discutido na seção 4, os desempenhos dos

métodos Hilbert R-tree e SR-tree não foram competitivos. Nesta seção, nós apresentamos os motivos do baixo desempenho destes métodos de acesso e também destacamos configurações para as quais estes MAE podem se tornar bem competitivos. Em particular, para ambos os métodos de acesso, centróides muito próximas podem degenerar a organização da estrutura de dados e conseqüentemente degradar o desempenho. Este fato é discutido em seguida e constitui em um dos motivos para o fraco desempenho dos referidos métodos de acesso, especificamente para tipos de distribuição baseados na classe de organização 4. Para o método Hilbert R-tree, o valor de Hilbert de um retângulo é definido como o valor de Hilbert de seu centro (i.e. sua centróide). Desta forma, retângulos com centróides muito próximos tendem a possuir o mesmo valor de Hilbert, independente de qualquer outra propriedade espacial (como exemplo, a sua extensão espacial). Tal fato prejudica a obtenção de uma ordenação linear dos retângulos que seja satisfatória. Por exemplo, durante o tratamento de overflow, os retângulos são distribuídos uniformemente entre s nós (i.e. move-se alguns dos M+1 retângulos pertencentes ao nó que sofreu overflow para os s-1 cooperating siblings) ou distribuídos uniformemente entre s+1 nós (i.e. no particionamento de s nós para s+1 nós durante o split). Em ambos os casos, a distribuição uniforme é efetuada de acordo com o valor de Hilbert dos retângulos. Caso os retângulos possuam o mesmo valor de Hilbert, a distribuição é efetuada sem qualquer critério geométrico, e com isto a organização da estrutura de dados da Hilbert R-tree é degenerada. Já a SR-tree sofre do problema de fanout, desde que efetua o armazenamento conjunto de uma MBC (bounding sphere) e de um MBR (bounding rectangle) em cada entrada dos nós internos (não-folhas). O problema do fanout é compensado, geralmente, devido à eliminação de uma grande quantidade de subárvores durante a realização de consultas espaciais, sendo esta eliminação proporcionada pelo uso de uma melhor aproximação, ou seja, especificamente pela utilização da interseção de uma MBC com um MBR. Entretanto, quando os centróides estão muito próximas, a seletividade de uma consulta espacial é inerentemente mais alta, desde que acontece um alto grau de sobreposição entre os objetos espaciais (i.e. retângulos de dados). Portanto, centróides muito próximas degeneram a organização da estrutura de dados da SR-tree no sentido que anulam completamente os benefícios propiciados com o uso conjunto de uma MBC e de um MBR, isto é, no sentido que não permitem a eliminação de um número tão grande de subárvores quanto o desejado pois realmente torna-se necessário a descida até diversos nós folhas. Contudo, através de uma investigação complementar, nós verificamos que o desempenho da Hilbert R-tree e da

SR-tree, com relação ao suporte às consultas espaciais de seleção, foi também muito afetado devido às características espaciais de tamanho e formato dos retângulos de dados. O agrupamento incorreto, em um mesmo nó folha, de retângulos com características antagônicas de tamanho e formato degenera a organização da estrutura de dados dos referidos métodos. Como exemplo, um grande número de retângulos pequenos com formato (quase) quadrático podem ser associados ao mesmo nó folha que alguns poucos retângulos grandes com o formato linear “longo e fino”. Isto pode acontecer porque tanto a Hilbert R-tree quanto a SR-tree baseiam-se estritamente em centróides para direcionar a inserção de dados no índice. Como conseqüência deste agrupamento inapropriado de retângulos, ocorre a formação de regiões muito grandes para as correspondentes entradas de nós internos superiores (Figura 1) e assim a organização da estrutura de dados destes MAE é significativamente degenerada. Isto aconteceu na indexação dos arquivos de dados presentes em nossos testes de desempenho anteriores para os métodos Hilbert R-tree e SR-tree e o principal motivo do baixo desempenho destes métodos para point queries e range queries.

x =

y

Figura 1 Representação de uma Entrada de um 1 Nó Interno contendo= uma Região Grande 0 3 y Com o intuito de evitar x o armazenamento de retângulos de dados pequenos e muito pequenos juntamente com retângulos médios e grandes, e conseqüentemente evitar a formação de regiões grandes para as entradas de nós nãofolhas, nós efetuamos uma seqüência adicional de testes de desempenho com novas amostras de dados. Para estas amostras, nós modificamos as características de tamanho e formato dos retângulos de dados. O tamanho dos retângulos foi fixado em 0,001% do tamanho total do extent. Com isto, evitou-se uma grande variação no tamanho dos retângulos associados a qualquer nó-folha e minimizou-se também o tamanho das regiões. Vale lembrar que a estratégia de geração utilizada em nossos testes de desempenho anteriores (seção 3) permitiu uma grande variação no tamanho dos retângulos, entre quase 0% do tamanho do extent (< 10-8 %) e 10% do tamanho total do extent. Já com relação ao formato dos retângulos de dados nestes novos testes de desempenho, nós optamos por uma distribuição uniforme entre os formatos linear-x, linear-x “longo e fino”, quadrático, linear-y e linear-y “longo e fino”. Tal distribuição de formatos teve por objetivo indu-

zir a formação de regiões mais balanceadas, algumas das quais com um formato próximo ao quadrático. Para isto, nós fixamos os formatos em x = y (quadrático), x = 2y (linear-x), y = 2x (linear-y), x = 20y (linear-x “longo e fino”), e y = 20x (linear-y “longo e fino”). Para cada um dos formatos foram geradas a mesma quantidade de retângulos, isto é, 20% do volume de dados de cada amostra. Primeiramente, nós efetuamos testes de desempenho com amostras de dados que seguiram uma distribuição espacial segundo o tipo T22, isto é, seguiram uma distribuição uniforme ao longo de todo o extent. Para este tipo de distribuição espacial, a carga de trabalho apresen-tou características muito semelhantes às características observadas nos arquivos de consulta de nossos testes de desempenho anteriores. Apenas o tamanho das janelas de consulta para IRQ foi diferente do tamanho utilizado em nossos testes anteriores, isto é, foi ajustado para 0,01% do extent devido ao novo tamanho dos dados. Em especial, a utilização deste tipo de distribuição objetivou reduzir o número de centróides muito próximos entre si. Para o volume de dados 10k, a SR-tree foi o método mais eficiente para todas as consultas espaciais de seleção com a primeira amostra de dados e também obteve ótimos resultados de desempenho (i.e. segundo melhor desempenho) com a segunda amostra de dados para IRQ e CRQ, além de resultados competitivos para PQ e ERQ que foram, respectivamente, 3,27% e 8,13% inferiores ao desempenho do melhor MAE (i.e. R*-tree CR). Os resultados de desempenho da Hilbert R-tree foram competitivos na primeira amostra de dados, tendo sido inferiores ao do método SR-tree entre 6,12% e 12,76%. Para CRQ, em especial, a Hilbert R-tree alcançou o segundo melhor resultado de desempenho. Ainda com o volume de dados 10k, na segunda amostra de dados a Hilbert R-tree manteve o comportamento para PQ e ERQ, porém melhorou com relação a IRQ e CRQ, para as quais foi o método mais eficiente. Uma análise comparativa com a R*-tree CR indicou que ambas a SR-tree e a Hilbert R-tree propiciaram um melhor desempenho do que a R*-tree CR nas duas amostras de dados do volume 10k para IRQ e CRQ. Para os volumes de dados 25k, 50k e 100k, a SR-tree e a Hilbert R-tree apresentaram um comportamento semelhante nestes volumes, porém diferente do verificado com o volume 10k. Em particular, estes métodos voltaram a propiciar um fraco desempenho no suporte às consultas PQ e ERQ. Para estas consultas, o desempenho da SR-tree e da Hilbert R-tree foi inferior ao do melhor desempenho, respectivamente, entre 24,70% e 49,02% e entre 21,23% e 37,58%. A Hilbert R-tree, por outro lado, obteve resultados de desempenho competitivos para IRQ e CRQ, tendo sido o MAE vencedor para ambas as amostras de dados com os volumes 50k e 100k e tendo alcançado o segundo

melhor desempenho com o volume de dados 25k (perda de desempenho entre 3,57% e 11,81% para o MAE mais eficiente). Já a SR-tree, com relação às consultas IRQ e CRQ, produziu resultados competitivos, com um desempenho inferior de 4,83% a 17,92% ao do melhor MAE. Vale destacar que a Hilbert R-tree venceu a R*-tree CR em todas as configurações de volume e amostra de dados para IRQ e CRQ, ao passo que a SR-tree obteve com estas consultas espaciais um desempenho muito próximo ao da R*-tree CR quando perdeu (entre 1,32% a 8,74% inferior) e um desempenho superior ao da R*-tree CR em oito das dezesseis configurações para IRQ e CRQ. Em segundo lugar, nós realizamos testes de desempenho com amostras de dados que seguiram uma distribuição espacial baseada no tipo T23, ou seja, que seguiram uma distribuição não-uniforme ao longo de todo o extent sem que fosse constituído qualquer cluster. A carga de trabalho, em particular, diferiu dos arquivos de consulta anteriores no sentido que usou uma distribuição correlacionada com os dados para as quatro consultas espaciais de seleção. O uso de uma distribuição correlacionada com os dados faz com que a seletividade de uma consulta aumente muito e por conseguinte o desempenho da SR-tree tendeu a piorar. O desempenho da Hilbert R-tree, no entanto, continuou sendo competitivo, sendo melhor que a R*-tree CR em todas as configurações de tipo e volume, exceto uma. 6

Conclusão

O uso de diferentes tipos de distribuição espacial dos dados proporcionou uma grande variação no desempenho dos MAE no suporte às consultas espaciais de seleção. A variação no desempenho dos MAE foi de até 7.496,64% para point queries, de até 5.981,08% para intersection range queries, de até 1.363,94% para containment range queries e de até 8.282,62% para enclosure range queries. Nota-se, portanto, que o fator distribuição espacial exerce uma forte influência no desempenho dos MAE. Em especial, nós observamos que a organização dos dados afetou mais o desempenho dos métodos do que a localização dos dados, apesar de que o uso de diferentes subclasses de localização também afetou significativamente o desempenho dos métodos de acesso. O desempenho dos MAE foi favorecido ou prejudicado em função de determinadas classes de organização. Por exemplo, a R-tree foi competitiva para tipos de distribuição baseados em clusters. Por fim, para as configurações citadas na seção 5, os métodos SR-tree e Hilbert R-tree obtiveram resultados de desempenho competitivos, especialmente com relação a IRQ e CRQ. Estes resultados foram possíveis devido principalmente à modificação das características de tamanho e formato dos retângulos de dados.

Referências [1] Beckmann, N., et al. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In Proc. 1990 ACM SIGMOD Conference, pp. 322-331, 1990. [2] Carneiro, A.P. Análise de Desempenho de Métodos de Acesso Espaciais Baseada em um Banco de Dados Real. Master’s thesis, IC, Unicamp, 1998. [3] Ciferri, R.R, Salgado, A.C., Cortez, S.S. Investigando a Variação do Desempenho de Métodos de Acesso Multidimensionais em Função da Distribuição Espacial dos Dados. In Proc. XV SBBD, Brasil, pp. 115-129. 2000. [4] Cox Junior, F.S. Análise de Métodos de Acesso a Dados Espaciais Aplicados a Sistemas Gerenciadores de Banco de Dados. Master’s thesis, DCC, Unicamp, 1991. [5] Gaede, V., Günther, O. Multidimensional Access Methods. ACM Computing Surveys, 30(2):170-231,1998.

Figura 2 Tipo de Distribuição T23

[6] Gatti. S.D. Fatores que Afetam o Desempenho de Métodos de Junções Espaciais: Um Estudo com Base em Dados Reais. Master’s thesis, IC, Unicamp, July 2000. [7] Greene, D. An Implementation and Performance Analysis of Spatial Data Access Methods. In Proc. 5th IEEE ICDE, 1989. [8] Günther, O., Bilmes, J. Tree-based Access Methods for Spatial Databases: Implementation and Performance Evaluation. IEEE TKDE, 3(3):342-356, September 1991. [9] Guttman, A. R-Trees: A Dynamic Index Structure for Spatial Searching. In Proc. 1984 ACM SIGMOD Conference, pp. 47-57, USA, June 1984. [10] Kamel, I., Faloutsos, C. Hilbert R-tree: An Improved R-tree using Fractals. In Proc. 20 th VLDB Conference, pp. 500-509, Chile, 1994. [11] Katayama, N., Satoh, S. The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries. In Proc. SIGMOD Conference, pp. 369-380, June 1997.

Figura 3 Tipo de Distribuição T24

[12] Kriegel, H.-P., et. al. Performance Comparison of Point and Spatial Access Methods. In volume 409 of LNCS, pp. 89-114. 1989. [13] Moore, G.E. Cramming more Components onto Integrated Circuits. Electronics, 38(8), April 1965. [14] Sellis, T., Roussopoulos, N., Faloutsos, C. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In Proc. 13th VLDB Conference, pp. 507-518, 1987.

Agradecimentos Os autores agradecem a Mario A. Nascimento (University of Alberta, Canadá) pelas inúmeras sugestões e críticas a este trabalho. Os autores também agradecem aos pesquisadores do grupo de Banco de Dados do Instituto de Computação da Unicamp pela disponibilização do código da maioria dos métodos estudados. O primeiro autor também agradece ao programa PICDT/CAPES pelo apoio financeiro.

Figura 4 Tipo de Distribuição T22 (Retângulos)

Lihat lebih banyak...

Comentários

Copyright © 2017 DADOSPDF Inc.