Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

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

Full text
Author(s):
Munoz, Javier Vargas [1] ; Goncalves, Marcos A. [2] ; Dias, Zanoni [1] ; Torres, Ricardo da S. [1]
Total Authors: 4
Affiliation:
[1] Univ Estadual Campinas, Ave Albert Einstein 1251, Campinas, SP - Brazil
[2] Univ Fed Minas Gerais, Ave Antonio Carlos 6627, Belo Horizonte, MG - Brazil
Total Affiliations: 2
Document type: Journal article
Source: PATTERN RECOGNITION; v. 96, DEC 2019.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 14/50715-9 - Characterizing and predicting biomass production in sugarcane and eucalyptus plantations in Brazil
Grantee:Rubens Augusto Camargo Lamparelli
Support type: Research Grants - Research Partnership for Technological Innovation - PITE
FAPESP's process: 16/50250-1 - The secret of playing football: Brazil versus the Netherlands
Grantee:Sergio Augusto Cunha
Support type: Research Projects - Thematic Grants
FAPESP's process: 17/16246-0 - Sensitive media analysis through deep learning architectures
Grantee:Sandra Eliza Fontes de Avila
Support type: Regular Research Grants
FAPESP's process: 17/20945-0 - Multi-user equipment approved in great 16/50250-1: local positioning system
Grantee:Sergio Augusto Cunha
Support type: Multi-user Equipment Program
FAPESP's process: 14/12236-1 - AnImaLS: Annotation of Images in Large Scale: what can machines and specialists learn from interaction?
Grantee:Alexandre Xavier Falcão
Support type: Research Projects - Thematic Grants
FAPESP's process: 13/50169-1 - Towards an understanding of tipping points within tropical South American biomes
Grantee:Ricardo da Silva Torres
Support type: Research Grants - Research Partnership for Technological Innovation - PITE
FAPESP's process: 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points
Grantee:Flávio Keidi Miyazawa
Support type: Research Projects - Thematic Grants
FAPESP's process: 17/12646-3 - Déjà vu: feature-space-time coherence from heterogeneous data for media integrity analytics and interpretation of events
Grantee:Anderson de Rezende Rocha
Support type: Research Projects - Thematic Grants
FAPESP's process: 13/50155-0 - Combining new technologies to monitor phenology from leaves to ecosystems
Grantee:Leonor Patricia Cerdeira Morellato
Support type: Research Program on Global Climate Change - University-Industry Cooperative Research (PITE)
FAPESP's process: 15/24494-8 - Communications and processing of big data in cloud and fog computing
Grantee:Nelson Luis Saldanha da Fonseca
Support type: Research Projects - Thematic Grants