System and method for determining semantically related terms based on sequences of search queries

• US 7,814,086 B2
• Filed: 11/16/2006
• Issued: 10/12/2010
• Est. Priority Date: 11/16/2006
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Sebastian, Shaji, Murthi, Vijay, Bartz, Kevin, Rey, Benjamin
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/600,698
• Publication Number:
  US 20080120072A1
• Time in Patent Office: 1,426 Days
• Field of Search: None
• US Class Current: 707/708
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06F 16/374 Thesaurus
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/184 Intellectual property management

Abstract

The present disclosure is directed to systems and methods for determining semantically related terms based on sequences of search queries. Generally, a semantically related term tool examines search logs to associate search queries with a user submitting the search query. The semantically related term tool establishes a plurality of sequences of search queries, each sequence of search queries comprising one or more search queries associated with a common user and relating to a common concept. The semantically related term tool receives one or more seed terms and determines one or more terms related to the received seed terms based on the established plurality of sequences of search queries.

Claims

1. A method for determining one or more semantically related terms based on sequences of search queries, the method comprising:

examining search query information to associate search queries with a user submitting the search query;

establishing a plurality of sequences of search queries, each sequence of search queries comprising one or more search queries associated with a common user and relating to a common concept;

receiving one or more seed terms;

creating a first set of vectors representing for each search query in the search query information, whether the search query is associated with each sequence of the plurality of sequences;

creating a second set of vectors representing for each search query in the search query information, a weight associated with the search query based on the number of sequences of the plurality of sequences the search query is associated with; and

determining one or more terms semantically related to the seed terms based on the first set of vectors, the second set of vectors, and at least one seed term of the received one or more seed terms;

wherein determining one or more terms semantically related to the seed terms comprises determining a weighted average over each sequence of the plurality of sequences as a function of the first and second set of vectors, and the at least one seed term; and

wherein the weighted average is calculated using the formula;

T=Sum of (V1*VectorSimilarity(V2,S)),

wherein V1*VectorSimilarity (V2,S) is calculated for a number of sequences found in the search query information;

V1 is the relevant vector of the first set of vectors indicating for each search query in the search query information, whether a search query is associated with the relevant sequence;

V2 is the relevant vector of the second set of vectors including for each search query in the search query information, an entry indicating a weight of a search query associated with the sequence; and

S is the seed term vector indicating for each search query in the search query information, whether the search query is one of the received seed terms.

2. The method of claim 1, wherein establishing a plurality of sequences of search queries comprises:

adding a first search query associated with a first user to a first sequence;

determining whether to add a second search query associated with the first user to the first sequence based on a similarity between the second search query and at least the first search query of the first sequence;

adding the second search query to the first sequence in response to determining the similarity between the second search query and at least the first search query of the first sequence exceeds a similarity threshold; and

adding the second query to a second sequence in response to determining the similarity between the second search query and at least the first search query of the first sequence does not exceed the similarity threshold.

3. The method of claim 2, wherein determining a similarity between the second search query and at least the first search query of the first sequence is based on at least one of:

an edit distance between the second search query and at least the first search query of the first sequence;

a word edit distance between the second search query and at least the first search query of the first sequence;

a difference between a time the second search query issued and the time that at least the first search query of the first sequence issued;

whether there is a prefix overlap between the second search query and at least the first search query of the first sequence;

whether there is a suffix overlap between the second search query and at least the first search query of the first sequence;

a geographic location related to the second search query and at least the first search query of the first sequence; and

a product brand associated with the second search query and at least the first search query of the first sequence.

4. The method of claim 1, wherein determining one or more terms semantically related to the seed terms comprises:

weighing each entry in first and second set of vectors based on a total number of sequences of the plurality of sequences and a number of sequences that contain each search query; and

normalizing the first and second set of vectors.

5. The method of claim 1, wherein the VectorSimilarity operation is one of a Pearson correlation, a cosine similarity, mutual information, Jaccard'"'"'s coefficient, Tanimoto coefficients, or similarity metrics based on distance metrics like Euclidean distance, Hamming distance, Chebychev'"'"'s distance, Mahalonobis distance, and Manhattan distance.

6. A computer-readable storage medium comprising a set of instructions for determining one or more semantically related terms based on sequences of search queries, the set of instructions to direct a processor to perform acts of:

examining search query information to associate search queries with a user submitting the search query;

establishing a plurality of sequences of search queries, each sequence of search queries comprising one or more search queries associated with a common user and relating to a common concept;

receiving one or more seed terms;

creating a first set of vectors representing for each search query in the search query information, whether the search query is associated with each sequence of the plurality of sequences;

