Analysis of distance based indexing methods for similarity search

In this paper we investigate data structures for performing similarity search queries in metric spaces. We have selected six methods proposed in three different communities: two theoretically analyzed structures of Clarkson (1999), GNAT and SA-tree from databases, and AESA and LAESA which are used for pattern recognition applications. We have implemented all these methods and compared their efficiency in practice. We propose an improvement for GNAT data structure that reduces its space requirement. We show this improvement does not degrade the query time by much.