Patent ID: 8180756

Claim:
A computer-implemented method for identifying users colluding with a user represented by vector x in a first plurality of vectors, wherein each of the vectors represents a corresponding user, wherein each feature of each vector represents the corresponding user's click-behavior with regard to a content item, the method comprising: determining, using one or more computers, a score for each vector y, wherein the score represents a partial similarity between the vector x and each vector y, wherein each vector y is a vector in the first plurality of vectors, and each vector y includes at least one feature indexed in an index, wherein the partial similarity represents a degree of similarity between features of the vector x and corresponding features of each vector y, and wherein the partial similarity score is determined using features of vector x and only the indexed features of each vector y; 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 y, 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 a similarity threshold, repeating the operations of determining a partial similarity score and determining an upper bound; determining that the upper bound is lower than the similarity threshold; based on determining that the upper bound is lower than the similarity threshold, updating scores only for vectors y having a non-zero partial similarity score; and identifying a user represented by a vector y with a non-zero score as a user colluding with the user represented by the vector x using the score for the vector y.