Similarity Problems in High Dimensions

Similarity computations on large amounts of high-dimensional data has become
the backbone of many of the tasks today at the frontier of computer science, from
machine learning to information retrieval. With this volume and complexity of
input we commonly accept that finding exact results for a given query will entail
prohibitively large storage or time requirements, so we pursue approximate results.
The main contribution of this dissertation is the introduction of new or improved
approximation algorithms and data structures for several similarity search
problems. We examine the furthest neighbor query, the annulus query, distance
sensitive membership, nearest neighbor preserving embeddings and set similarity
queries in the large-scale, high-dimensional setting. In particular: ’
© We present an algorithm for approximate furthest neighbor improving on
the query time of the previous state-of-the-art.
© We combine this algorithm with state-of-the-art approximate nearest
neighbor algorithms to address the approximate annulus query.
© We introduce the first non-trivial algorithm for approximate distance sensitive
membership without false negatives.
© We show that nearest neighbor preserving embeddings can be performed
faster by applying ideas from the framework of Fast Distance Preserving
Embeddings.
© We introduce and analyse a new randomized algorithm for set similarity
join, several times faster than previous algorithms.