SPLX-Perm: A Novel Permutation-Based Representation for Approximate Metric Search

Lucia Vadicamo*, Richard Connor, Fabrizio Falchi, Claudio Gennaro, Fausto Rabitti

*Corresponding author for this work

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

Abstract

Many approaches for approximate metric search rely on a permutation-based representation of the original data objects. The main advantage of transforming metric objects into permutations is that the latter can be efficiently indexed and searched using data structures such as inverted-files and prefix trees. Typically, the permutation is obtained by ordering the identifiers of a set of pivots according to their distances to the object to be represented. In this paper, we present a novel approach to transform metric objects into permutations. It uses the object-pivot distances in combination with a metric transformation, called n-Simplex projection. The resulting permutation-based representation, named SPLX-Perm, is suitable only for the large class of metric space satisfying the n-point property. We tested the proposed approach on two benchmarks for similarity search. Our preliminary results are encouraging and open new perspectives for further investigations on the use of the n-Simplex projection for supporting permutation-based indexing.

Original languageEnglish
Title of host publicationSimilarity Search and Applications - 12th International Conference, SISAP 2019, Proceedings
EditorsGiuseppe Amato, Claudio Gennaro, Vincent Oria, Miloš Radovanovic
PublisherSpringer
Pages40-48
Number of pages9
ISBN (Print)9783030320461
DOIs
Publication statusPublished - 1 Jan 2019
Event12th International Conference on Similarity Search and Applications, SISAP 2019 - Newark, United States
Duration: 2 Oct 20194 Oct 2019

Publication series

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

Conference

Conference12th International Conference on Similarity Search and Applications, SISAP 2019
Country/TerritoryUnited States
CityNewark
Period2/10/194/10/19

Keywords

  • Approximate metric search
  • Metric embedding
  • n-point property
  • n-Simplex projection
  • Permutation-based indexing

Fingerprint

Dive into the research topics of 'SPLX-Perm: A Novel Permutation-Based Representation for Approximate Metric Search'. Together they form a unique fingerprint.

Cite this