An eigenvalue-based pivot selection strategy for improving search efficiency in metric spaces
Sunghwan Kim, Da-Young Lee, Hwan-Gue Cho · 2016
Utilizing pivot spaces is a popular method to perform similarity search queries in metric spaces when it is difficult to search the objects with their plain representation. In the pivot space, an object is transformed into a vector whose coordinates are its distances to pre-defined pivots. Based on this transform, any distance-based and multi-dimensional data structures can be used to perform various types of search queries. Although it has been observed that the search performance in terms of query throughput highly depends on which pivots are chosen, it still has been unclear how to choose good pivots despite of a number of work presented over decades. In this paper, we present a pivot selection strategy based on their correlation. By computing eigenvalues and manipulating them, independent pivots are chosen to improve the efficiency of the searching process in the pivot space. Experimental results show that selecting uncorrelated pivots improves the performance, and outperforms other previous pivot selection approaches.