Search result ranking using query clustering

Patent metadata

Field	Value
Publication number	US-9251292-B2
Application number	US-201313794349-A
Country	US
Kind code	B2
Filing date	Mar 11, 2013
Priority date	Mar 11, 2013
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

Systems and methods are disclosed herein for providing search results, particularly product records from a product database. Past queries are analyzed and grouped into clusters according to similarities, with each query including a highly relevant head query and a plurality of tail queries. Similarity of queries may be determined based on user response similarity to query results, co-occurrence, and textual similarity. One or more categories are identified for the clusters, such as based on click-through rates for search results of the head queries of the clusters. Upon receiving a query, a cluster for the query is identified, such as according to similarity to one or more queries of the cluster. The categories associated with the cluster are then used to one or both of augment the query and rank search results for the query.

First claim

The invention claimed is:

1. A method for searching, the method comprising:
receiving, by a computer system, first queries, from a user;
selecting, by the computer system, a plurality of head queries from among the first queries;
clustering, by the computer system, the first queries, exclusive of the plurality of head queries, to the plurality of head queries by:
calculating similarity scores for at least a portion of the first queries relative to the plurality of head queries; and
clustering the at least the portion of the first queries to the plurality of head queries according to the similarity scores;

associating, by the computer system, one or more categories with each head query of the plurality of head queries;
receiving, by the computer system, a second query;
determining a similarity between the second query and at least one of a selected head query of the plurality of head queries;
associating, by the computer system, the second query with the selected head query of the plurality of head queries according to the similarity between the second query and the at least one of the selected head query; and
identifying, by the computer system, one or more documents relevant to the second query using the one or more categories associated with the selected head query of the plurality of head queries;
wherein:
calculating the similarity scores for the at least the portion of the first queries relative to the plurality of head queries further comprises:
evaluating response similarity between user selections of search results for the at least the portion of the first queries and user selections of search results for the plurality of head queries by evaluating an equation:

Sim
(

q
1

,

q
2

)

=

P
1

·

P
2



P
1



2

⁢



P
2



2

where Sim (q 1 ,q 2 ) is a similarity score of a first query a 1 of the at least the portion of the first queries, q 2 is a head query of the plurality of head queries, P 1 is a vector of user selection counts for search results of q 1 , and P 2 is a vector of user selection counts for search results of q 2 .

2. The method of claim 1 , wherein calculating the similarity scores for the at least the portion of the first queries relative to the plurality of head queries further comprises:
determining co-occurrences of the at least the portion of the first queries with the plurality of head queries in a same user session.

3. The method of claim 1 , wherein calculating the similarity scores for the at least the portion of the first queries relative to the plurality of head queries further comprises evaluating textual similarity of the at least the portion of the first queries to the plurality of head queries.

4. The method of claim 1 , wherein calculating the similarity scores for the at least the portion of the first queries relative to the plurality of head queries further comprises:
calculating first scores according to the response similarity between user selections of the search results for the at least the portion of the first queries and user selections of the search results for the plurality of head queries;
calculating second scores according to co-occurrences of the at least the portion of the first queries with the plurality of head queries in a same user session;
calculating third scores according to textual similarity of the at least the portion of the first queries to the plurality of head queries; and
calculating the similarity scores for the at least the portion of the first queries according to a combination of the first, second, and third scores.

5. The method of claim 1 , wherein selecting, by the computer system, the plurality of head queries from among the first queries further comprises:
selecting, as the plurality of head queries, those queries of the first queries having highest click-through rates for search results associated therewith.

6. The method of claim 1 , further comprising evaluating the first queries to identify synonyms according to the clustering of the first queries, exclusive of the plurality of head queries, to the plurality of head queries.

7. The method of claim 6 , further comprising modifying the second query according to the identified synonyms.

8. A system for searching, the system comprising one or more processors and one or more memory devices coupled to the one or more processors, the one or more memory devices storing executable and operational data effective to cause the one or more processors to:
receive first queries, from a user;
select a plurality of head queries from among the first queries;
cluster the first queries, exclusive of the plurality of head queries, to the plurality of head queries by:
calculating similarity scores for at least a portion of the first queries relative to the plurality of head queries by evaluating response similarity between user selections of search results for the at least the portion of the first queries and user selections of search results for the plurality of head queries, by evaluating an equation:

Sim
(

q
1

,

q
2

)

=

P
1

·

P
2



P
1



2

⁢



P
2



2

Assignees

• Wal Mart Stores Inc

Inventors

• Cheng Jinxing
• Gattani Abhishek

Classifications

• G06F17/30979 Primary

  Physics · mapped topic

• G06F17/30705

  Physics · mapped topic

• G06F17/3069

  Physics · mapped topic

• G06F17/30646

  Physics · mapped topic

• G06F16/35

  Clustering; Classification · CPC title