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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

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.
Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications - 30th International Conference, DEXA 2019, Proceedings
EditorsSven Hartmann, Josef Küng, Gabriele Anderst-Kotsis, Ismail Khalil, Sharma Chakravarthy, A Min Tjoa
Place of PublicationCham
PublisherSpringer
Pages106-121
Number of pages16
Volume11706
ISBN (Electronic)978-3-030-27615-7
ISBN (Print)978-3-030-27614-0
DOIs
Publication statusPublished - 2019
EventDEXA 2019 - 30th International Conference on Database and Expert Systems Applications - Johannes Kepler University, Linz, Austria
Duration: 26 Aug 201929 Aug 2019

Publication series

NameLecture Notes in Computer Science
PublisherSpringerLink
Volume11706

Conference

ConferenceDEXA 2019 - 30th International Conference on Database and Expert Systems Applications
Abbreviated titleDEXA
CountryAustria
CityLinz
Period26/08/1929/08/19

Keywords

  • Metric spaces
  • Proximity Graphs
  • Similarity search

Fingerprint Dive into the research topics of 'HGraph: a connected-partition approach to proximity graphs for similarity search'. Together they form a unique fingerprint.

  • Cite this

    Capobianco Shimomura, L., & Kaster, D. (2019). HGraph: a connected-partition approach to proximity graphs for similarity search. In S. Hartmann, J. Küng, G. Anderst-Kotsis, I. Khalil, S. Chakravarthy, & A. M. Tjoa (Eds.), Database and Expert Systems Applications - 30th International Conference, DEXA 2019, Proceedings (Vol. 11706, pp. 106-121). (Lecture Notes in Computer Science ; Vol. 11706). Springer. https://doi.org/10.1007/978-3-030-27615-7_8