Re-ranking Permutation-Based Candidate Sets with the n-Simplex Projection

Giuseppe Amato, Edgar Chávez, Richard Connor, Fabrizio Falchi, Claudio Gennaro, Lucia Vadicamo*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)


In the realm of metric search, the permutation-based approaches have shown very good performance in indexing and supporting approximate search on large databases. These methods embed the metric objects into a permutation space where candidate results to a given query can be efficiently identified. Typically, to achieve high effectiveness, the permutation-based result set is refined by directly comparing each candidate object to the query one. Therefore, one drawback of these approaches is that the original dataset needs to be stored and then accessed during the refining step. We propose a refining approach based on a metric embedding, called n-Simplex projection, that can be used on metric spaces meeting the n-point property. The n-Simplex projection provides upper- and lower-bounds of the actual distance, derived using the distances between the data objects and a finite set of pivots. We propose to reuse the distances computed for building the data permutations to derive these bounds and we show how to use them to improve the permutation-based results. Our approach is particularly advantageous for all the cases in which the traditional refining step is too costly, e.g. very large dataset or very expensive metric function.

Original languageEnglish
Title of host publicationSimilarity Search and Applications - 11th International Conference, SISAP 2018, Proceedings
EditorsStéphane Marchand-Maillet, Yasin N. Silva, Edgar Chávez
Number of pages15
ISBN (Print)9783030022235
Publication statusPublished - 1 Jan 2018
Event11th International Conference on Similarity Search and Applications, SISAP 2018 - Lima, Peru
Duration: 7 Oct 20189 Oct 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11223 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference11th International Conference on Similarity Search and Applications, SISAP 2018


  • Distance bounds
  • Metric embedding
  • Metric search
  • n-point property
  • n-Simplex projection
  • Permutation-based indexing


Dive into the research topics of 'Re-ranking Permutation-Based Candidate Sets with the n-Simplex Projection'. Together they form a unique fingerprint.

Cite this