Approximate similarity search using samples
Bilegsaikhan Naidan, Magnus Lie Hetland, Ole Edsberg · 2011
We present an approximation technique for similarity queries in metric spaces seeking to reduce the number of distance computations required to process the query. The new technique could be applied to ball and hyperplane regions in metric index structures, but also to non-metric index structures such as generalized search trees. Experimental results show that our sampling based technique performed better than the relative error approximation technique, but worse than the region proximity technique.