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

[0001] This application claims priority to U.S. Provisional Application No. 60/731,460, filed Oct. 27, 2005, which is hereby incorporated by reference. This application is related to U.S. patent application Ser. No. 11/399,949, entitled “System and Method for Identifying Bounds of a Geographical Area”, and U.S. patent application Ser. No. 11/399,950, entitled “System and Method for Selecting Targeted Information for Serving with a Map View”, both of which were filed Apr. 7, 2006.

[0002] This invention relates to the field of computer systems. More particularly, a system and methods are provided for efficiently identifying geographical areas that overlap a map view at least a threshold percentage or amount.

[0003] Mapping software is very popular with many computer users, who may rely upon it for obtaining directions, becoming familiar with a new area, finding points of interest, locating a business establishment, etc. Existing methods of electronically displaying maps are typically capable of locating and displaying a specific address or landmark (e.g., an airport) within a particular geographical area (e.g., a city, a state, a country). However, they are generally not capable of identifying or determining boundaries of the geographical area, and may therefore be unable to provide supplemental information (e.g., advertisements, descriptions of sites of interest) pertaining just to that area.

[0004] For example, advertisers are often interested in having advertisements for their establishments or products displayed for users who open an electronic map to view an area in which their establishment is located or their product is available. Thus, a hotel or restaurant may wish to have an advertisement served with (e.g., overlaid upon) a map centered within some distance of their location.

[0005] However, the area covered by the user's view port may overlap multiple cities, metropolitan regions or other areas that the advertiser is not interested in or that are not covered by the advertiser's agreement with the map provider or service. Or, the advertiser may want its advertisement served with maps covering a general area (e.g., a city, a metropolitan region). In either scenario, it is necessary to determine whether a map display provided to a user overlaps an advertiser's area(s) of interest and, possibly, whether it overlaps more or less than a threshold amount.

[0006] Unfortunately, mapping software cannot readily determine where one geographical area (e.g., city, metropolitan region) ends and another begins. Even if the data used to display an area shows purported boundaries (e.g., if the electronic map is simply a copy of a printed map), those boundaries are not coded in a manner decipherable by the software (e.g., as latitude/longitude coordinates).

[0007] If the mapping algorithm or software is not capable of identifying boundaries of geographical areas, then it cannot properly limit the display of a particular advertisement to appropriate map views, and may not be able to determine which advertisements to display for a particular view.

[0008] Similarly, if a mapping algorithm or tool cannot identify the boundaries or extent of a geographical area, then the algorithm or tool will also be incapable of determining which areas overlap a map view. This will also negatively affect the ability to select and/or display advertisements appropriate to the view.

[0009] Yet further, even if a mapping tool was capable of identifying boundaries of geographical areas, and could determine whether a particular area overlapped a user's view of a map, it may not be desirable to automatically display all advertisements associated with all overlapping areas. For example, if an advertiser's target area of interest overlaps only a very small portion of the user's view, then it may be preferable for an advertisement associated with that area to be omitted, or lowered in priority with regard to advertisements associated with areas comprising much larger portions of the view.

[0010] A system and method for identifying a set of target geographical 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. Each target area has an associated message or information (e.g., an advertisement) that may be served with view ports of that area.

[0011] Within a view port served or to be served to a user, multiple points are substantially equally spaced within the view port, such that any target area that significantly overlaps the view port (e.g., by at least a threshold percentage of the view port, such as 25%) is likely to overlap at least 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.

[0020] The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of particular applications of the invention and their requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art and the general principles defined herein may be applied to other embodiments and applications without departing from the scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown, but is to be accorded the widest scope consistent with the principles and features disclosed herein.

Introduction

[0021] Embodiments of the invention described herein facilitate the identification or selection of advertisements, announcements and/or other messages to be displayed to users or viewers of an electronic map. The map may encompass or overlay virtually any geographical area(s) and may be used for virtually any purpose, such as navigation (e.g., driving directions), searching for a particular type of business (e.g., a shopping mall, a restaurant), locating landmarks or sites of interest (e.g., parks, airports), etc. An embodiment of the invention may be implemented with a map derived from imagery (e.g., aerial, satellite), from rendering of a printed map, from other sources or any combination of sources.

[0022] In one embodiment of the invention, a system and method are provided for determining a geographical area's bounds, to facilitate a determination as to whether a map view (or view port) intersects the area. The area may be a city, a metropolis (e.g., metropolitan area), a region (e.g., a state, a county), a country, etc.

[0023] In one implementation of this embodiment, areas are first associated with points or sets of points within the areas (e.g., latitude/longitude coordinates of city centers). Areas are then iteratively increased in size until a collision occurs with a neighboring area or some other terminating condition arises, at which time the expansion in the direction of the collision is stopped. By repeating this process until a perimeter is defined (i.e., by collisions), an outline of the area is identified. Illustratively, if no geographical data are available in a particular direction, or a topographical feature is encountered (e.g., an ocean), expansion in that direction may halt without a collision.

[0024] In another embodiment of the invention, the boundaries of one or more geographical areas are used to determine whether and how much an area overlaps a user's map view or view port. In this embodiment, a number of points or zones are defined within the view port. Intersections between the points or zones and one or more geographical areas may then be calculated to determine which areas overlap the view port and possibly estimate how much they overlap.

[0025] In yet another embodiment of the invention, advertisements associated with particular geographical areas are selected for serving with a view port based on whether and/or how much those areas overlap the view port. Illustratively, advertisements to be served with a view port may be selected based on the geographical area(s) within the view port. However, an advertisement associated with an area that comprises a tiny portion of the view port may be omitted or reduced in priority compared to an advertisement associated with an area that covers a large majority of the view port.

[0026] Embodiments of the invention described below may be implemented by map providers, advertisers and/or other organizations. For example, a map provider may select or generate a map view based on a user's request, then query an ad server for ads appropriate to the user's view port and serve the map and ads together.

[0027] FIG. 1 is a block diagram of a computing environment in which an embodiment of the invention may be implemented.

