Melhorando o desempenho de métodos de acesso métricos dinâmicos com pivôs adicionais locais e antecipação de informações

Página do item simplificado
dataload.collectionmapped02 - Mestrado - Ciência da Computaçãopt_BR
dataload.filenamenourau3922.pdfpt_BR
dataload.handlemapped123456789/50pt_BR
dataload.idpergamum6654pt_BR
dataload.idvirtuanourauvtls000201483pt_BR
dataload.idvirtuapergamumvtls000201483pt_BR
dataload.idvirtuapergamum.sameurlnourauSIMpt_BR
dataload.linknourauhttp://www.bibliotecadigital.uel.br/document/?code=vtls000201483pt_BR
dataload.linknourau.regularSIMpt_BR
dataload.linknourau.retificadohttp://www.bibliotecadigital.uel.br/document/?code=vtls000201483pt_BR
dataload.linknourau.size64.00pt_BR
dc.contributor.advisorKaster, Daniel dos Santos [Orientador]pt_BR
dc.contributor.authorOliveira, Paulo Henrique dept_BR
dc.contributor.bancaRazente, Humberto Luizpt_BR
dc.contributor.bancaBonifácio, Adilson Luizpt_BR
dc.contributor.bancaBrancher, Jacques Duíliopt_BR
dc.coverage.spatialLondrinapt_BR
dc.date.accessioned2024-05-01T11:49:45Z
dc.date.available2024-05-01T11:49:45Z
dc.date.created2015.00pt_BR
dc.date.defesa28.07.2015pt_BR
dc.description.abstractResumo: Nos últimos anos, o crescimento do volume de dados complexos tem sido acelerado por constantes avanços tecnológicos em dispositivos eletrônicos Neste trabalho, são considerados dados complexos quaisquer dados não representáveis por tipos tradicionais, como números, caracteres, datas e textos curtos Dados multimídia, dados georreferenciados e séries temporais são exemplos dessa categoria de dados A relação de ordem é uma propriedade que permite identificar qual elemento precede o outro, segundo algum critério, em cada par de elementos do domínio Visto que estruturas de indexação tradicionais são baseadas nessa propriedade, elas não são adequadas para dados complexos Entretanto, existem estruturas apropriadas para domínios complexos, como os Métodos de Acesso Métricos (MAMs) Há diversos MAMs relatados na literatura, categorizados de diferentes formas dependendo dos fatores que são levados em conta para estruturar os dados Os fatores tipo de pivô e dinamicidade da estrutura estão diretamente relacionados um ao outro Neste trabalho, pivôs são elementos que agem como representantes de certas regiões do espaço de busca e são usados para podar elementos irrelevantes durante a execução de consultas Diz-se que um pivô é global quando todos os elementos do conjunto de dados são referenciados a ele, enquanto um pivô é local quando somente uma porção do conjunto de dados é referenciada a ele Porque pivôs globais são referenciados por todo o conjunto de dados, eles têm um alto impacto no processo de poda de elementos irrelevantes, uma vez que um único pivô global pode ser usado para descartar uma grande quantidade de elementos irrelevantes No entanto, MAMs baseados em pivôs globais podem ter sua dinamicidade comprometida pelo fato de eventuais atualizações relacionadas a pivôs precisarem ser propagadas por toda a estrutura Pivôs locais, por outro lado, permitem que a manutenção ocorra localmente ao preço de um menor poder de poda Nesse contexto, esta Dissertação teve como alvo melhorar o desempenho de MAMs dinâmicos sem comprometer sua dinamicidade, uma vez que várias aplicações manipulam dados complexos online e, consequentemente, demandam índices dinâmicos e eficientes para serem bem-sucedidas Esta Dissertação apresenta duas técnicas para aumentar o poder de poda de MAMs dinâmicos: (i) usar pivôs adicionais locais para reduzir cálculos de distância e (ii) antecipar informações de nós filhos para reduzir acessos a disco desnecessários Ambas as técnicas foram aplicadas a um MAM dinâmico e avaliadas sobre conjuntos de dados reais, reduzindo o tempo de execução em até mais de 5% para consultas por similaridade sobre conjuntos de dados com dimensionalidades e cardinalidades moderadas e altaspt_BR
dc.description.abstractother1Abstract: In recent years, the growth of complex data has been accelerated by constant technological advances in electronic devices In this work, complex data are considered as any data not representable by traditional types, such as numbers, characters, dates and short texts Multimedia data, georeferenced data and time series are examples of this category of data The order relation is a property that allows identifying which element precedes the other, according to some criterion, in each pair of elements of the domain Since traditional index structures are based on this property, they are not suitable for complex data Nevertheless, there are structures well-suited for complex domains, such as the Metric Access Methods (MAMs) There are several MAMs related in the literature, categorized in different ways depending on which factors are taken into account to structure the data The factors pivot type and structure dynamicity are directly related to each other In this work, pivots are elements that act as representatives of certain regions of the search space and are employed to prune irrelevant elements during the query execution It is said that a pivot is global when all elements of the dataset are referenced to it, whereas a pivot is local when only a portion of the dataset is referenced to it Because global pivots are referenced by the whole dataset, they have a high impact in the pruning process of irrelevant elements, once that a single global pivot can be used to discard a large amount of irrelevant elements However, MAMs based on global pivots may have their dynamicity compromised by the fact that eventual pivot-related updates need to be propagated through the entire structure Local pivots, on the other hand, allow the maintenance to occur locally at the price of a lower pruning ability In this context, this dissertation aimed at improving the performance of dynamic MAMs without harming their dynamicity, once that several applications handle online complex data and, consequently, demand efficient dynamic indexes to be successful This dissertation presents two techniques for improving the pruning ability of dynamic MAMs: (i) using local additional pivots to reduce distance calculations and (ii) anticipating information from child nodes to reduce unnecessary disk accesses Both techniques have been applied to a dynamic MAM and evaluated over real datasets, reducing execution time in up to more than 5% for similarity queries posed on datasets ranging from moderate to high dimensionality and cardinalitypt_BR
dc.description.notesDissertação (Mestrado em Ciência da Computação) - Universidade Estadual de Londrina, Centro de Ciências Exatas, Programa de Pós-Graduação em Ciência da Computaçãopt_BR
dc.identifier.urihttps://repositorio.uel.br/handle/123456789/9157
dc.languagepor
dc.relation.coursedegreeMestradopt_BR
dc.relation.coursenameCiência da Computaçãopt_BR
dc.relation.departamentCentro de Ciências Exataspt_BR
dc.relation.ppgnamePrograma de Pós-Graduação em Ciência da Computaçãopt_BR
dc.subjectBanco de dadospt_BR
dc.subjectGerênciapt_BR
dc.subjectEstruturas de dados (Computação)pt_BR
dc.subjectSistemas multimídiapt_BR
dc.subjectComputadorespt_BR
dc.subjectDatabase managementpt_BR
dc.subjectStructures, Data (Computer science)pt_BR
dc.subjectMultimedia systemspt_BR
dc.subjectComputers - Access controlpt_BR
dc.titleMelhorando o desempenho de métodos de acesso métricos dinâmicos com pivôs adicionais locais e antecipação de informaçõespt_BR
dc.typeDissertaçãopt_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
3922.pdf
Tamanho:
914.26 KB
Formato:
Adobe Portable Document Format
Baixar

Coleções

02 - Mestrado - Ciência da Computação