Determining query terms of little significance

• US 8,346,757 B1
• Filed: 03/28/2005
• Issued: 01/01/2013
• Est. Priority Date: 03/28/2005
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lamping, John, Bisciglia, Christophe
• Primary Examiner(s): Wilson, Kimberly
• Assistant Examiner(s): Liu, Hexing
• Application Number:
  US11/090,302
• Time in Patent Office: 2,836 Days
• Field of Search: 707/713, 707/714, 707/718, 707/721, 707/728, 707/730, 707/731, 707/748, 707/750, 707/752, 707/765
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: H04L 67/01 Protocols

Abstract

A system determines whether a term of a search query is a term with little significance based on a context of the search query. The system performs a search based on the search query while considering the term with little significance as optional when the search query includes the term with little significance and presents a list of search results based on the search.

Claims

1. A method, comprising:

receiving, by a processor in a computer system, a search query that includes a plurality of terms;

analyzing, by a processor in the computer system, a particular term of the search query to calculate an indication of significance of the particular term of the search query, where analyzing the particular term includes;

an determining if the particular term is significant when present in the search query with one or more other terms of the search query, the determining including;

identifying pairs of queries in a query log that are the same except that one of the queries in each of the pairs of queries includes the particular term and the other of the queries in each of the pairs of queries does not include the particular term, and

identifying whether a group of the pairs of queries is associated with at least a threshold quantity of search results that are common between each of the pairs of queries, and

identifying the particular term as a term that has little significance when a group of the pairs of queries is associated with at least the threshold quantity of search results that are common between each of the pairs of queries in the group, the particular term being significant when the group of the pairs of queries is not associated with at least the threshold quantity of search results;

identifying, by a processor in the computer system, documents based on a subset of the plurality of terms of the search query, where the subset does not include the particular term that has little significance; and

providing, by a processor in the computer system, a list of search results based on the identified documents.

2. The method of claim 1, further comprising:

analyzing the query log to generate data structure entries that correlate search terms; and

storing the generated data structure entries in a data structure that is stored in the memory.

3. The method of claim 2, where analyzing the query log includes:

identifying a pair of queries in the query log that are the same except that one of the queries in the pair of queries includes an extra term that is not included in the other query, of the pair of queries,

calculating a quantity of search results that are common to the pair of queries, and

identifying the extra term as a term of little significance when the quantity of search results, that are common to the pair of queries, is above the threshold quantity.

4. The method of claim 1, further comprising:

calculating whether one or more contexts exist in which the particular term is significant, where the calculating includes;

identifying a set of pairs of queries in the query log in which the particular term appears with one or more same terms in each query of the pairs of queries, where one of the queries in each of the pairs of queries includes the particular term and another one of the queries in each of the pairs of queries does not include the particular term,

identifying whether a group of the pairs of queries in the set includes at least another threshold quantity of search results that are different between each of the pairs of queries, and

identifying the particular term as significant when the group is associated with at least the threshold quantity of search results that are different between each of the pairs of queries.

5. The method of claim 1, further comprising:

identifying pairs of queries in the query log that are the same except that one of the queries in each of the pairs of queries includes an extra term that is not included in another query of the pair of queries;

identifying whether a group of the pairs of queries is associated with at least another threshold quantity of search results that are different between each of the pairs of queries in the group; and

identifying the extra term as a term that is significant when a group of the pairs of queries is associated with at least the other threshold quantity of search results that are different between each of the pairs of queries in the group.

6. The method of claim 5, further comprising:

calculating whether a context exists in which the extra term has little significance, where the calculating includes;

identifying a set of pairs of queries in the query log in which the extra term appears with one or more same terms in each query of the pairs of queries, where one of the queries in each of the pairs of queries includes the extra term and another one of the queries in each of the pairs of queries does not include the extra term, and

identifying the extra term as having little significance when a group of the pairs of queries in the set is associated with at least the threshold quantity of search results that are common between each of the pairs of queries.

7. The method of claim 1, further comprising:

analyzing the query log to identify whether a user provided a first search query, followed by a second query, where the first query includes a first term and the second search query does not include the first term; and

identifying the first term as a term of little significance when the user provided the first search query, followed by the second search query, a quantity of times that exceeds a threshold.

8. The method of claim 7, where identifying the first term as a term of little significance includes:

identifying that the user provided the first search query that includes the first term followed by the second search query that does not include the first term for at least 1% of the queries associated with the user.

