HGraph: a connected-partition approach to proximity graphs for similarity search

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


Similarity search is a common approach to support new applications that deal with complex data (e.g., images, videos, georeferenced data, etc.). As a consequence, appropriate indexing structures to support this task have been proposed in the literature. Recently, graph-based methods have shown to be very efficient for approximate similarity search. However, some of the main types of graphs used still suffer from two main drawbacks: (i) slow construction, and (ii) inaccurate retrieval. To reduce these drawbacks, in this paper, we propose the HGraph method. HGraph is a divide-and-conquer method for building graphs for similarity search that recursively partitions the input dataset and connect vertices across partitions at different levels. The method can be used with different types of graphs proposed in the literature to speed up the graph construction time as well as to increase the approximate search results quality through long-range edges connecting pivots of different partitions. We present experimental results using real datasets that show that HGraph applied to the k-NNG graph was able to decrease the construction time while increasing the approximate search recall when compared to the k-NNG. Regarding the application of HGraph to the NSW graph, the query recall also increased, however with a higher computational cost. An analysis of different combinations of the tested methods demonstrated HGraph query times given a recall rate were always among the top results regarding different setups.
Originele taal-2Engels
TitelDatabase and Expert Systems Applications - 30th International Conference, DEXA 2019, Proceedings
RedacteurenSven Hartmann, Josef Küng, Gabriele Anderst-Kotsis, Ismail Khalil, Sharma Chakravarthy, A Min Tjoa
Plaats van productieCham
Aantal pagina's16
ISBN van elektronische versie978-3-030-27615-7
ISBN van geprinte versie978-3-030-27614-0
StatusGepubliceerd - 2019
EvenementDEXA 2019 - 30th International Conference on Database and Expert Systems Applications - Johannes Kepler University, Linz, Oostenrijk
Duur: 26 aug 201929 aug 2019

Publicatie series

NaamLecture Notes in Computer Science


CongresDEXA 2019 - 30th International Conference on Database and Expert Systems Applications
Verkorte titelDEXA

Vingerafdruk Duik in de onderzoeksthema's van 'HGraph: a connected-partition approach to proximity graphs for similarity search'. Samen vormen ze een unieke vingerafdruk.

Citeer dit