Open AccessProximity Graphs for Similarity Searches: Experimental Survey and the New Connected-Partition Approach HGraph
Author(s) -
Larissa C. Shimomura,
Daniel S. Kaster
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.5753/sbbd_estendido.2021.18181
Subject(s) - computer science , similarity (geometry) , graph , nearest neighbor search , partition (number theory) , graph partition , data mining , information retrieval , theoretical computer science , artificial intelligence , mathematics , combinatorics , image (mathematics)
Similarity searching is a widely used approach to retrieve complex data (images, videos, time series, etc.). Similarity searches aim at retrieving similar data according to the intrinsic characteristics of the data. 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. This work presents two main contributions to graph-based methods for similarity searches. 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. The second contribution is a new graph-based method called HGraph, which is a connected-partition approach to build a proximity graph and answer similarity searches. Both of our contributions and results were published and received awards in international conferences.