[0028] In FIG. 1, users 102 operate any type or types of client devices that are capable of displaying a view of an electronic map (e.g., computers, personal digital assistants, smart phones). The user's view of a map may be termed a map view or view port. Users' client devices are coupled to network 104 and/or other communication links coupled to mapping system 110, which comprises ad server 120 and map server 130. The components of mapping system 110 may be physically and/or logically distributed. In one embodiment of the invention, network 104 comprises the Internet.

[0029] Ad server 120 selects ads from data store 122 for serving to users, based on criteria such as a user's map view, search query, language, etc. Criteria for selecting an ad may be received from map server 130 and/or other sources (e.g. a web server through which a user accesses the functions of mapping system 110).

[0030] Data store 122 stores information regarding targeting constraints of ads, such as when or to which users a particular ad should or should not be served. For example, one or more geographic areas may be associated with an ad, so that the ad is only (or preferably) served with map views that include or overlap with the associated area(s).

[0031] Data store 122 also stores geographic information about cities, metropolises, regions (e.g., states), countries and/or other target geographic areas or locations associated with ads handled by the ad server. The data store records relationships between these areas, such as which larger area (e.g., region, country) a particular smaller area (e.g., city, metropolis) is part of, and which smaller areas (e.g., cities) are part of a particular larger area (e.g., metropolis, region, country).

[0032] The data store may also include latitude/longitude coordinates associated with any of these areas, particularly cites. Illustratively, the latitude/longitude coordinate of a city may correspond to the center of the city.

[0033] Map server 130 is responsible for displaying map views and ads, based on factors such as user input, ad parameters, video resolution, display device and so on. Ads to be served to users are received by map server 130 from ad server 120 via RPC (Remote Procedure Call) or other suitable means.

[0034] Boundary generator 132 is configured to determine a boundary of a geographic area or location reflected in data store 122, and may also be configured to generate or retrieve coordinates (e.g., latitude/longitude coordinates) of an area (e.g., from the data store).

[0035] Spatial index 134 comprises an index of all the geographic areas or locations reflected in data store 122, and may be constructed by boundary generator 132, or from data generated by the boundary generator. The spatial index may also be used to compare an advertiser's area of interest with a user's view port of a map, and may determine whether, and possibly how much, the area of interest overlaps the view port. As described below, the spatial index may be organized as a hierarchical collection of nodes corresponding to geographic cells or zones.

Determining Bounds of a Geographical Area

[0036] In an embodiment of the invention, a boundary is determined for a geographical area, which may be a city, a metropolis, a region (e.g., a county or state) or a country. In other implementations, boundaries of areas of other scopes may be determined. Area boundaries may be computed in advance of users' queries for maps or map views, or may be computed as needed.

[0037] This embodiment of the invention makes use of a spatial index (e.g., spatial index 134 of FIG. 1), a database or other collection of geographic or geospatial data covering all areas whose bounds are to be determined. For example, some or all of the earth's surface may be divided into cells of data.

[0038] In this example, the six faces of a cube encompassing the earth are projected onto the earth. Those six projections become the top layer cells (i.e., layer 1) in the hierarchy because they reflect the first geographical division of the earth's surface. The spatial index thus includes six nodes at level one, corresponding to the six initial cells.

[0039] Each first layer cell is then subdivided in quad-tree fashion into four child cells at the next layer. This subdivision scheme may be repeated as many times as desired, to generate any number of layers of cells.

[0040] At each successive layer or level, cells decrease in size and increase in number. Illustratively, cells that comprise only water or that do not comprise any geographic area of interest are not further subdivided. For example, at least one coordinate (e.g., one latitude/longitude point) may be known for each area of interest. If a given cell encompasses none of those points, it may not be further subdivided. A set of geographical areas of interest may be derived from the areas reflected in a data store such as data store 122 of FIG. 1 (e.g., target areas of advertisements or other information).

[0041] In one embodiment of the invention, this subdivision may be repeated until approximately 30 layers of cells are defined (e.g., layers 1-30). With the earth as the starting sphere, this yields leaf cells covering approximately one square centimeter. However, cells at a given level M may not all be the same size. For example, geographic cells near the equator will be longer in their longitudinal dimension than cells at the same level located nearer either pole.

[0042] The data can be stored or arranged as a tree having a root (e.g., layer 0) that represents the entire realm of data (e.g., the earth, a continent), leaf cells (e.g., at layer N), and any number of intermediate layers or levels of cells. Cells at “higher” layers (e.g., layers 1, 2) are closer to the root and cover larger areas than cells at “lower” layers (e.g., layer N−1) closer to the leaf cells. A hierarchical spatial index can then be constructed with nodes corresponding to the cells.

[0043] In another implementation, different cell division schemes may be applied with different starting areas (e.g., different continents), different initial cell definitions (e.g., dividing each upper layer cell into nine lower layer cells instead of four), etc.

[0044] FIGS. 2-5 demonstrate methods of determining bounds of geographical areas according to an embodiment of the invention. Other embodiments may be derived from the following descriptions without exceeding the scope of the invention.

[0045] FIG. 2 demonstrates a method of determining the bounds of cities. In operation 202, the cities for which bounds are to be determined are identified. Any number of cities may be selected, such as all cities associated with advertisements or other information that may be served with a user's map view.

[0046] In operation 204, locations of those cities are identified. For example, longitude and latitude coordinates for each city may be determined by retrieving them from storage (e.g., data store 122 of FIG. 1), looking them up in a suitable geospatial database, etc. A city's coordinates may correspond to the city's center (e.g., geographical center, downtown, political center), but need not be exact.

[0047] Also in operation 204, a grid of leaf cells of geographical data that cover each city's coordinates is identified. The size of the leaf cells will depend upon how many levels or layers were defined in the hierarchy of cells and the corresponding spatial index (i.e., at what level of the hierarchy the leaf cells reside).

