System and method for identifying geographical areas that significantly overlap a map view

• US 7,595,725 B1
• Filed: 04/07/2006
• Issued: 09/29/2009
• Est. Priority Date: 10/27/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Rose, Mark, Ramaswamy, Sridhar, Joseph, Joshy
• Primary Examiner(s): Crosland; Donnie L
• Application Number:
  US11/400,701
• Time in Patent Office: 1,271 Days
• Field of Search: 340/539.2, 340/990, 340/995.1
• US Class Current: 340/539.2
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0251 Targeted advertisements
• CPC Class Codes: G09B 29/006 Representation of non-cartographic information on maps, e.g. population distribution, wind direction, radiation levels, air and sea routes

Abstract

A system and method for identifying, from a set of geographical areas, a set of target areas that overlap a map view or view port of a map. Target areas are defined as circles having centers and radii, as sets of geographic cells overlaying the areas, or as other polygons of geographic data. Within a view port served or to be served to a user, multiple points are defined and substantially equally spaced within the view port, such that any target area that may significantly overlap the view port (e.g., at least a threshold percentage of the view port) is likely to overlap a minimum number of the points (e.g., one). Some or all target areas are then tested for intersection with some or all of the points, and calculations may be made to determine how much the intersecting areas actually overlap the view port.

Claims

1. A computer-implemented method of identifying which of a set of target geographical areas significantly overlap a view port of a map, wherein the computer includes a processor, the method comprising:

identifying a set of target areas, wherein each target area is associated with a message desired to be served with a view port overlapping the target area;

identifying a view port to be served to a user;

selecting a plurality of points within the view port; and

for each target area, determining whether the target area intersects one or more of the points.

2. The method of claim 1, further comprising:

filtering the target areas based on an amount of overlap between the target areas and the view port.

3. The method of claim 1, further comprising:

for each target area that intersects at least one of the plurality of points, estimating an overlap between the target area and the view port.

4. The method of claim 3, wherein said estimating an overlap comprises:

calculating the overlap as a percentage of the area of the view port.

5. The method of claim 3, wherein said estimating an overlap comprises:

identifying a number of the points overlapped by the target area.

6. The method of claim 1, further comprising:

identifying bounds of one or more target areas.

7. The method of claim 6, wherein said identifying bounds comprises:

for each of the one or more target areas, identifying a set of cells of geographic data overlaying the target area.

8. The method of claim 1, wherein said identifying a set of target areas comprises:

receiving from an advertiser a description of a target area of an advertisement, wherein said message is the advertisement.

9. The method of claim 1, wherein said identifying a view port comprises:

receiving from the user one or more parameters of the view port; and

constructing the view port based on the parameters.

10. The method of claim 9, wherein the parameters identify at least one of the target areas.

11. The method of claim 1, wherein said selecting comprises:

defining a grid of substantially equally spaced points within the view port.

12. The method of claim 11, wherein the points are defined such that a target area that overlaps the view port at least a threshold amount is likely to intersect at least one of the points.

13. The method of claim 12, wherein said threshold amount is approximately 25% of the view port.

14. The method of claim 1, wherein each target area is one of:

a city;

a metropolis;

a region;

a country;

a geographic circle having a center location and a radius; and

a geographic polygon.

15. A computer readable medium storing instructions that, when executed by a computer, cause the computer to perform a method of identifying which of a set of target geographical areas significantly overlap a view port of a map, the method comprising:

identifying a set of target areas, wherein each target area is associated with a message desired to be served with a view port overlapping the target area;

identifying a view port to be served to a user;

selecting a plurality of points within the view port; and

for each target area, determining whether the target area intersects one or more of the points.

16. A computer system for identifying target geographical areas that significantly overlap a view port of a map, the system comprising:

a first server configured to store information configured to be served with view ports encompassing the target geographical areas; and

a second server configured to serve view ports overlapping the target geographical areas;

a hierarchical spatial index comprising nodes corresponding to multiple layers of cells of geographical information; and

a boundary generator configured to, for each target geographical area;

identify a set of the cells of geographical information that encompass the target geographical area; and

determine bounds of the target geographical areas using said set of cells.

17. The computer system of claim 16, wherein said boundary generator is further configured to:

test for intersection between the target geographical areas and a plurality of points within the view port; and

calculate an amount of overlap of each target geographical area that intersects at least one of the plurality of points.