Proximity graphs for similarity searches : experimental survey and the newconnected-partition approach HGraph

Página do item simplificado
dataload.collectionmapped02 - Mestrado - Ciência da Computaçãopt_BR
dataload.filenamenourau6671.pdfpt_BR
dataload.handlemapped123456789/50pt_BR
dataload.idpergamum125276pt_BR
dataload.idvirtuanourauvtls000226937pt_BR
dataload.idvirtuapergamumvtls000226937pt_BR
dataload.idvirtuapergamum.sameurlnourauNÃOpt_BR
dataload.linknourauhttp://www.bibliotecadigital.uel.br/document/?code=vtls226937pt_BR
dataload.linknourau.regularNÃOpt_BR
dataload.linknourau.retificadohttp://www.bibliotecadigital.uel.br/document/?code=vtls000226937pt_BR
dataload.linknourau.size61.00pt_BR
dc.contributor.advisorKaster, Daniel dos Santos [Orientador]pt_BR
dc.contributor.authorShimomura, Larissa Capobiancopt_BR
dc.contributor.bancaRodrigues Junior, José Fernandopt_BR
dc.contributor.bancaFelinto, Alan Salvanypt_BR
dc.coverage.spatialLondrinapt_BR
dc.date.accessioned2024-05-01T13:10:52Z
dc.date.available2024-05-01T13:10:52Z
dc.date.created2019.00pt_BR
dc.date.defesa16.04.2019pt_BR
dc.description.abstractResumo: O desenvolvimento tecnológico acelerou o crescimento do volume de dados complexos como imagens, vídeos, séries temporais e dados geográficos Uma abordagem bastante utilizada para a recuperação de dados complexos são as consultas por similaridade As consultas por similaridade têm como objetivo principal recuperar dados similares a partir de características intrínsecas dos dados Assim, para facilitar a recuperação de dados complexos usando consultas por similaridade é necessário organizar grande quantidade de dados de forma que dados similares possam ser recuperados da forma mais rápida possível Diversos métodos de acesso foram propostos na literatura para tornar a recuperação por similaridade de grandes bases de dados mais rápida Artigos publicados recentemente indicam que métodos que utilizam grafos são bastante eficientes e superam o desempenho de métodos de outras categorias em várias situações Porém, de acordo com nosso conhecimento, nenhum trabalho se dedicou a realizar uma análise experimental em um número abrangente de métodos baseados em grafos utilizando os mesmos algoritmos de busca e o mesmo ambiente Esta Dissertação apresenta uma revisão bibliográfica sobre os principais tipos de grafos utilizados para consultas por similaridade, também foi realizado uma avaliação experimental utilizando os mesmos algoritmos de consulta com resposta exata e com resposta aproximada O métodos foram avaliados conforme seu comportamento considerando os principais parâmetros de construção e consulta para uma variedade de bases de dados reais A partir dos resultados desta avaliação foi proposto o método baseado em grafos, HGraph O HGraph é um método baseado em partições conectadas proposto para construir grafos de proximidade e responder consultas por similaridade O HGraph utiliza uma estratégia de divisão e conquista para construir tipos de grafos propostos na literatura Para conectar as diferentes partições do processo de divisão e conquista arestas longas foram adicionadas ao HGraph Foi avaliado o comportamento dos principais parâmetros do HGraph e seu desempenho quanto a tempo de construção e consultas por similaridade foram comparados com os métodos k-NNG (k-Nearest Neighbors Graph) , NSW (Navigable Small World Graph) e SAT (Spatial Approximation Tree) Como resultado, o HGraph foi capaz de melhorar o k-NNG em termos de tempo de construção, tempo de consulta e qualidade de resposta Além disso, o HGraph obteve melhor desempenho na busca em alguns datasets quando comparado ao NSW e a SATpt_BR
dc.description.abstractother1Abstract: The technology development has accelerated the growth of the volume of complex data, such as images, videos, time series, and georeferenced data A widely used approach to retrieve complex data are the similarity searches The similarity searches aim at retrieving similar data according to intrinsic characteristics of the data Therefore, in order to facilitate the retrieval of complex data using similarity searches, it is necessary to organize large collections of data in a way that similar data can be retrieved in the shortest time as possible Several access methods were proposed in the literature to speed up similarity data retrieval from large databases Recently, graph-based methods have emerged as a very efficient alternative for similarity retrieval, with reports indicating they have outperformed methods of other categories in several situations However, to the best of our knowledge, there is no previous work with experimental analysis on a comprehensive number of graph-based methods using the same search algorithm and execution environment This work presents two main contributions The first contribution is a survey on the main graph types currently employed for similarity searches and an experimental evaluation of the most representative graphs in a common platform, for exact and approximate search algorithms We evaluated the relative performance behavior of these graphs with respect to the main construction and query parameters for a variety of real-world datasets According to the evaluation of the results, we propose a new graph-based method called HGraph, the second contribution of this work HGraph is a connected partition approach to build graph-based methods and answer similarity searches In HGraph we use a divide and conquer strategy to build graph-based methods proposed in the literature and add long-range edges to connect the different partitions These long-range edges are added in order to increase the answer quality compared to their “base” graph type We evaluated the HGraph main parameters behavior and compared the HGraph construction time and similarity search performance for approximate searches to the k-NNG, SWG and the SAT As a result, the HGraph method was able to accelerate the k-NNG graph construction and improve the k-NNG query time and query recall Thus, the HGraph performed better in similarity searches than the SWG and the SAT in some datasetspt_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/11178
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.subjectTeoria dos grafospt_BR
dc.subjectProcessamento de dadospt_BR
dc.subjectEspaços métricospt_BR
dc.subjectRecuperação de dados (Computação)pt_BR
dc.subjectGraph theorypt_BR
dc.subjectMetric spacespt_BR
dc.subjectData processingpt_BR
dc.titleProximity graphs for similarity searches : experimental survey and the newconnected-partition approach HGraphpt_BR
dc.typeDissertaçãopt_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
6671.pdf
Tamanho:
4.01 MB
Formato:
Adobe Portable Document Format
Baixar

Coleções

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