Similarity search is the task of identifying, in a collection of items, the ones that are “similar” to a givenquery item. This task has a range of important applications (e.g. in information retrieval, patternrecognition, statistics, and machine learning) where data sets are often big, high dimensional, andpossibly noisy. State-of-the-art methods for similarity search offer only weak guarantees wh ...