Adaptive and Dynamic Pivot Selection for Similarity Search


  • Mariano Salvetti Universidad Nacional de Rosario
  • Claudia Deco Universidad Nacional de Rosario
  • Nora Reyes Universidad Nacional de San Luis
  • Cristina Bender Universidad Nacional de Rosario


Metric databases, Dynamic index, Sparse Spatial Selection


In this paper, a new indexing and similarity search method based on dynamic selection of pivots is presented. It uses Sparse Spatial Selection (SSS) for the initial selection of pivots. Two new selection policies of pivots are added, in order to the index suits itself to searches when it adapts to the metric space. The proposed structure automatically adjusts to the region where most of searches are made. In this way, the amount of distance computations during searches is reduced. The adjustment is done using the policy of 'the most candidate' for the incoming pivot selection, and the policy of 'the least discriminating' for the outgoing pivot selection.


Download data is not yet available.