9. The method of claim 7, further comprising:

identifying the first term as significant when a quantity of times, that the user provided the first search query that includes the first term followed by the second search query that does not include the particular term, does not exceed the threshold.

10. The method of claim 7, further comprising:

repeating the analyzing the query log and identifying the first term as a term of little significance based on other terms with which the first term occurs in the search query.

11. The method of claim 1, where providing a list of search results comprises:

scoring the identified documents, where the particular term with little significance contributes an amount that is greater than zero and is less than an amount contributed by another term of the search query to a score of one of the identified documents.

12. The method of claim 1, further comprising:

assigning a first weight to a first term of the search query, where the first term is different from the particular term with little significance, and

assigning a second weight to the particular term with little significance, where the second weight is less than the first weight.

13. The method of claim 12, further comprising:

identifying whether one of the identified documents includes both the first term and the particular term of little significance;

scoring the one of the identified documents based on the first weight and the second weight when the one of the identified documents includes both the first term and the particular term of little significance; and

scoring the one of the identified documents based on the first weight but not the second weight when the one of the identified documents includes the first term but does not include the particular term of little significance.

14. The method of claim 13, where providing the list of search results includes:

calculating a position of the one of the identified documents in the list of search results based on its score.

15. The method of claim 1, where determining if the particular term is significant includes:

looking up the particular term in a data structure, where the data structure includes;

a first field that identifies the particular term,

a second field that identifies a first set of terms, where, when the particular term appears in a search query with one or more terms of the first set, the particular term has little significance, and

a third field that identifies a second set of terms, where, when the particular term appears in a search query with one or more terms of the second set, the particular term is significant.

16. The method of claim 15, where looking up the particular term in the data structure includes:

identifying a best match between terms of the search query in the data structure to calculate whether the particular term has little significance or is significant.

17. A method, comprising:

analyzing, by a processor in a computer system, query logs to identify pairs of queries that are the same except that one of the queries in each of the pairs of queries includes an extra term that is not included in another query in the pair of queries;

calculating, by a processor in the computer system, a quantity of search results, associated with a group of the pairs of queries, that are common or different between the pair of queries;

identifying, by a processor in the computer system, whether the group of the pairs of queries is associated with at least a first threshold quantity of the search results that are common between each of the pairs of queries;

identifying, by a processor in the computer system, the extra term as a term of little significance when the group of the pairs of queries is associated with at least the first threshold quantity of search results that are common between each of the pairs of queries in the group; and

identifying, by a processor in the computer system, the extra term as a term that is significant when a group of the pairs of queries is associated with at least a second threshold quantity of search results that are different between each of the pairs of queries in the group.

18. The method of claim 17, further comprising:

calculating whether a first context exists in which the extra term is significant when the extra term is identified as a term of little significance in a different second context.

19. The method of claim 18, where calculating whether the first context exists in which the extra term is significant includes:

identifying a set of pairs of queries in the query logs in which the extra term appears, where each pair of queries, of the set, includes a similar context, where one of the queries in each of the pairs of queries includes the extra term and another one of the queries in each of the pairs of queries does not include the extra term,

identifying that a group of the pairs of queries, in the set, is associated with at least the second threshold quantity of search results that are different between each of the pairs of queries, and

identifying the extra term as significant in the similar context upon identifying that a group of the pairs of queries in the set is associated with at least the second threshold quantity of search results that are different between each of the pairs of queries.

20. The method of claim 17, further comprising:

updating a data structure with information indicating that the extra term is a term of little significance or is a term that is significant.

21. The method of claim 17, further comprising:

identifying whether a context exists in which the extra term has little significance when the extra term is identified as a term that is significant.

22. The method of claim 21, where identifying whether a context exists in which the extra term has little significance includes:

identifying a set of pairs of queries in the query logs in which the extra term appears, where each pair of queries, of the set, includes a similar context, where one of the queries in each of the pairs of queries includes the extra term and another one of the queries in each of the pairs of queries does not include the extra term,

identifying whether a group of the pairs of queries in the set is associated with at least the first threshold quantity of search results that are common between each of the pairs of queries, and

identifying the extra term as a term of little significance in the similar context when a group of the pairs of queries in the set includes at least the first threshold quantity of search results that are common between each of the pairs of queries.

23. The method of claim 17, further comprising:

