Adaptive and Dynamic Pivot Selection for Similarity Search

Abstract

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.