[0048] In one implementation in which the spatial index comprises approximately 30 layers, a city's coordinates may be used to lookup a central leaf cell for the city that encompasses those coordinates. Then, eight additional leaf cells that adjoin the central leaf cell in all directions (i.e., horizontally, vertically and on both diagonals) are also identified unless, possibly, they are undefined (i.e., consist of no geographic or geospatial data) or comprise ocean or other topographical features that are not considered. Thus, in this implementation, 3×3 grids of leaf cells (i.e., nine leaf cells) covering all or a portion of each city are now defined.

[0049] In one alternative implementation, some other number of cells is placed over the cities' coordinates, and may be leaf cells or cells at any other level of the spatial index hierarchy. For example, the latitude/longitude coordinates of a city may be used to identify the central intersection of a 2×2 or 4×4 grid of cells.

[0050] In operation 206, the cities' grids of leaf cells are replaced with initial ancestor cells at a default or specified level in the spatial index hierarchy, in order to cover an initial area of a desired size. As described below, cities' initial areas will be iteratively expanded until some terminating condition is satisfied, at which time their boundaries will have been delineated.

[0051] In the illustrated embodiment of the invention, if the desired starting area for a city for calculating its boundaries is approximately one square mile, leaf cells comprising the city's 3×3 grid of leaf cells (e.g., at level 30) are replaced with initial cells at such a level (e.g., level 13) that the combined size of the initial cells is approximately one square mile.

[0052] Different cities may have initial areas of different sizes. Therefore, the spatial index level of cells used to construct the (e.g., 3×3) grid of leaf cells in operation 204 and/or the initial city cells in operation 206 may be different for different cities. For example, if it is known that a city is of a particular size or within a particular size range, the layer from which initial cells are selected to construct its starting area may be selected accordingly.

[0053] Also, cities' initial cells are selected so that no initial cell is associated with more than one city.

[0054] In operation 208, any or all of the cities are tested to determine if any of their initial cells would collide (e.g., overlay, intersect) if replaced with their immediate ancestors. In the illustrated method, a collision occurs if cells of two or more different cities would be replaced with the same ancestor cell.

[0055] Therefore, a given cell at level N will not be replaced with its level N−1 ancestor cell if two or more of the N−1 ancestor's descendants belong to different cities. More specifically, in this embodiment, any given cell and all of its descendants belong to at most one city.

[0056] The size of a city's initial cells may make unlikely for a collision to occur at this stage, especially if only relatively large or popular cities were selected in operation 202, as they would likely be far enough apart that their initial cells' ancestors are distinct from each other.

[0057] In operation 210, each cell (e.g., at layer N) that can expand without collision is replaced with the next larger cell (i.e., the cell at layer N−1 that includes the cell). Thus, multiple adjacent cells having the same immediate ancestor may be replaced with a single larger cell.

[0058] In one implementation, a cell at a given level (or set of adjacent cells having the same ancestor) also may not be replaced or expanded if it is known that the next larger cell comprises no useful geospatial or geographic data not already covered by the existing cells. For example, if the only content of the next larger cell not covered by existing cells is undefined (e.g., no data available), does not include or is not part of any geographical area of interest, or comprises ocean or some other limiting or non-land topographical feature, those existing cells may not be replaced.

[0059] Each time cells at one layer of the data tree are to be replaced with cells at the next higher layer, replacements are attempted for all cities before moving on to the next round of replacements. In other words, all cells at a given level M that can be replaced or expanded without collision, are replaced with their level M−1 ancestor cells before any level M−1 cells are considered for replacement or expansion. This ensures that each city's bounds are allowed to grow at the same rate.

[0060] In operation 212, it is determined whether any of the replacement cells would collide if expanded. When a cell of one city cannot be expanded or replaced without colliding with another city, it can be determined that a boundary between the two cities has been detected. The boundary at the cells that collided may be derived from one of the colliding cells (e.g., one of its sides or corners, a midpoint of a side of the cell), midpoints of the colliding cells, or in some other manner.

[0061] Expansion of cells, or replacement of cells with larger cells, may also halt for reasons other than collisions. For example, in one implementation, expansion may halt automatically after a given number of iterations of cell replacements, even if a collision has not yet occurred. This would prevent a city's boundaries from expanding so far that they encompass an unreasonably large area.

[0062] In another implementation, expansion or replacement of a cell associated with a city may cease when the other three of its ancestor cell's four descendants are unassigned. In this implementation, an unassigned cell is a cell that is not associated with any area of interest (e.g., any city, metropolis, region or country associated with information served to users with map views). For example, unassigned cells may cover water (e.g., ocean, lake) or land that does not include any cities of interest.

[0063] In another implementation, expansion may cease for a city based on some categorization of the city. For example, some or all cities may be categorized based on size (e.g., large, medium, small), population, population density or other factor(s). In this case a determination may be made that all residents of the city, or some high percentage thereof, likely reside within a particular distance of the city's coordinates. Expansion may halt when that distance from the city's coordinates has been reached.

[0064] In yet another implementation, phantom cities or other areas may be defined to act as stopping points for cell expansion or replacement. For example, one or more phantom cities associated with no metropolis or a phantom metropolis may be placed around an island that includes a city (e.g., Honolulu). As cells associated with the city are expanded, if a collision is detected with a phantom city then expansion of the city's bounds is halted in that direction. Cells of a phantom area may or may not be expanded when determining boundaries of cities and/or other areas.

[0065] In operation 214, it is determined whether sufficient boundaries have been delimited for all cities of interest. In one implementation, when no cells of a particular city can be expanded or enlarged any further (e.g., because they would collide with cells from other cities), then a boundary of that city has been identified. The actual bounds assigned to the city may be derived from an outline of the cells, by a line connecting their midpoints or points of collision, etc.

[0066] In an embodiment of the invention, cities' bounds may be used as the starting point for finding bounds of larger areas, such as metropolises, regions (e.g., states) and countries.

[0067] FIG. 3 demonstrates a method of identifying bounds of one or more metropolises, according to an embodiment of the invention.

