SYSTEMS AND METHODS FOR GENERATING STATISTICS FROM SEARCH ENGINE QUERY LOGS

• US 20110040733A1
• Filed: 05/08/2007
• Published: 02/17/2011
• Est. Priority Date: 05/09/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sercinoglu, Olcan, Boytsov, Artem, Dean, Jeffrey A.
• Granted Patent: US 8,126,874 B2
• Time in Patent Office: Days
• US Class Current: 707/688
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/3349 Reuse of stored results of previous queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

A computer-implemented method includes calculating first statistics about a user-identified event within a first subset of a database of events; selecting a second subset of the database of events based on said first statistics; calculating second statistics about the user-identified event within the second subset of the database of events; merging the first and second statistics as statistics of the user-identified event within the entire database of events; and generating a result including at least a portion of the merged statistics of the user-identified event.

Claims

1. A computer-implemented method, comprising:

at a server system, distinct from a client system, the server system having one or more processors and memory storing programs executed by the one or more processors;

responding to a query from the client system for statistics of occurrence of a user-identified event, including;

accessing a database of events, wherein the database of events includes more than two sets of partitions;

determining a number of partitions of the database of events to access in order to obtain at least a predefined threshold number of the user-identified event with respect to at least one of;

a plurality of time periods, a plurality of geographic locations and a plurality of languages;

identifying instances of occurrence of the user-identified event in the determined number of partitions of the database of events to produce representative statistics of occurrence of the user-identified event within the entire database of events;

generating a result including a least a portion of the representative statistics of occurrence of the user-identified event, the result including sub-results comprising representative statistics of occurrence of the user-identified event, for at least one of;

a plurality of time periods, a plurality of geographic locations and a plurality of languages; and

sending to the client system for display at the client system the result, including the sub-results comprising representative statistics of occurrence of the user-identified event for at least one of;

a plurality of time periods, a plurality of geographic locations, and a plurality of languages.

4. The method of claim 1, including:

determining a first number of instances of occurrence of the user-identified event within a first set of partitions of the database of events;

in response to determining that the first number of instances of occurrence of the user-identified event within the first set of partitions does not exceed a predefined threshold,

selecting a second set of partitions of the database of events,

determining a second number of instances of occurrence of the user-identified event within the second set of partitions of the database of events, and

merging the first and second number of instances as the representative statistics of occurrence of the user-identified event within the entire database of events; and

in response to determining that the first number of instances of occurrence of the user-identified event exceeds the predefined threshold, estimating an occurrence frequency of occurrence of the user-identified event within the entire database of events in accordance with the first number of instances of occurrence of the user-identified event.

5. The method of claim 4, further comprising:

in response to determining that the first number of instances of occurrence of the user-identified event does not exceed the predefined threshold, estimating an occurrence frequency of occurrence of the user-identified event within the entire database of events in accordance with the first and second numbers of instances of occurrence of the user-identified event.

6. The method of claim 1, wherein an event in the database of events includes one or more mini-sessions, each mini-session having a user identifier, a temporal value, a geographic location value, and one or more query strings.

7. The method of claim 6, wherein the user identifier of a mini-session is based on a cookie of the mini-session.

8. The method of claim 6, wherein the representative statistics of occurrence of the user-identified event includes numbers of instances of the event within multiple time periods, and the method including aggregating instances of the event in a plurality of respective time periods based on their associated mini-session temporal values.

9. The method of claim 6, wherein the representative statistics of occurrence of the user-identified event includes numbers of instances of the event within multiple geographical regions, and the method including aggregating instances of the event in a plurality of respective geographical regions based on their associated mini-session geographic location values.

33. The method of claim 4, wherein a number of partitions included in the second set of partitions is selected based on the first number of instances of occurrence of the user-identified event within the first set of partitions.

34. The method of claim 1, further comprising:

generating a series of sub-queries based on the received query and one or more of;

a timeframe of query submission, a geographic location of query submission, and a language of query submission, wherein the instances of occurrence of the user-identified event correspond to instances of the sub-queries within partitions of the database of events.

53. The method of claim 1, further comprising:

generating a plurality of sub-queries, each sub-query corresponding to a distinct value of an event parameter of occurrence of the user-identified event, the event parameter selected from the set consisting of a geographic location, time period, and language; and

generating a respective sub-result, comprising representative statistics of occurrence of the user-identified event, for each of the generated sub-queries and sending the sub-results to the client system.

