Engineering Efficient Similarity Search Methods

Abstract

Similarity search has become one of the important parts of many applications including multimedia retrieval, pattern recognition and machine learning. In this problem, the main task is to retrieve most similar (closest) objects in a large data set to a query efficiently by using a function that gives the distance between two objects.

This thesis is presented as a collection of seven papers with a tutorial on the topic and is mainly focused on efficiency issues of similarity search.

• Paper I provides a survey on state-of-the-art approximate methods for metric and non-metric spaces. • Paper II proposes an approximate indexing method for the non-metric Bregman divergences. • Paper III shows how to transform static indexing methods into dynamic ones. • Paper IV presents a learning method to prune in metric and non-metric spaces. • Paper V improves the existing approximate technique that can be applied to ball-based metric indexing methods. • Paper VI presents an open source cross-platform similarity search library and a toolkit called the “Non-Metric Space Library” (NMSLIB) for evaluation of similarity search methods. • Paper VII evaluates a metric index for approximate string matching.