[0068] In operation 302, one or more cities deemed to lie within the boundaries of each metropolis are identified. A metropolis may be based on a single city (e.g., New York city) or multiple cities (e.g., Minneapolis and St. Paul).

[0069] Illustratively, every city for which bounds have been determined or will be determined (e.g., as described in FIG. 2) is either associated with a metropolis that is deemed to include the city, or is specifically coded as not being part of any metropolis. The latter condition may be used to help identify boundaries of a metropolis, region, state or other relatively large area, by ensuring the area is not expanded to include cities that don't belong in the area.

[0070] Thus, in operation 302, any or all cities for which bounds were (or will be) determined and that are part of a metropolis may be selected to start the process of defining that metropolis' boundaries.

[0071] In operation 304, coordinates of each selected city within the selected metropolises are identified, such as the latitude and longitude coordinates of each city's center. And, leaf cells of geographical data that cover each city's coordinates are identified, along with some number of adjacent cells. Illustratively, in the same manner as described above in conjunction with FIG. 2, a 3×3 grid of leaf cells may be selected, preferably with the center cell covering the city's coordinates (especially if those coordinates correspond to the city's center).

[0072] In operation 306, the cities' leaf cells are replaced with initial ancestor cells at a default or specified level in the spatial index hierarchy, in order to cover an initial city area of a desired size. The spatial index layer from which initial cells are selected, and the resulting initial city areas may or may not be the same as described above in conjunction with FIG. 2. However, cities' initial cells are selected so that no initial cell is associated with more than one city. All initial cells of cities in one metropolis are considered to be part of, or associated with, that metropolis.

[0073] In operation 308, any or all of the cities are tested to determine if any of their initial cells would collide (e.g., overlay, intersect) if replaced with their immediate ancestors. In the illustrated method, a collision occurs if cells of two or more different metropolises (or cells of a metropolis and a city not part of any metropolis) would be replaced with the same ancestor cell.

[0074] Therefore, a given cell at level N will not be replaced with its level N−1 ancestor cell if two or more of the N−1 ancestor's descendants belong to different metropolises (or to a metropolis and a city that is not part of any metropolis). More specifically, in this embodiment, any given cell and all of its descendants belong to at most one metropolis.

[0075] The size of a metropolis' initial cells may make this occurrence unlikely, especially if the metropolises selected in operation 302 are distant from each other and comprise a close cluster of cities.

[0076] In operation 310, each initial cell (e.g., at layer N) that can expand without collision is replaced with the next larger cell (i.e., the cell at layer N−1 that includes the initial cell). Thus, multiple adjacent cells having the same immediate ancestor may be replaced with a single larger cell.

[0077] In one implementation, a cell at a given layer that is part of a metropolis (or a set of adjacent cells belonging to the same cell at the next higher layer) also may not be replaced if it is known that the next larger cell comprises no useful geospatial or geographic data not already covered by the existing cells, or no data that is part of the metropolis. For example, if the only content of the next larger cell not covered by existing cells is undefined (e.g., no data available), does not include or is not part of any geographical area of interest, or comprises ocean or some other limiting topographical feature, those existing cells may not be replaced.

[0078] Each time cells at one layer of the data tree are to be replaced with cells at the next higher layer, replacements are attempted for all cells of all metropolises at the same layer before moving on to the next round of replacements. This ensures that each metropolis' boundaries are allowed to grow at the same rate.

[0079] In operation 312, it is determined whether any of the replacement cells would, if expanded further, collide with a cell associated with a different metropolis or a city that is not part of a metropolis. For example, while determining the boundaries of a San Francisco metropolis, expansion of a cell associated with that metropolis may cause a collision with a cell associated with a San Jose metropolis or a city not part of a metropolis (e.g., Fremont). This indicates that a boundary of the San Francisco metropolis has been located.

[0080] Expansion of cells, or replacement of cells with larger cells, may also halt for reasons other than collisions. For example, in one implementation expansion may halt automatically after a given number of iterations of cell replacements even if a collision has not yet occurred. This would prevent a metropolis' bounds from expanding so far that they encompass an unreasonably large area.

[0081] In another implementation, expansion or replacement of a cell associated with a metropolis may cease when the other three of its ancestor cell's four immediate descendants are unassigned.

[0082] In operation 314, it is determined whether sufficient boundaries have been delimited for all metropolises of interest. In one implementation, when no cells of a particular metropolis can be expanded or enlarged any further (e.g., because they would collide with cells from other metropolises or cities not part of metropolises), then a boundary of that metropolis has been identified. The actual bounds assigned to the metropolis may be derived from an outline of its cells, by a line connecting their midpoints or points of collision, etc.

[0083] In one alternative implementation of this embodiment of the invention, bounds of a metropolis may be determined by starting with the bounds of one or more cities within the metropolis, and then expanding or replacing those cities' cells as described previously. A method such as the one described in conjunction with FIG. 2 may be used to identify city bounds. Illustratively, all cells associated with the cities may iteratively be expanded to a common level first (e.g., the highest layer of cell reached while determining the cities' bounds), while testing for collisions, before expanding to a higher layer.

[0084] FIG. 4 demonstrates a method of determining regional bounds according to an embodiment of the invention. In this embodiment of the invention, a region corresponds to a state or county in the United States, but may correspond to provinces, cantons, districts or other areas within other countries.

[0085] In operation 402, one or more cities and/or metropolises deemed to lie within the bounds of each selected region are identified. Illustratively, every city for which bounds have been determined or will be determined (e.g., as described in FIG. 2), and possibly every metropolis for which bounds have been determined or will be determined (e.g., as described in FIG. 3), is associated with a region that is deemed to include the city (or metropolis), or is specifically coded as not being part of any region. The latter condition may be used to help identify bounds of a regional area by ensuring the area is not expanded to include cities or metropolises not actually part of the region.

[0086] Thus, in operation 402, any or all cities for which bounds were determined and that lie within a region may be selected to start the process of defining that region's bounds.

