Adaptive distributed indexing of local adverts

• US 8,666,989 B1
• Filed: 12/02/2011
• Issued: 03/04/2014
• Est. Priority Date: 12/02/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gilliam, Emil, Wu, Ping
• Primary Examiner(s): HO, BINH VAN
• Application Number:
  US13/310,288
• Time in Patent Office: 823 Days
• Field of Search: 707/741
• US Class Current: 707/741
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06Q 30/0251 Targeted advertisements

Abstract

Techniques for storing and retrieving content associated with a specific geographic location include identifying discrete regions included in a bounding region and initializing a list of discrete regions and a count of identified local content. For each identified region: determining a number of content items included in the region; updating the region list with an ID of the identified region if it contains at least one content item; and adding the determined number of content items to the count of identified local content. Deciding whether to proceed to a next identified region includes determining if unprocessed regions remain and if a predetermined content limit was reached. The next region is then processed if there is a next region and the content limit has not been reached. The regions are processed, content IDs for content items associated with processed regions are located in a content database for further selection or serving.

Claims

1. A method of efficiently determining the number of local content items near a geographic location, the method comprising:

defining a bounding region around the geographic location;

selecting, from a distributed indexed table, one or more discrete local areas at least partially included in the bounding region,

where said local areas are selected based on their associated index values; and

where the associated index values for physically close local areas are numerically close so that a continuous set of index values in the distributed indexed table is stored on a particular device included distributed storage system;

building a data summary for the identified discrete local areas, said building including

creating, in a memory portion of the particular device, an array-type data structure having at least two array cells and an membership test condition for each cell, where each array cell is associated with a particular number or numerical range of content items;

testing, with at least one processor, the associated index value of each selected discrete local area against each membership test condition to determine a number of content items in the discrete local area; and

placing the associated index value of a particular selected local area into a particular array cell responsive to an indication during said testing that the particular selected local area meets the criteria of the membership test condition associated with that array cell, said adding being performed with said processor;

where the data summary is represented by the cells of the array-type data structure after said testing; and

using the data summary instead of a database query to provide a content server with information about numbers of content items in one or more portions of the bounding region.

2. The method of claim 1, where there is no array cell representing zero.

3. The method of claim 1, where the array-type data structure is a histogram having at least two buckets;

and

where the membership test condition for each bucket is a Bloom filter.

4. The method of claim 1, where said information about numbers of content items includes information about how many content items are in the bounding region and how the content items are distributed in the bounding region.

5. The method of claim 1, where the content items are advertisements associated with precise geographic locations within the discrete local areas.

6. The method of claim 1, where the discrete local area is an S2Cell.

7. The method of claim 1, where the index value of each discrete local area is a 64-bit identifier.

8. The method of claim 1, where the distributed indexed table has a plurality of rows and each row in the table includes a content item identifier and a precise geographic location such that each row is uniquely identified by the combination of the content item identifier and the precise geographic location.

9. The method of claim 8, where more than one row in the distributed indexed table may have the same index value.

10. A system, the system comprising:

a processor;

a non-transitory computer-readable memory containing instructions which, when read by the processor, cause the processor to perform a method of efficiently determining the number of local content items near a geographic location, the method including the steps of

defining a bounding region around the geographic location;

selecting, from a distributed indexed table, one or more discrete local areas at least partially included in the bounding region,

where said local areas are selected based on their associated index values; and

where the associated index values for physically close local areas are numerically close so that a continuous set of index values in the distributed indexed table is stored on a particular device included distributed storage system;

building a data summary for the identified discrete local areas, said building including

creating, in a memory portion of the particular device, an array-type data structure having at least two array cells and an membership test condition for each cell, where each array cell is associated with a particular number or numerical range of content items;

testing, with at least one processor, the associated index value of each selected discrete local area against each membership test condition to determine a number of content items in the discrete local area; and

placing the associated index value of a particular selected local area into a particular array cell responsive to an indication during said testing that the particular selected local area meets the criteria of the membership test condition associated with that array cell, said adding being performed with said processor;

where the data summary is represented by the cells of the array-type data structure after said testing; and

using the data summary instead of a database query to provide a content server with information about numbers of content items in one or more portions of the bounding region.