Junções por similaridade aproximadas em espaços vetoriais densos

Página do item simplificado
dc.contributor.advisor-co1Santana
dc.contributor.advisor1Ribeiro, Leonardo Andrade
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4036932351063584
dc.contributor.referee1Ribeiro, Leonardo Andrade
dc.contributor.referee2Bedo, Marcos Vinicius Naves
dc.contributor.referee3Martins, Wellington Santos
dc.creatorSantana , Douglas Rolins de
dc.creator.Latteshttps://lattes.cnpq.br/6843698978977791
dc.date.accessioned2023-10-16T14:48:15Z
dc.date.available2023-10-16T14:48:15Z
dc.date.issued2023-08-24
dc.description.abstractSimilarity Join is an operation that returns pairs of objects whose similarity is greater than or equal to a specified threshold, and is essential for tasks such as cleaning, mining, and data integration. A common approach is to use data vector representations, such as the TFIDF method, and measure the similarity between vectors using the cosine function. However, computing the similarity for all pairs of vectors can be computationally prohibitive on large data sets. Traditional algorithms exploit the sparsity of vectors and apply filters to reduce the comparison space. Recently, advances in natural language processing have produced in semantically richer vectors, improving the results quality. However, these vectors have different characteristics from those generated by traditional methods, being dense and of high dimensionality. Preliminary experiments demonstrated that L2AP, the best known algorithm for similarity join, is not efficient for dense vector spaces. Due to the intrinsic characteristics of such vectors, approximate solutions based on specialized indices are predominant for dealing with large datasets. In this context, we investigate how to perform similarity joins using the Hierarchical Navigable Small World (HNSW), a state-of-the-art graph-based index designed for approximate k-nearest neighbor (kNN) queries. We explored the design space of possible solutions, ranging from top-end alternatives to HNSW to deeper integration of similarity join processing into this framework. The experiments carried out demonstrated accelerations of up to 2.48 and 3.47 orders of magnitude in relation to the exact method and the baseline approach, respectively, maintaining recovery rates close to 100%.eng
dc.description.provenanceSubmitted by Dayane Basílio (dayanebasilio@ufg.br) on 2023-10-05T14:08:23Z workflow start=Step: editstep - action:claimaction No. of bitstreams: 2 license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Dissertação - Douglas Rolins de Santana - 2023.pdf: 2340915 bytes, checksum: 85470543a8c6995a8b36bf5676fa176f (MD5)en
dc.description.provenanceStep: editstep - action:editaction Approved for entry into archive by Luciana Ferreira(lucgeral@gmail.com) on 2023-10-16T14:48:15Z (GMT)en
dc.description.provenanceMade available in DSpace on 2023-10-16T14:48:15Z (GMT). No. of bitstreams: 2 license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Dissertação - Douglas Rolins de Santana - 2023.pdf: 2340915 bytes, checksum: 85470543a8c6995a8b36bf5676fa176f (MD5) Previous issue date: 2023-08-24en
dc.description.resumoJunção por similaridade é uma operação que retorna pares de objetos cuja similaridade é maior ou igual a um limite especificado, sendo essencial para tarefas como limpeza, mineração e integração de dados. Uma abordagem comum é utilizar representações vetoriais dos dados, como o método TF-IDF, e medir a similaridade entre vetores usando a função cosseno. No entanto, calcular a similaridade para todos os pares de vetores pode ser computacionalmente proibitivo em grandes conjuntos de dados. Algoritmos tradicionais exploram a esparsidade dos vetores e aplicam filtros para reduzir o espaço de comparação. Recentemente, avanços no processamento de linguagem natural resultaram em vetores semanticamente mais ricos, melhorando a qualidade dos resultados. No entanto, esses vetores têm características distintas dos gerados por métodos tradicionais, sendo densos e de alta dimensionalidade. Experimentos preliminares demonstraram que o L2AP, melhor algoritmo conhecido para junção por similaridade, não é eficiente em espaços vetoriais densos. Devido às características intrínsecas de tais vetores, soluções aproximadas baseadas em índices especializados são predominantes para lidar com grandes conjuntos de dados. Nesse contexto, foram investigadas formas de realizar junções por similaridade usando o Hierarchical Navigable Small World (HNSW), um índice baseado em grafos de última geração projetado para buscas aproximadas de k-vizinho mais próximo (kNN). Foi explorado o espaço de projeto de possíveis soluções, variando de alternativas do topo do HNSW à uma integração mais profunda do processamento de junção por similaridade nessa estrutura. Os experimentos realizados demonstraram acelerações de até 2,48 e 3,47 ordens de magnitude em relação ao método exato e à abordagem baseline, respectivamente, mantendo taxas de recuperação próximas a 100%.
dc.identifier.citationSANTANA, Douglas R. Junções por similaridade aproximadas em espaços vetoriais densos. 2023. 101 p. Dissertação (Mestrado em Ciência da computação) - Instituto de informática, Universidade federal de Goiás, 2023.
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/13058
dc.languagepor
dc.publisherUniversidade Federal de Goiás
dc.publisher.countryBrasil
dc.publisher.departmentInstituto de Informática - INF (RG)
dc.publisher.initialsUFG
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 Internationalen
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectJunção por similaridadepor
dc.subjectWord embeddingspor
dc.subjectVetores densospor
dc.subjectHNSWpor
dc.subjectSimilarity joineng
dc.subjectDense vectorseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO
dc.titleJunções por similaridade aproximadas em espaços vetoriais densos
dc.title.alternativeApproximate similarity joins over dense vector embeddingseng
dc.typeDissertação

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Douglas Rolins de Santana - 2023.pdf
Tamanho:
2.23 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)