[0087] In operation 404, coordinates of each selected city within the selected regions are identified, such as the latitude and longitude coordinates of each city's center. And, leaf cells of geographical data that cover each city's coordinates are identified, along with some number of adjacent cells. Illustratively, in the same manner as described above in conjunction with FIG. 2, a 3×3 grid of leaf cells may be selected, preferably with the center cell covering the city's coordinates (especially if those coordinates correspond to the city's center).

[0088] In operation 406, the cities' leaf cells are replaced with initial ancestor cells at a default or specified level in the spatial index hierarchy, in order to cover an initial city area of a desired size. The spatial index layer from which initial cells are selected, and the resulting initial city areas may or may not be the same as described above in conjunction with FIG. 2. However, cities' initial cells are selected so that no initial cell is associated with more than one city. All initial cells of cities in one region are considered to be part of, or associated with, that region.

[0089] In operation 408, any or all of the cities are tested to determine if any of their initial cells would collide (e.g., overlay, intersect) if replaced with their immediate ancestors. In the illustrated method, a collision occurs if cells of two or more different regions (or cells of a region and a city or metropolis not part of any region) would be replaced with the same ancestor cell.

[0090] Therefore, a given cell at level N will not be replaced with its level N−1 ancestor cell if two or more of the N−1 ancestor's descendants belong to different regions (or to a region and a city or metropolis that is not part of any region). More specifically, in this embodiment, any given cell and all of its descendants belong to at most one region.

[0091] In operation 410, each initial cell (e.g., at layer N) that can expand without collision is replaced with the next larger cell (i.e., the cell at layer N−1 that includes the initial cell). Thus, multiple adjacent cells having the same immediate ancestor may be replaced with a single larger cell.

[0092] In one implementation, a regional cell at a given layer (or set of adjacent cells belonging to the same cell at the next higher tree layer) also may not be replaced if it is known that the next larger cell comprises no useful geospatial or geographic data not already covered by the existing cells, or no data that is part of the region. For example, if the only content of the next larger cell not covered by existing cells is undefined (e.g., no data available), does not include or is not part of any geographical area of interest, or comprises ocean or some other limiting topographical feature, those existing cells may not be replaced.

[0093] Each time cells at one layer of the data tree are to be replaced with cells at the next higher layer, replacements are attempted for all regions' cells at the same layer before moving on to the next round of replacements. This ensures that each region's boundaries are allowed to grow at the same rate.

[0094] In operation 412, it is determined whether any of the replacement cells would, if expanded further, collide with a cell associated with a different region or a city (or metropolis) that is not part of a region.

[0095] Expansion of cells, or replacement of cells with larger cells, may also halt for reasons other than collisions. For example, in one implementation, expansion may halt automatically after a given number of iterations of cell replacements even if a collision has not yet occurred. This would prevent a region's bounds from expanding so far that they encompass an unreasonably large area.

[0096] In another implementation, expansion of a cell associated with a region may cease when the other three of its ancestor cell's four subcells are unassigned.

[0097] In operation 414, it is determined whether sufficient boundaries have been delimited for all regions of interest. In one implementation, when no cells of a particular region can be expanded or enlarged any further (e.g., because they would collide with cells from other regions, or with cells of cities or metropolises not part of any region), then a boundary of that region has been identified. The actual bounds assigned to the region may be derived from an outline of its cells, by a line connecting their midpoints or points of collision, etc.

[0098] In one alternative implementation of this embodiment of the invention, bounds of a region may be determined by starting with the bounds of one or more cities (and/or metropolises) within the region, and then expanding or replacing those cells as described previously. A method such as the one described in conjunction with FIG. 2 may be used to identify city bounds and a method as described in conjunction with FIG. 3 may be used to identify metropolitan bounds. Illustratively, all cells associated with the cities (and/or metropolises) may iteratively be expanded to a common level first (e.g., the highest layer of cell reached while determining the cities' boundaries), while testing for collisions, before expanding to a higher layer.

[0099] FIG. 5 demonstrates a method of determining bounds of one or more countries, according to an embodiment of the invention.

[0100] In operation 502, one or more cities, metropolises and/or regions deemed to lie within the bounds of each selected country are identified. Illustratively, every city, metropolis and region for which bounds have been determined or will be determined is associated with a country that is deemed to include the city, metropolis or region, or is specifically coded as not being part of any country. The latter condition may be used to help identify bounds of a country by ensuring the country is not expanded to include areas not actually part of the country.

[0101] Thus, in operation 502, any or all cities and/or other areas (e.g., metropolises, regions) for which bounds were determined and that lie within a country may be selected to start the process of defining that country's bounds.

[0102] In operation 504, coordinates of each selected city or other area within the selected countries are identified, such as the latitude and longitude coordinates of each city's center. And, leaf cells of geographical data that cover each city's coordinates are identified, along with some number of adjacent cells. Illustratively, in the same manner as described above in conjunction with FIG. 2, a 3×3 grid of leaf cells may be selected, preferably with the center cell covering the city's coordinates (especially if those coordinates correspond to the city's center).

[0103] In operation 506, the cities' leaf cells are replaced with initial ancestor cells at a default or specified level in the spatial index hierarchy, in order to cover an initial city area of a desired size. The spatial index layer from which initial cells are selected, and the resulting initial city areas may or may not be the same as described above in conjunction with FIG. 2. However, cities' initial cells are selected so that no initial cell is associated with more than one city. All initial cells of cities in one country are considered to be part of, or associated with, that country.

[0104] In operation 508, any or all of the cities are tested to determine if any of their initial cells would collide (e.g., overlay, intersect) if replaced with their immediate ancestors. In the method of FIG. 5, a collision occurs if cells of two or more different countries (or cells of a country and either a city, metropolis or region not part of any country) would be replaced with the same ancestor cell.

