Comment by binarymax

Really interesting and have not heard of k-medoids before!

Have you tried BanditPAM as an index creation technique for approximate-nearest-neighbor search?