# US 8,280,881 B1 · Similar search queries and images

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,881 B1
- Document ID: US8280881B1
- Status: Granted
- Kind: B1
- Application number: 12/622,630
- Filed: 2009-11-20
- Granted: 2012-10-02
- Earliest claimed: 2009-10-29
- Assignees: Google Inc.
- Inventors: Yun Zhou; Gaurav Garg; Radhika Malpani
- Web page: https://patentgrep.com/patent/US8280881B1

## CPC

- G06F 16/56: having vectorial format
- G06F 16/50: of still image data
- G06F 16/53: Querying
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods, systems and apparatus, including computer programs encoded on a computer storage medium, for determining similar queries for image searches. In one aspect, a method includes generating, for each of a plurality of search queries, a selection vector for the search query, each selection vector including a plurality of vector elements, each vector element corresponding to a unique image, and the value of each vector element being proportional to a number of selections of its corresponding unique image in response to the unique image being presented as a search result for the search query. The method further includes selecting a first search query and a second search query from the plurality of search queries and determining, from the selection vectors for the first and second search queries, a similarity measure that is a measurement of the similarity of the first search query to the second query.

## Claims

### Claim 1

A computer-implemented method performed by a data processing apparatus, the method comprising:
generating, for each of a plurality of search queries, a selection vector for the search query, each selection vector including a plurality of vector elements, each vector element corresponding to a unique image, and the value of each vector element being proportional to a number of selections of its corresponding unique image in response to the unique image being presented as a search result for the search query;
selecting a first search query and a second search query from the plurality of search queries;
generating an inverted image list for each of the unique images, the inverted image list including, for each unique image, one or more tuples, each tuple identifying a search query and including a non-zero vector element corresponding to the unique image and the search query;
selecting, for the first search query, each inverted image list that includes a tuple identifying the first search query;
selecting, for the second search query and from the selected inverted image lists that include the tuple identifying the first search query, each tuple identifying the second search query; and
determining, from the selection vectors for the first and second search queries, a similarity measure that is a measurement of the similarity of the first search query to the second search query.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1, wherein determining the similarity measure comprises:
for each selected inverted image list that includes a selected tuple identifying the second search query, multiplying the non-zero vector element of the tuple by the non-zero vector element of the tuple identifying the first search query in the selected inverted image list to generate an image contribution value; and
summing the image contribution values.

### Claim 3 (depends on 2)

The computer-implemented method of claim 2, wherein:
each tuple includes a respective normalization value that is proportional to the values of the vector elements of the selection vector of the search query the tuple identifies; and
determining the similarity measure further comprises dividing the sum of the image contribution values by a product of the normalization value of the tuples identifying the first search query and the normalization value of the tuples of the second search query.

### Claim 4 (depends on 3)

The computer-implemented method of claim 3, wherein the value of each vector element is equal to the number of selections of its corresponding unique image in response to the unique image being presented as the search result for the search query.

### Claim 5 (depends on 3)

The computer-implemented method of claim 3, wherein the value of each vector element is a probability that its corresponding unique image will be selected in response to the unique image being presented as a search result for the search query of the vector element.

### Claim 6 (depends on 3)

The computer-implemented method of claim 3, wherein the normalization value is a Euclidean norm.

### Claim 7

A computer-implemented method performed by a data processing apparatus, the method comprising:
generating, for each of a plurality of search queries, a selection vector for the search query, each selection vector including a plurality of vector elements, each vector element corresponding to a unique image, and the value of each vector element being proportional to a number of selections of its corresponding unique image in response to the unique image being presented as a search result for the search query;
selecting a first search query and a second search query from the plurality of search queries;
generating an inverted image list for each of the unique images, the inverted image list including, for each unique image, one or more tuples, each tuple identifying a search query and including a normalized value that is proportional to a ratio of the non-zero vector element corresponding to the unique image and the search query to a normalization value that is proportional to the values of the vector elements of the selection vector of the search query the tuple identifies;
selecting, for the first search query, each inverted image list that includes a tuple identifying the first search query;
selecting, for the second search query and from the selected inverted image lists that include the tuple identifying the first search query, each tuple identifying the second search query; and
determining, from the selection vectors for the first and second search queries, a similarity measure that is a measurement of the similarity of the first search query to the second search query.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7, wherein determining the similarity measure comprises:
for each selected inverted image list that includes a selected tuple identifying the second search query, multiplying the normalized value of the tuple by the normalized value of the tuple identifying the first search query in the selected inverted image list to generate an image contribution value; and
summing the image contribution values.

### Claim 9

A system comprising:
one or more computers; and
a computer-readable medium coupled to the one or more computers having instructions stored thereon which, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
generating, for each of a plurality of search queries, a selection vector for the search query, each selection vector including a plurality of vector elements, each vector element corresponding to a unique image, and the value of each vector element being proportional to a number of selections of its corresponding unique image in response to the unique image being presented as a search result for the search query;
selecting a first search query and a second search query from the plurality of search queries;
generating an inverted image list for each of the unique images, the inverted image list including, for each unique image, one or more tuples, each tuple identifying a search query and including a non-zero vector element corresponding to the unique image and the search query;
selecting, for the first search query, each inverted image list that includes a tuple identifying the first search query;
selecting, for the second search query and from the selected inverted image lists that include the tuple identifying the first search query, each tuple identifying the second search query; and
determining, from selection vectors for the first and second search queries, a similarity measure that is a measurement of the similarity of the first search query to the second search query.