[0105] Therefore, a given cell at level N will not be replaced with its level N−1 ancestor cell if two or more of the N−1 ancestor's descendants belong to different countries (or to a country and either a city, metropolis or region that is not part of any country). More specifically, in this embodiment, any given cell and all of its descendants belong to at most one country.

[0106] In operation 510, each initial cell (e.g., at layer N) that can expand without collision is replaced with the next larger cell (i.e., the cell at layer N−1 that includes the initial cell). Thus, multiple adjacent initial cells may be replaced with a single larger cell.

[0107] In one implementation, a country cell at a given layer (or set of adjacent cells belonging to the same cell at the next higher tree layer) also may not be replaced if it is known that the next larger cell comprises no useful geospatial or geographic data not already covered by the existing cells, or no data that is part of the country. For example, if the only content of the next larger cell not covered by existing cells is undefined (e.g., no data available), does not include or is not part of any geographical area of interest, or comprises ocean or some other limiting topographical feature, those existing cells may not be replaced.

[0108] Each time cells at one layer of the data tree are to be replaced with cells at the next higher layer, replacements are attempted for all countries' cells at the same layer before moving on to the next round of replacements. This ensures that each country's bounds are allowed to grow at the same rate.

[0109] In operation 512, it is determined whether any of the replacement cells would, if expanded further, collide with a cell associated with a different country or a city (or metropolis or region) that is not part of a country.

[0110] Expansion of cells, or replacement of cells with larger cells, may also halt for reasons other than collisions. For example, in one implementation, expansion may halt automatically after a given number of iterations of cell replacements even if a collision has not yet occurred. This would prevent a country's bounds from expanding so far that they encompass an unreasonably large area.

[0111] In another implementation, expansion of a cell associated with a country may cease when the other three of its ancestor cell's four subcells are unassigned.

[0112] In operation 514, it is determined whether sufficient boundaries have been delimited for all countries of interest. In one implementation, when no cells of a particular country can be expanded or enlarged any further (e.g., because they would collide with cells from other countries, or areas not part of any country), then a boundary of that country has been identified. The actual bounds assigned to the country may be derived from an outline of its cells, by a line connecting their midpoints or points of collision, etc.

[0113] In one alternative implementation of this embodiment of the invention, bounds of a country may be determined by starting with the bounds of one or more cities (and/or metropolises and regions) within the country, and then expanding or replacing those cities' cells as described previously. A method such as the one described in conjunction with FIG. 2 may be used to identify city bounds; a method as described in conjunction with FIG. 3 may be used to identify metropolitan bounds; a method as described in conjunction with FIG. 4 may be used to identify regional bounds.

