13. A method of identifying pairs of similar vectors in a set of vectors, the method comprising: determining, using one or more computers, a partial similarity score for a vector x in a set of vectors and each other vector in the set of vectors, each partial similarity score representing a degree of similarity between features of the vector x and corresponding features of other vectors in the set of vectors; determining, using one or more computers, an upper bound, the upper bound being an estimate of the maximum similarity between non-processed features of the vector x and non-processed features of the other vectors, the non-processed features being features that have not been used to calculate the partial similarity scores; as long as the upper bound is greater than or equal to the similarity threshold, adding vectors to a candidate set of vectors and repeating the operations of determining a partial similarity score and determining an upper bound; when the upper bound is lower than the similarity threshold, determining partial similarity scores only for vectors in the candidate set of vectors; and identifying x and a vector y in the candidate set of vectors as similar vectors using the partial similarity score between x and y.
13. A method of identifying pairs of similar vectors in a set of vectors, the method comprising: determining, using one or more computers, a partial similarity score for a vector x in a set of vectors and each other vector in the set of vectors, each partial similarity score representing a degree of similarity between features of the vector x and corresponding features of other vectors in the set of vectors; determining, using one or more computers, an upper bound, the upper bound being an estimate of the maximum similarity between non-processed features of the vector x and non-processed features of the other vectors, the non-processed features being features that have not been used to calculate the partial similarity scores; as long as the upper bound is greater than or equal to the similarity threshold, adding vectors to a candidate set of vectors and repeating the operations of determining a partial similarity score and determining an upper bound; when the upper bound is lower than the similarity threshold, determining partial similarity scores only for vectors in the candidate set of vectors; and identifying x and a vector y in the candidate set of vectors as similar vectors using the partial similarity score between x and y. 14. The method of claim 13 , further comprising determining a similarity estimate between the comparison vector x and a candidate vector y; if the similarity estimate meets a similarity threshold, determining a similarity score between the comparison vector x and the candidate vector y; and if the similarity score meets the similarity threshold, identifying the pair of vectors (x, y) as a pair of similar vectors.