Interaction with image databases is facilitated by using example images in a query. Query-by-example often requires a comparison of the features in the query image with features of the database image. The appropriate comparison function need not be the Euclidean distance between the two features - several non-Euclidean similarity measures have been shown to be visual more appropriate. This paper considers the problem of efficient retrieval of images using such similarity measures. A classical k-d tree based indexing algorithm is extended to such similarity measures and experimental performance evaluation of the algorithm is also provided.