56. The method of claim 1, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods.

57. The method of claim 1, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods and said plurality of geographic regions.

58. The method of claim 1, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods and said plurality of languages.

2. (canceled)

3. (canceled)

10-32. -32. (canceled)

35. A computerized server system for generating user requested statistics, comprising:

memory;

one or more processors;

one or more programs stored in the memory and configured for execution by the one or more processors, the one or more programs including;

instructions for responding to a query from a client system for statistics of occurrence of a user-identified event, including;

instructions for accessing a database of events, wherein the database of events includes more than two sets of partitions;

instructions for determining a number of partitions of the database of events to access in order to obtain at least a predefined threshold number of the user-identified event with respect to at least one of;

a plurality of time periods, a plurality of geographic locations and a plurality of languages;

instructions for identifying instances of occurrence of the user-identified event in the determined number of partitions of the database of events to produce representative statistics of occurrence of the user-identified event within the entire database of events;

instructions for generating a result including a least a portion of the representative statistics of occurrence of the user-identified event, the result including sub-results comprising representative statistics of occurrence of the user-identified event, for at least one of;

a plurality of time periods, a plurality of geographic locations and a plurality of languages; and

instructions for sending to the client system for display at the client system the result, including the sub-results comprising representative statistics of occurrence of the user-identified event for at least one of;

a plurality of time periods, a plurality of geographic locations, and a plurality of languages.

36. The system of claim 35, the one or more programs including:

instructions for determining a first number of instances of occurrence of the user-identified event within a first set of partitions of the database of events;

instructions for execution in response to determining that the first number of instances of occurrence of the user-identified event within the first set of partitions does not exceed a predefined threshold, including;

instructions for selecting a second set of partitions of the database of events,

instructions for determining a second number of instances of occurrence of the user-identified event within the second set of partitions of the database of events, and

instructions for merging the first and second number of instances as the representative statistics of occurrence of the user-identified event within the entire database of events; and

instructions for execution in response to determining that the first number of instances of occurrence of the user-identified event exceeds the predefined threshold, including instructions for estimating an occurrence frequency of occurrence of the user-identified event within the entire database of events in accordance with the first number of instances of occurrence of the user-identified event.

37. The system of claim 36, the one or more programs including:

instructions for execution in response to determining that the first number of instances of occurrence of the user-identified event does not exceed the predefined threshold, including instructions for estimating an occurrence frequency of occurrence of the user-identified event within the entire database of events in accordance with the first and second numbers of instances of occurrence of the user-identified event.

38. The system of claim 35, wherein an event in the database of events includes one or more mini-sessions, each mini-session having a user identifier, a temporal value, a geographic location value, and one or more query strings.

39. The system of claim 38, wherein the user identifier of a mini-session is based on a cookie of the mini-session.

40. The system of claim 38, wherein the representative statistics of occurrence of the user-identified event includes numbers of instances of the event within multiple time periods, the one or more programs including instructions for aggregating instances of the event in a plurality of respective time periods based on their associated mini-session temporal values.

41. The system of claim 38, wherein the representative statistics of occurrence of the user-identified event includes numbers of instances of the event within multiple geographical regions, the one or more programs including instructions for aggregating instances of the event in a plurality of respective geographical regions based on their associated mini-session geographic location values.

42. The system of claim 35, wherein a number of partitions included in the second set of partitions is selected based on the first number of instances of occurrence of the user-identified event within the first set of partitions.

43. The system of claim 35, the one or more programs including:

instructions for generating a series of sub-queries based on the received query and one or more of;

a timeframe of query submission, a geographic location of query submission, and a language of query submission, wherein the instances of occurrence of the user-identified event correspond to instances of the sub-queries within partitions of the database of events.

54. The system of claim 35, the one or more programs including:

instructions for generating a plurality of sub-queries, each sub-query corresponding to a distinct value of an event parameter of occurrence of the user-identified event, the event parameter selected from the set consisting of a geographic location, time period, and language; and

instructions for generating a respective sub-result for each of the generated sub-queries and sending the sub-results to the client system.

59. The system of claim 35, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods.

60. The system of claim 35, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods and said plurality of geographic regions.

61. The system of claim 35, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods and said plurality of languages.

44. A non-transitory computer readable storage medium storing one or more programs for execution by one or more processors of a server computer system, the one or more programs comprising:

