Similarity-based searching
AssigneeGoogle Inc.
InventorsRoberto J. Bayardo, Yiming Ma, Ramakrishnan Srikant
Life of this patent
Estimating the term…
Abstract
Pairs of similar vectors (or objects) in a set of vectors (or objects) are identified. A comparison vector x in a set of vectors is identified; a size threshold is determined such that if a similarity between the vector x and a vector y in the set of vectors is equal to or greater than a similarity threshold, then the vector y has a size at least equal to the size threshold, the size of the candidate vector y being determined based on a number of non-zero features in the vector y. A vector having a size less than the size threshold is removed from the set of candidate vectors.
Claims43
A method of identifying pairs of similar vectors in a dataset of vectors, the method comprising:
- for a comparison vector x in a dataset of vectors and a similarity threshold value t, determining a size threshold minsize, wherein minsize is a function of x and t, such that if a similarity between the vector x and a vector y in the dataset of vectors is equal to or greater than the similarity threshold value t, then the vector y has a size at least equal to the size threshold minsize, the size of a vector being defined as the number of non-zero components in the vector;
- producing a set of candidate vectors from the dataset of vectors, wherein vectors having a size less than the size threshold minsize are not included in the set of candidate vectors;
- and
- identifying a pair of similar vectors (x, y), wherein y is in the set of candidate vectors.
A system for identifying pairs of similar vectors in a dataset of vectors, comprising:
- a dataset tool to produce a set of candidate vectors from a dataset of vectors, and to identify a comparison vector x in the dataset of vectors;
- and
- a similarity tool to determine, for the comparison vector x and a similarity threshold t, a size threshold minsize, wherein minsize is a function of x and t, such that if a similarity between one of the candidate vectors y and the comparison vector x is equal to or greater than a similarity threshold value t, then the vector y has a size at least equal to the size threshold minsize, the size of a vector being defined as the number of non-zero components in the vector,
- wherein the dataset tool does not include vectors having a size less than the size threshold minsize in the set of candidate vectors, and
- wherein the similarity tool identifies a pair of similar vectors (x, y), wherein v is in the set of candidate vectors.
A system comprising:
- means for determining, for a comparison vector x in a dataset of vectors and a similarity threshold value t, a size threshold minsize, wherein minsize is a function of x and t, such that if a similarity between the vector x and a vector y in the dataset of vectors is equal to or greater than the similarity threshold value t, then the vector y has a size at least equal to the size threshold minsize, the size of a vector being defined as the number of non-zero components in the vector;
- and
- a computer-readable storage device storing instructions that, when executed by one or more computers, cause the one or more computers to perform operations comprising:
- producing a set of candidate vectors from the dataset of vectors, wherein vectors having a size less than the size threshold minsize are not included in the set of candidate vectors;
- and
- identifying a pair of similar vectors (x, y), wherein y is in the set of candidate vectors.
Dependencies are inferred from the claim text.