[0114] Illustratively, all cells associated with the cities (and/or metropolises and regions) may iteratively be expanded to a common level first (e.g., the highest layer of cell reached while determining the cities' bounds), while testing for collisions, before expanding to a higher layer.

[0115] Embodiments of the invention for determining bounds of cities, metropolises, regions and countries have now been described with reference to FIGS. 2-5. In another embodiment of the invention, a single method may be employed to determine bounds of multiple types of areas. Illustratively, starting with city coordinates and initial city cells, cells are repeatedly replaced with the encompassing cell of the next higher layer until all areas' bounds are identified.

[0116] As the cells get larger and larger, first city bounds are identified, then metropolitan, regional and country bounds. Each area's bounds may be detected through collisions with other cities/metropolises/regions/countries, through collisions with bodies of water, through collisions with unassigned cells or areas having no useful geographic data, through a fixed level or number of expansions, etc.

[0117] In an embodiment of the invention, a void cell, zone or point may be defined to encompass a location for which no geographic or geospatial data is available or a geographic or topographic feature at which cell expansion/replacement should halt (e.g., an ocean). Thus, testing for an intersection between a cell associated with one area (e.g., city, metropolis, region, country) and cells of other areas may also involve testing for intersection (or adjacency) with a void cell. A void cell may be of any size and may therefore be found at any layer of a hierarchy of geographic or geospatial data cells. The set of cells that comprise, define or delineate an area may be termed the area's cell covering.

[0118] As described previously, a hierarchical spatial index may be constructed to reflect the entire cell division scheme, from layer 0 (e.g., the earth) or layer 1 (e.g., the projection of a cube onto the earth's surface) to as low a level as is desired. In one embodiment of the invention, approximately 30 layers of cells are defined.

[0119] Each node in the spatial index corresponds to one cell of the cell division scheme. The index may be constructed sparsely, meaning that nodes are generated only when and as the corresponding cells are needed.

[0120] All geographic areas of interest (e.g., the cities, metropolises, regions and countries for which bounds are determined) are represented by a finite set of cells, with each cell corresponding to one index node. Each node has a list of geographic areas that overlap or include its corresponding cell.

[0121] Given a point of latitude/longitude, the leaf cell that overlaps the point can be determined quickly. From that cell, its ancestor cells can be easily identified by reference to the index. The union of the leaf cell and its ancestors yields all geographic areas that intersect the point.

[0122] As described in a following section, this procedure can be used to help determine what areas intersect a user's view port.

Determining Overlap between a Target Area and a View Port

[0123] In an embodiment of the invention, a method is provided for efficiently determining whether, and possibly how much, a target geographical area overlaps a map view or view port that is (or will be) served to a user.

[0124] An implementation of this embodiment of the invention may be used to determine whether a user's view port intersects a target geographical area in which, or for which, an advertiser has paid to place advertisements. In particular, an advertiser may specifically request an ad be served with maps or view ports within target cities, metropolises, regions (e.g., counties, states), countries or other areas. By determining which target areas overlap a particular view port, appropriate ads can be identified for serving with the view port.

[0125] In this embodiment, by defining a set of points or zones within the view port, tests for intersection can be performed quickly and efficiently. In particular, testing for an intersection between a number of areas and a point is faster than testing for intersections between a number of areas and another area.

[0126] In one particular implementation, the extent or amount of overlap between a view port and an advertiser's target area(s) may determine whether the advertiser's ad is served and/or its priority (e.g., the order or position in which it is served with or among other ads). More specifically, if an ad's target area overlaps the view port only a relatively small amount (e.g., less than 10% or 25% of the view port), the ad may not be served or may be served with relatively low priority. For example, if the user's view port encompasses the entire United States, an ad targeting one or even a few specific cities in the United States may not be served.

[0127] Conversely, if an ad's target area significantly overlaps the view port (e.g., by more than 50%), then the ad may be served and may also be awarded relatively high priority or prominence. For example, if a user's view port encompasses the metropolitan San Francisco area, an ad targeting the city of San Francisco or the state of California may be served.

[0128] A method of determining bounds or boundaries of geographical areas described in the previous section may be used to help determine whether an advertisement targeting such an area overlaps or intersects a given view port, by providing an easily manipulated definition of a target area.

[0129] However, target areas of advertisements are not limited to the types of areas addressed in the previous section (i.e., city, metropolis, region, country). A target area may be a circle defined by a set of latitude/longitude coordinates plus a radius, a geographic cell as described in the previous section, a series of vectors, or virtually any other area.

[0130] FIG. 6 demonstrates a method of determining overlap between a map view or view port of a map, or some other view of geographical data, and one or more target geographical areas. A target geographical area may be the target of a particular advertisement or advertiser, a focus of research or an investigation, or may be targeted for some other reason (e.g., polling, surveys).

[0131] In operation 602, a set of target areas is identified (e.g., all areas associated with advertisements or other information to be served with map views). The targeted geographical areas may be delineated or defined by a set of cells overlaying the area, by a circle centered on some target (e.g., an address, a city's coordinates), or by some polygon described by vectors, latitude/longitude coordinates or other means (e.g., zip code, area code).

[0132] In one implementation, target geographical areas are loaded into a spatial index when mapping system 110 (or ad server 120) of FIG. 1 is booted, meaning that the nodes of the index identify which (if any) target areas their corresponding geographic cells lie within. The spatial index may be constructed as described in the preceding section, or may be loaded from storage after having been constructed earlier. Thus, for each target area, a set of geographic cells encompassing the area is easily identified by referring to the spatial index.

[0133] In operation 604, a map view is generated or retrieved, possibly using parameters from a user. Illustratively, a map view may be generated in response to a user's submission of some parameters, such as a name of a known area (e.g., a city, a metropolis, a region, a country), an address, a pair of latitude and longitude coordinates, etc. A map view may then be selected based on the parameters.

[0134] The resolution of the view may depend on the level of detail inherent in the user's specified parameters. For example, if the user simply names a city, the map view may encompass all or most of the bounded area of the city (e.g., as determined by the method illustrated in FIG. 2). If she gives a specific address, the map view may focus on a portion of the city that includes the address (e.g., a cell or set of cells that encompass the address). Regardless of the resolution, the area displayed within the map view is readily determined by latitude/longitude coordinates, vectors, other spatial coordinates, etc.

[0135] In operation 606, a set of points is overlaid upon the map view, or invisibly placed within it. In one implementation the points are equally or fairly equally distributed within the map view. Many possible distributions are envisioned, especially if the map view is rectangular, as is the case with most existing display devices.

[0136] In the embodiment of the invention reflected in FIG. 6, points are placed within or upon a map view in such a way that any target geographical area that overlaps the map view a significant or meaningful amount will intersect at least a threshold number (e.g., one) of the points. Because most target areas may be relatively centric and dense (e.g., circular, rectangular), depending on the number and distribution of points, only areas that have minimal overlap with the map view may be able to overlap without intersecting at least one point.

[0137] FIG. 7 demonstrates illustrative distributions of points within a map view. Map view 702 demonstrates the even distribution of 9 test points within one map view. Similarly, map view 712 demonstrates the distribution of 20 test points within another map view.

[0138] In different implementations, different numbers of points may be placed and may be placed in various patterns, depending on the dimensions and size of the map view, the smallest overlap that is deemed significant, and/or other factors.

[0139] In operation 608, tests for intersections are performed between some or all points and some or all target areas. In one implementation, the spatial index is queried for each test point, to determine which (if any) target areas intersect the point. As described above, a leaf cell that overlaps a given point can be quickly identified. The spatial index node that corresponds to that leaf cell will have a list of all target areas that include the leaf cell.

[0140] Operation 608 thus yields a set of target areas that overlap at least one of the test points. These target areas may all be candidates for having associated information (e.g., advertisements, notices, warnings) served with the map view.

[0141] In operation 610, the set of target areas that intersect at least one test point are filtered to eliminate areas that only minimally overlap the view port.

[0142] In particular, in this embodiment of the invention, an advertisement or other information associated with a target area may not be served unless the target area overlaps at least a threshold amount of the map view (e.g., 10%, 25%, 3 of 9 points, 5 of 20 points). The information that is served may be prioritized based on the amount of overlap of different target areas, to determine the order in which the information should be listed, where it should be positioned, the size or other attribute of the information (e.g., font, color, text or image).

Selecting Targeted Messages Based on a Map View Port

[0143] In an embodiment of the invention, a system and method are provided for selecting one or more targeted advertisements or other information for presentation to a user in conjunction with an electronic map view port. Although implementations of this embodiment for selecting targeted advertisements are described below, one skilled in the art will appreciate that other types of messages, announcements, notices, warnings, and so on, may be selected in other implementations.

[0144] In this embodiment of the invention, advertisers describe or select target areas for their advertisements. The areas may be predefined, such as cities, metropolises, regions and countries for which bounds are determined in an embodiment of the invention described in a previous section. Or, a target area may be defined as a circle having a center (e.g., an address, a city, a latitude/longitude coordinate) and a radius (e.g., 10 miles, 30 miles), a polygon (e.g., defined as a set of vectors, a connected set of latitude/longitude coordinates) or in some other manner.

[0145] An advertisement's target area is used to determine whether or when to serve the advertisement to a user. In particular, the advertisement may be served with map view ports that intersect the target area in a significant manner. In different implementations, a “significant” intersection may be defined differently. In one implementation, a view port significantly intersects a target area if they intersect and the intersection comprises at least a threshold percentage of the area of the view port, such as 10%, 25%, 40%, etc. The amount or percentage of overlap may be used as an indicator of the ad's relevance.

[0146] In another implementation, a view port significantly intersects a target area if the target area intersects at least a threshold number of test points within the view port, as described in the preceding section.

[0147] In order for an advertisement to be served with a user's view port, however, it may not be enough for the advertisement's target area to significantly intersect the view port. It may also be necessary for the advertisement to match any query terms, search terms, keywords or other criteria (if any such criteria exist). Such criteria may be specified by a user or selected by the system serving the view port or advertisements for the view port.

[0148] FIG. 8 demonstrates a method of selecting advertisements for serving with a map view port based on whether and how much the advertisements' target areas intersect or overlap the view port, according to one embodiment of the invention.

[0149] The method of FIG. 8 may be preceded by implementation of an embodiment of the invention described in conjunction with any or all of FIGS. 2-5, to determine bounds of various geographic areas. As described below, when one of these geographic areas is specified as an advertisement's target area, knowledge of the area's bounds and the area's cell coverage may facilitate a determination of whether the area intersects a given view port.

[0150] In operation 802 of the method illustrated in FIG. 8, advertisers associate their ads with one or more target areas. Illustratively, for each advertisement, an advertiser may select one or more predefined areas (e.g., cities, metropolises, regions, countries) as target areas, or may describe an area of interest as a circle having a center (e.g., a city, an address) and a radius or in some other manner.

[0151] The advertisers may also provide keywords, search terms or other query filters for determining whether their advertisements are relevant to a user's query (e.g., for “hotels” or “restaurants”). Such query filters are not required, however, as an advertiser may want an advertisement shown to all users receiving a view port of a particular area, not just a subset of those users that enter matching search terms.

[0152] In operation 804, parameters or criteria are received for selecting or generating a view port to be served to a user. In one implementation, the parameters are received from the user, such as when he or she requests a map view of an address or area. The parameters include or imply at least one of a city, metropolis, region (e.g., county, state, province) or country, but may also include a specific address, an airport name or identifier, and/or other information from which a map view port can be selected.

[0153] In operation 806, a view port to be served to the user is retrieved or generated. Illustratively, if the user requests a known or common view port (e.g., a map of a popular city or region), a pre-constructed view port may be retrieved from storage. Or, the view port may be dynamically generated based on the user's parameters, size and/or resolution of the user's display device, etc., usually virtually any type of map data (e.g., rendered, satellite imagery, aerial imagery).

[0154] In operation 808, some or all known target areas (e.g., target areas of all known ads having target areas) are compared to the view port to determine whether and/or how much they overlap.

[0155] In one implementation, all advertisements' target areas are compared to the view port. In another implementation, advertisements whose target areas cannot overlap are not considered. For example, if the user requests a view of California or a metropolis or city within California, target areas wholly contained within other states and within countries other than the United States may be eliminated from consideration without testing for overlap.

[0156] In another implementation, overlaps may be predetermined. For example, for a popular view port and advertisements not limited by search terms (or limited only by popular search terms), overlaps may be determined ahead of time and stored.

[0157] In the illustrated embodiment of the invention, advertisements whose target areas do not significantly overlap the view port are eliminated from consideration for serving with the view port. In this embodiment, a significant intersection requires a target area to cover or comprise at least 25% of the area of the view port. The percentage of overlap may be calculated in different ways in different implementations of this embodiment.

[0158] In one implementation, a method described in the preceding section is employed to identify target areas that overlap at least a threshold percentage (e.g., 25%). In that method, a plurality of test points is distributed within the view port. Then, instead of testing for intersections between two two-dimensional areas (i.e., the view port and a target area), simpler comparisons are made between individual test points (all or a subset of the points) and a target area. The test points may be distributed such that if a target area overlaps a threshold number of the points (e.g., 1, 2, 3) it is likely that the target area significantly intersects the view port; a more exact comparison may or may not be calculated.

[0159] In optional operation 810, the set of advertisements whose target areas significantly intersect the view port is filtered based on the user's query terms (e.g., keywords).

[0160] After operation 810, the view port and any number of advertisements are served to the user. The advertisements that are served have been determined to significantly overlap the view port, and may match the user's query terms, if any.

[0161] The advertisements served with the view port may be prioritized based on how significantly their target areas overlap the view port and/or the degree to which they match the query terms. For example, the more an advertisement's target area overlaps the view port, the higher priority the advertisement may be awarded. An advertisement's priority may affect how or where the advertisement is served, such as its location or ranking on the user's display, or its size, font, color or other attribute.

[0162] The program environment in which a present embodiment of the invention is executed illustratively incorporates a general-purpose computer or a special purpose device such as a hand-held computer. Details of such devices (e.g., processor, memory, data storage, display) may be omitted for the sake of clarity.

[0163] It should also be understood that the techniques of the present invention may be implemented using a variety of technologies. For example, the methods described herein may be implemented in software executing on a computer system, or implemented in hardware utilizing either a combination of microprocessors or other specially designed application specific integrated circuits, programmable logic devices, or various combinations thereof. In particular, the methods described herein may be implemented by a series of computer-executable instructions residing on a suitable computer-readable medium. Suitable computer-readable media may include volatile (e.g., RAM) and/or non-volatile (e.g., ROM, disk, DVD) memory, carrier waves and transmission media (e.g., copper wire, coaxial cable, fiber optic media). Exemplary carrier waves may take the form of electrical, electromagnetic or optical signals conveying digital data streams along a local network, a publicly accessible network such as the Internet or some other communication link.

[0164] The foregoing embodiments of the invention have been presented for purposes of illustration and description only. They are not intended to be exhaustive or to limit the invention to the forms disclosed. Accordingly, the scope of the invention is defined by the appended claims, not the preceding disclosure.