instructions for responding to a query from a client system for statistics of occurrence of a user-identified event, including;

instructions for accessing a database of events, wherein the database of events includes more than two sets of partitions;

instructions for determining a number of partitions of the database of events to access in order to obtain at least a predefined threshold number of the user-identified event with respect to at least one of;

a plurality of time periods, a plurality of geographic locations and a plurality of languages;

instructions for identifying instances of occurrence of the user-identified event in the determined number of partitions of the database of events to produce representative statistics of occurrence of the user-identified event within the entire database of events;

instructions for generating a result including a least a portion of the representative statistics of occurrence of the user-identified event, the result including sub-results comprising representative statistics of occurrence of the user-identified event, for at least one of;

a plurality of time periods, a plurality of geographic locations and a plurality of languages; and

instructions for sending to the client system for display at the client system the result, including the sub-results comprising representative statistics of occurrence of the user-identified event for at least one of;

a plurality of time periods, a plurality of geographic locations, and a plurality of languages.

45. The non-transitory computer readable storage medium of claim 44, the computer program mechanism comprising including:

instructions for determining a first number of instances of occurrence of the user-identified event within a first set of partitions of the database of events;

instructions for execution in response to determining that the first number of instances of occurrence of the user-identified event within the first set of partitions does not exceed a predefined threshold, including;

instructions for selecting a second set of partitions of the database of events,

instructions for determining a second number of instances of occurrence of the user-identified event within the second set of partitions of the database of events, and

instructions for merging the first and second number of instances as the representative statistics of occurrence of the user-identified event within the entire database of events; and

instructions for execution in response to determining that the first number of instances of occurrence of the user-identified event exceeds the predefined threshold, including instructions for estimating an occurrence frequency of occurrence of the user-identified event within the entire database of events in accordance with the first number of instances of occurrence of the user-identified event.

46. The non-transitory computer readable storage medium of claim 45, the computer program mechanism comprising including:

instructions for execution in response to determining that the first number of instances of occurrence of the user-identified event does not exceed the predefined threshold, including instructions for estimating an occurrence frequency of occurrence of the user-identified event within the entire database of events in accordance with the first and second numbers of instances of occurrence of the user-identified event.

47. The non-transitory computer readable storage medium of claim 44, wherein an event in the database of events includes one or more mini-sessions, each mini-session having a user identifier, a temporal value, a geographic location value, and one or more query strings.

48. The non-transitory computer readable storage medium of claim 47, wherein the user identifier of a mini-session is based on a cookie of the mini-session.

49. The non-transitory computer readable storage medium of claim 47, wherein the representative statistics of occurrence of the user-identified event includes numbers of instances of the event within multiple time periods, the computer program mechanism comprising including instructions for aggregating instances of the event in a plurality of respective time periods based on their associated mini-session temporal values.

50. The non-transitory computer readable storage medium of claim 47, wherein the representative statistics of occurrence of the user-identified event includes numbers of instances of the event within multiple geographical regions, the computer program mechanism comprising including instructions for aggregating instances of the event in a plurality of respective geographical regions based on their associated mini-session geographic location values.

51. The computer readable storage medium of claim 44, wherein a number of partitions included in the second set of partitions is selected based on the first number of instances of occurrence of the user-identified event within the first set of partitions.

52. The non-transitory computer readable storage medium of claim 44, the one or more programs including:

instructions for generating a series of sub-queries based on the received query and one or more of;

a timeframe of query submission, a geographic location of query submission, and a language of query submission, wherein the instances of occurrence of the user-identified event correspond to instances of the sub-queries within partitions of the database of events.

55. The non-transitory computer readable storage medium of claim 44, the computer program mechanism comprising including:

instructions for generating a plurality of sub-queries, each sub-query corresponding to a distinct value of an event parameter of occurrence of the user-identified event, the event parameter selected from the set consisting of a geographic location, time period, and language; and

instructions for generating a respective sub-result for each of the generated sub-queries and sending the sub-results to the client system.

62. The non-transitory computer readable storage medium of claim 44, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods.

63. The non-transitory computer readable storage medium of claim 44, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods and said plurality of geographic regions.

64. The non-transitory computer readable storage medium of claim 44, wherein the result includes sub-results, comprising representative statistics of occurrence of the user-identified event, for said plurality of time periods and said plurality of languages.