creating a second set of vectors representing for each search query in the search query information, a weight associated with the search query based on the number of sequences of the plurality of sequences the search query is associated with; and

determining one or more terms semantically related to the seed terms based on the first set of vectors, the second set of vectors, and at least one seed term of the received one or more seed terms;

wherein determining one or more terms semantically related to the seed terms comprises determining a weighted average over each sequence of the plurality of sequences as a function of the first and second set of vectors, and the at least one seed term; and

wherein the weighted average is calculated using the formula;

T=Sum of (V1*VectorSimilarity(V2,S)),

wherein V1*VectorSimilarity (V2,S) is calculated for a number of sequences found in the search query information;

V1 is the relevant vector of the first set of vectors indicating for each search query in the search query information, whether a search query is associated with the relevant sequence;

V2 is the relevant vector of the second set of vectors including for each search query in the search query information, an entry indicating a weight of a search query associated with the sequence; and

S is the seed term vector indicating for each search query in the search query information, whether the search query is one of the received seed terms.

7. The computer-readable storage medium of claim 6, wherein establishing a plurality of sequences of search terms comprises:

adding a first search query associated with a first user to a first sequence;

determining whether to add a second search query associated with the first user to the first sequence based on a similarity between the second search query and at least the first search query of the first sequence;

adding the second search query to the first sequence in response to determining the similarity between the second search query and at least the first search query of the first sequence exceeds a similarity threshold; and

adding the second query to a second sequence in response to determining the similarity between the second search query and at least the first search query of the first sequence does not exceed the similarity threshold.

8. A system for determining one or more semantically related terms based on sequences of search queries, the system comprising:

a search query memory module storing search query information, the search query information associating at least search queries received at a search engine and a user submitting the search queries,

a semantically related term tool operative to;

access the search query memory module storing search query information and determine a plurality of search sequences, each search sequence comprising one or more search queries submitted by a common user and related to a common concept;

create a first set of vectors representing for each search query in the search query information of the search query memory module, whether the search query is associated with each sequence of the plurality of sequences;

create a second set of vectors representing for each search query in the search query information of the search query memory module, a weight associated with the search query based on the number of sequences of the plurality of sequences the search query is associated with; and

determine one or more terms semantically related to the seed terms based on the first set of vectors, the second set of vectors, and at least one seed term of the received one or more seed terms;

wherein to determine one or more terms semantically related to the seed terms, the semantically related term tool is further operative to determine a weighted average over each sequence of the plurality of sequences as a function of the first and second set of vectors, and the at least one seed term; and

wherein the weighted average is calculated using the formula;

T=Sum of (V1*VectorSimilarity(V2,S)),

wherein V1*VectorSimilarity (V2,S) is calculated for a number of sequences found in the search query information;

V1 is the relevant vector of the first set of vectors indicating for each search query in the search query information, whether a search query is associated with the relevant sequence;

V2 is the relevant vector of the second set of vectors including for each search query in the search query information, an entry indicating a weight of a search query associated with the sequence; and

S is the seed term vector indicating for each search query in the search query information, whether the search query is one of the received seed terms.

9. The system of claim 8, wherein the semantically related term tool receives the one or more seed terms from a system of an online advertisement service provider.

10. The system of claim 9, wherein the one or more seed terms are received from a keyword suggestion tool of the online advertisement service provider.

11. The system of claim 9, wherein the one or more seed terms are received from an advertisement campaign management system of the online advertisement service provider.

12. The system of claim 8, wherein the semantically related term tool comprises:

a memory module operative to store a set of instructions for directing a processor to access the search query memory module storing search query information and determine a plurality of search sequences, each search sequence comprising one or more search queries submitted by a common user and related to a common concept, to receive one or more seed terms, and to determine one or more terms semantically related to the received seed terms based on the determined plurality of sequences of search queries; and

a processor operative to access the memory module of the semantically related term tool and execute the set of instructions.

13. The system of claim 8, wherein the semantically related term tool is operative to determine a plurality of sequences based on similarities between a first search query and at least one search query of a sequence of the plurality of sequences.

14. The system of claim 13, wherein similarities between search queries is based on at least one of:

an edit distance between the second search query and at least the first search query of the first sequence;

a word edit distance between the second search query and at least the first search query of the first sequence;

a difference between a time the second search query issued and the time that at least the first search query of the first sequence issued;

whether there is a prefix overlap between the second search query and at least the first search query of the first sequence;

whether there is a suffix overlap between the second search query and at least the first search query of the first sequence;

a geographic location related to the second search query and at least the first search query of the first sequence; and

a product brand associated with the second search query and at least the first search query of the first sequence.