Pre-computed impression lists

• US 8,832,070 B1
• Filed: 07/29/2013
• Issued: 09/09/2014
• Est. Priority Date: 01/02/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Chamberlain, Dawn, Manku, Gurmeet Singh, Stanley, Barbara Ann
• Primary Examiner(s): Ly, Anh
• Application Number:
  US13/953,490
• Time in Patent Office: 407 Days
• Field of Search: 707/709, 707/710, 707/731, 707/E17.014, 707/E17.016, 707/E17.116, 707/E17.117, 715/234, 715/236, 715/744, 715/760, 715/968, 705/14.4, 705/14.41, 705/14.49, 709/203, 709217-219
• US Class Current: 707/709
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 715/968 interface for database querying and retrieval

Abstract

Systems, methods, and computer program products identify one or more web page impressions satisfying one or more simply queries, each of the one or more web page impressions associated with a respective impression ID. Respective impression IDs of the one or more web pages satisfying the one or more simple queries are stored in an impression log. Subsequent to storing the respective impression IDs, a query is received from a client device, and a number of impression IDs for the one or more web pages satisfying the query are identified based on the identified one or more web page impressions satisfying the one or more simple queries.

Claims

1. A computer-implemented method of identifying web page impressions that satisfy a query comprising:

receiving, from a client device, a query having a number of criteria greater than a predetermined number, wherein the number of criteria and the predetermined number are both greater than zero and less than infinity, and the query specifies one or more attributes of web page impressions;

generating a plurality of sub-queries from the query, including generating a first sub-query associated with first criteria and generating a second sub-query associated with second criteria, wherein each criterion of the query is represented in at least one of the plurality of sub-queries, and the first criteria and the second criteria are mutually exclusive;

obtaining a response for each of the sub-queries, from a database of web page impressions, wherein each response comprises identifiers of web page impressions satisfying criteria of the associated sub-query;

generating a response to the query by comparing the responses to the sub-queries; and

providing an answer to the client device based at least in part on said generating a response to the query by comparing the responses to the sub-queries.

2. The method of claim 1, wherein receiving a query that specifies one or more attributes further comprises receiving a query that specifies at least one of a language, a country, a state, a city, a postal code, a web browser type, and an operating system type.

3. The method of claim 1, further comprising:

computing a response to an initial query; and

storing a result of the initial query in an impression log prior to receiving the query from the client device.

4. The method of claim 1, wherein obtaining a response for each of the sub-queries further comprises obtaining a pre-computed response to at least one of the sub-queries.

5. The method of claim 1, wherein generating a response to the query further comprises determining an intersection of the obtained responses for the sub-queries.

6. The method of claim 1, wherein obtaining a response for each of the sub-queries further comprises identifying a number of identifiers of webpage impressions satisfying the criteria of each sub-query.

7. The method of claim 1, wherein providing an answer to the client device further comprises providing a number of web page impressions that have attributes that meet the criteria of the query.

8. A data processing apparatus coupled to a database of web page impressions, wherein said data processing apparatus includes a processor configured to:

receive, from a client device, a query having a number of criteria greater than a predetermined number, wherein the number of criteria and the predetermined number are both greater than zero and less than infinity, and the query specifies one or more attributes of web page impressions;

generate a plurality of sub-queries from the query, wherein each criterion of the query is represented in at least one of the plurality of sub-queries;

obtain a response for each of the sub-queries, from the database of web page impressions, wherein each response comprises identifiers of web page impressions satisfying criteria of the associated sub-query;

generate a response to the query by comparing the responses to the sub-queries; and

provide an answer to the client device based at least in part on the generated response, by at least providing a number of web page impressions that have attributes that meet the criteria of the query.

9. The data processing apparatus of claim 8, further configured to receive a query that specifies one or more attributes by receiving a query that specifies at least one of a language, a country, a state, a city, a postal code, a web browser type, and an operating system type.

10. The data processing apparatus of claim 8, further configured to generate a plurality of sub-queries from the query by generating a first sub-query associated with first criteria and generating a second sub-query associated with second criteria, wherein the first criteria and the second criteria are mutually exclusive.

11. The data processing apparatus of claim 8, further configured to:

compute a response to an initial query; and

store a result of the initial query in an impression log prior to receiving the query from the client device.

12. The data processing apparatus of claim 8, further configured to obtain a response for each of the sub-queries by obtaining a pre-computed response to at least one of the sub-queries.

13. The data processing apparatus of claim 8, further configured to generate a response to the query by determining an intersection of the obtained responses for the sub-queries.

14. The data processing apparatus of claim 8, further configured to obtain a response for each of the sub-queries by identifying a number of identifiers of webpage impressions satisfying the criteria of each sub-query.

15. A computer-readable storage device having computer-executable instructions embodied thereon, wherein when executed by a data processing apparatus coupled to a database of web page impressions, the computer-executable instructions cause the data processing apparatus to perform the steps of:

computing a response to an initial query;

storing a result of the initial query in an impression log;

receiving, from a client device, a subsequent query having a number of criteria greater than a predetermined number, wherein the number of criteria and the predetermined number are both greater than zero and less than infinity, and the subsequent query specifies one or more attributes of web page impressions;

generating a plurality of sub-queries from the subsequent query, wherein each criterion of the subsequent query is represented in at least one of the plurality of sub-queries;

obtaining a response for each of the sub-queries, from the database of web page impressions, wherein each response comprises identifiers of web page impressions satisfying criteria of the associated sub-query;

generating a response to the subsequent query by comparing the responses to the sub-queries; and

providing an answer to the client device based at least in part on said generating a response to the subsequent query by comparing the responses to the sub-queries.

16. The computer-readable storage device of claim 15, further comprising computer-executable instructions such that receiving a subsequent query that specifies one or more attributes further comprises receiving a subsequent query that specifies at least one of a language, a country, a state, a city, a postal code, a web browser type, and an operating system type.

17. The computer-readable storage device of claim 15, further comprising computer-executable instructions such that generating a plurality of sub-queries from the subsequent query further comprises generating a first sub-query associated with first criteria and generating a second sub-query associated with second criteria, wherein the first criteria and the second criteria are mutually exclusive.