### Claim 10 (depends on 9)

The system of claim 9, wherein determining the similarity measure comprises:
for each selected inverted image list that includes a selected tuple identifying the second search query, multiplying the non-zero vector element of the tuple by the non-zero vector element of the tuple identifying the first search query in the selected inverted image list to generate an image contribution value; and
summing the image contribution values.

### Claim 11 (depends on 10)

The system of claim 10, wherein:
each tuple includes a respective normalization value that is proportional to the values of the vector elements of the selection vector of the search query the tuple identifies; and
determining the similarity measure further comprises dividing the sum of the image contribution values by a product of the normalization value of the tuples identifying the first search query and the normalization value of the tuples of the second search query.

### Claim 12 (depends on 11)

The system of claim 11, wherein the value of each vector element is equal to the number of selections of its corresponding unique image in response to the unique image being presented as the search result for the search query.

### Claim 13 (depends on 11)

The system of claim 11, wherein the value of each vector element is a probability that its corresponding unique image will be selected in response to the unique image being presented as a search result for the search query of the vector element.

### Claim 14

A computer-implemented method performed by a data processing apparatus, the method comprising:
generating, for each of a plurality of images, a selection vector for the image, each selection vector including a plurality of vector elements, each vector element corresponding to a unique search query, and the value of each vector element being proportional to a number of selections of the image in response to the image being presented as a search result for the unique search query;
selecting a first image and a second image from the plurality of images;
generating an inverted query list for each of the unique search queries, the inverted query list including, for each unique search query, one or more tuples, each tuple identifying an image and including a non-zero vector element corresponding to the image and the unique search query;
selecting, for the first image, each inverted query list that includes a tuple identifying the first image;
selecting, for the second image and from the selected inverted query lists that include the tuple identifying the first image, each tuple identifying the second image; and
determining, from the selection vectors for the first and second images, a similarity measure that is a measurement of the similarity of the first image to the second image;
wherein determining the similarity measure comprises:
for each selected inverted query list that includes a selected tuple identifying the second image, multiplying the non-zero vector element of the tuple by the non-zero vector element of the tuple identifying the first image in the selected inverted query list to generate a query contribution value; and
summing the query contribution values.

### Claim 15 (depends on 14)

The computer-implemented method of claim 14, wherein:
each tuple includes a respective normalization value that is proportional to the values of the vector elements of the selection vector of the image the tuple identifies; and
determining the similarity measure further comprises dividing the sum of the query contribution values by a product of the normalization value of the tuples identifying the first image and the normalization value of the tuples of the second image.

### Claim 16

A non-transitory computer-readable medium storing machine instructions operable to cause one or more programmable processors to perform operations comprising:
generating, for each of a plurality of search queries, a selection vector for the search query, each selection vector including a plurality of vector elements, each vector element corresponding to a unique image, and the value of each vector element being proportional to a number of selections of its corresponding unique image in response to the unique image being presented as a search result for the search query;
selecting a first search query and a second search query from the plurality of search queries;
generating an inverted image list for each of the unique images, the inverted image list including, for each unique image, one or more tuples, each tuple identifying a search query and including a non-zero vector element corresponding to the unique image and the search query;
selecting, for the first search query, each inverted image list that includes a tuple identifying the first search query;
selecting, for the second search query and from the selected inverted image lists that include the tuple identifying the first search query, each tuple identifying the second search query; and
determining, from the selection vectors for the first and second search queries, a similarity measure that is a measurement of the similarity of the first search query to the second search query.

### Claim 17 (depends on 16)

The non-transitory computer-readable medium of claim 16, wherein determining the similarity measure comprises:
for each selected inverted image list that includes a selected tuple identifying the second search query, multiplying the non-zero vector element of the tuple by the non-zero vector element of the tuple identifying the first search query in the selected inverted image list to generate an image contribution value; and
summing the image contribution values.

### Claim 18 (depends on 17)

The non-transitory computer-readable medium of claim 17, wherein:
each tuple includes a respective normalization value that is proportional to the values of the vector elements of the selection vector of the search query the tuple identifies; and
determining the similarity measure further comprises dividing the sum of the image contribution values by a product of the normalization value of the tuples identifying the first search query and the normalization value of the tuples of the second search query.

### Claim 19 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein the value of each vector element is equal to the number of selections of its corresponding unique image in response to the unique image being presented as the search result for the search query.

### Claim 20 (depends on 18)

The non-transitory computer-readable medium of claim 18, wherein the value of each vector element is a probability that its corresponding unique image will be selected in response to the unique image being presented as a search result for the search query of the vector element.