analyzing the query logs to identify whether individual users provided a first search query that includes the extra term followed by a second search query that does not include the extra term; and

identifying the extra term as a term of little significance based on identifying that individual users provided a first search query that includes the extra term followed by a second search query that does not include the extra term.

24. The method of claim 23, where identifying the extra term as a term of little significance includes:

identifying that individual users provided a first search query that includes the extra term followed by a second search query that does not include the extra term, when the individual users provided the first search query followed by another search query, greater than approximately 1% of the time.

25. The method of claim 23, further comprising:

identifying the extra term as a term that is significant when individual users did not provide a first search query that includes the extra term followed by a second search query that does not include the extra term greater than approximately 1% of the time.

26. The method of claim 23, further comprising:

repeating the analyzing query logs and identifying the extra term as a term of little significance for different contexts in which the extra term occurs.

27. A system comprising:

one or more processors to;

receive a search query;

analyze a particular term of the search query to calculate an indication of significance of the particular term of the search query, where, when analyzing the particular term, the processor is further to;

determine if the particular term is significant when present in the search query with one or more other terms of the search query, where, when determining, the processor is further to;

identify pairs of queries in a query log that are the same except that one of the queries in each of the pairs of queries includes the particular term and the other of the queries in each of the pairs of queries does not include the particular term, and

identify whether a group of the pairs of queries is associated with at least a threshold quantity of search results that are common between each of the pairs of queries, and

identify the particular term as having little significance when a group of the pairs of queries is associated with at least the threshold quantity of search results that are common between each of the pairs of queries in the group;

identify documents based on the search query;

generate scores for the identified documents, where the particular term with little significance contributes an amount that is greater than zero and is less than an amount that is contributed by another term of the search query to a score of one of the identified documents that includes both the term with little significance and the other term; and

identify a list of search results based on the scores of the identified documents.

28. The system of claim 27, where, when generating the scores for the identified documents, the processor is further to:

assign a first weight to the other term of the search query, and

assign a second weight to the particular term with little significance, where the second weight is less than the first weight.

29. The system of claim 28, where, when generating the scores for the identified documents, the processor is further to:

identify whether a document of the identified documents includes both the other term and the particular term with little significance,

score the document based on the first weight and the second weight when the document includes both the other term and the particular term with little significance, and

score the document based on the first weight and not the second weight when the document includes the other term and does not include the particular term with little significance.

30. A non-transitory computer-readable medium storing instructions, the instructions comprising:

one or more instructions which, when executed by at least one processor, cause the at least one processor to receive a search query that includes a plurality of terms;

one or more instructions which, when executed by at least one processor, cause the at least one processor to analyze a particular term of the search query to calculate an indication of significance of the particular term of the search query, the one or more instructions to analyze the particular term including;

one or more instructions to identify pairs of queries in a query log that are the same except that one of the queries in each of the pairs of queries includes an extra term and the other of the queries in each of the pairs of queries does not include the extra term,

one or more instructions to identify whether a group of the pairs of queries is associated with at least a threshold quantity of search results that are common between each of the pairs of queries,

one or more instructions to identify the particular term as a term that is not significant based on a group of the pairs of queries being associated with at least the threshold quantity of search results that are common between each of the pairs of queries in the group, the particular term being significant when the group of the pairs of queries is not associated with at least the threshold quantity of search results;

one or more instructions which, when executed by at least one processor, cause the at least one processor to identify documents based on the search query while considering the particular term that is not significant as optional; and

one or more instructions which, when executed by at least one processor, cause the at least one processor to provide a list of search results based on the identified documents, where at least one of the identified documents does not include the particular term that is not significant.

31. The method of claim 30, further comprising:

assigning a first score to the particular term that is not significant and a higher second score to another term of the search query; and

assigning scores to the identified documents based on the first and second scores.

32. The method of claim 30, further comprising:

analyzing another term of the search query to calculate an indication of significance of the other term of the search query, where analyzing the other term includes;

locating, in a data structure, an entry that associates the other term with one or more terms of the search query besides the other term, and

upon locating the entry that associates the particular term with one or more other terms of the search query, identifying the other term as significant.

33. The method of claim 30, where considering the particular term that is not significant as optional includes:

reducing a weight associated with the particular term, where the weight is used to identify documents based on the query.

34. The method of claim 33, where one or more other terms of the search query are associated with a higher weight than the reduced weight that is associated with the particular term.