Learning distance estimators from pivoted embeddings of metric objects

Carrara F., Gennaro C., Falchi F., Amato G.

Pivoted embeddings  Deep neural networks  Distance estimation  Regression  Metric spaces 

Efficient indexing and retrieval in generic metric spaces often translate into the search for approximate methods that can retrieve relevant samples to a query performing the least amount of distance computations. To this end, when indexing and fulfilling queries, distances are computed and stored only against a small set of reference points (also referred to as pivots) and then adopted in geometrical rules to estimate real distances and include or exclude elements from the result set. In this paper, we propose to learn a regression model that estimates the distance between a pair of metric objects starting from their distances to a set of reference objects. We explore architectural hyper-parameters and compare with the state-of-the-art geometrical method based on the n-simplex projection. Preliminary results show that our model provides a comparable or slightly degraded performance while being more efficient and applicable to generic metric spaces.

Source: SISAP 2020: the 13th International Conference on Similarity Search and Applications, pp. 361–368, Copenhagen, Denmark (Virtual), 30/09/2020 - 02/10/2020

Metrics