Hierarchical Clustering-Based Graphs for Large Scale Approximate Nearest Neighbor Search

Autor(es)

Munoz, Javier Vargas ^[1] ; Goncalves, Marcos A. ^[2] ; Dias, Zanoni ^[1] ; Torres, Ricardo da S. ^[1]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Ave Albert Einstein 1251, Campinas, SP - Brazil

^[2] Univ Fed Minas Gerais, Ave Antonio Carlos 6627, Belo Horizonte, MG - Brazil

• Tipo de documento: Artigo Científico
• Fonte: PATTERN RECOGNITION; v. 96, DEC 2019.
• Citações Web of Science: 0

Resumo

This paper presents a novel approach to perform fast approximate nearest neighbors search in high dimensional data, using a nearest neighbor graph created over large collections. This graph is created based on the fusion of multiple hierarchical clustering results, where a minimum-spanning-tree structure is used to connect all elements in a cluster. We propose a novel search technique to guide the navigation on the graph without computing exhaustively the distances to all neighbors in each step of the search, just to those in the direction of the query. The objective is to determine the nearest point to the query with a few number of distance calculations. We experimented in three datasets of 1 million SIFT, GIST, and GloVe features. Results show better speedups than another graph-based technique, and competitive speedups at high recall values when compared to classic and recent state-of-the-art techniques. (C) 2019 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 14/50715-9 - Characterizing and predicting biomass production in sugarcane and eucalyptus plantations in Brazil
• Beneficiário: Rubens Augusto Camargo Lamparelli
• Linha de fomento: Auxílio à Pesquisa - Parceria para Inovação Tecnológica - PITE
• Processo FAPESP: 16/50250-1 - O segredo de jogar futebol: Brasil versus Holanda
• Beneficiário: Claudio Alexandre Gobatto
• Linha de fomento: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/16246-0 - Análise de mídias sensíveis usando arquiteturas de aprendizado profundo
• Beneficiário: Sandra Eliza Fontes de Avila
• Linha de fomento: Auxílio à Pesquisa - Regular
• Processo FAPESP: 13/50169-1 - Towards an understanding of tipping points within tropical South American biomes
• Beneficiário: Ricardo da Silva Torres
• Linha de fomento: Auxílio à Pesquisa - Parceria para Inovação Tecnológica - PITE
• Processo FAPESP: 14/12236-1 - AnImaLS: Anotação de Imagem em Larga Escala: o que máquinas e especialistas podem aprender interagindo?
• Beneficiário: Alexandre Xavier Falcão
• Linha de fomento: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/20945-0 - EMU concedido no processo 16/50250-1: local positioning system
• Beneficiário: Ricardo da Silva Torres
• Linha de fomento: Auxílio à Pesquisa - Programa Equipamentos Multiusuários
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Linha de fomento: Auxílio à Pesquisa - Temático
• Processo FAPESP: 17/12646-3 - Déjà vu: coerência temporal, espacial e de caracterização de dados heterogêneos para análise e interpretação de integridade
• Beneficiário: Anderson de Rezende Rocha
• Linha de fomento: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/50155-0 - Combining new technologies to monitor phenology from leaves to ecosystems
• Beneficiário: Leonor Patricia Cerdeira Morellato
• Linha de fomento: Auxílio à Pesquisa - Programa de Pesquisa sobre Mudanças Climáticas Globais - PITE
• Processo FAPESP: 15/24494-8 - Comunicação e processamento de big data em nuvens e névoas computacionais
• Beneficiário: Nelson Luis Saldanha da Fonseca
• Linha de fomento: Auxílio à Pesquisa - Temático