Patent ID: 12203765

DETAILED DESCRIPTION

Overview

The technology relates to generating and displaying a map of geographic regions based on the proximity of points of interest (POI) along road segments. For instance, a map may be represented by a graph such that each node represents an intersection, each edge represents a road segment connected to an intersection, and each edge is assigned a score based on a certain criteria. By way of example, the criteria may be based on the road segment's total number of POI (e.g., restaurants), a score assigned to POI on a road segment, the density of the road segment's POI relative to its physical length, the physical distance of the segment's POI relative to an intersection, and a score assigned to neighboring segments. The graph may be iteratively filtered until small clusters of road segments are identified. The clusters may be displayed to users by outlining the associated segments and the footprint of POI that are within a threshold distance of the segment.

By way of illustration,FIG.2shows a map of road segments and POI that may be stored in the memory of a system such as that shown inFIG.1. As shown inFIG.3, the map may be modelled by a graph, where each edge represents a road segment and each node represents the intersection of one or more road segments with another road segment. Each edge may be initially assigned a score that is a based on information specific to the POI on that road segment, e.g., the number of POI located on the road segment and their ranking of those POI relative to others.

The score assigned to a road segment also may be based on the score of an adjacent segment. As shown inFIG.4, a portion of the score of edge AB may be added to adjacent edge BC, and a still smaller portion may be added to the edges that are adjacent to edge BC. In that regard, the POI-based score of a road segment may diffuse to direct and indirect neighbors of the segment.

Indeed, the score assigned to a road segment may be based on many other road segments. For example and as shown inFIG.5, as each edge's initial score is diffused to other segments, an increasingly diminishing portion of that score may be added to indirectly-adjacent edges until there is nothing left to add. As a result, a single edge's score may be updated multiple times if the edge is adjacent to multiple edges with relatively high scores.FIG.6shows the total score of each segment.

The graph of the map may be filtered based on a variety of criteria. For instance, the criteria may be based at least in part on characteristics that are specific to a single road segment, such as discarding edges with scores below a threshold. The discarding of edges may iteratively continue with increasingly large thresholds, which may eventually cause the graph to model clusters of connected road segments that are disconnected from the other represented in the graph. By way of example,FIGS.7and8illustrate clusters that formed as a result of iteratively raising the threshold.

The graph may also be filtered based on criteria that depend on the characteristic of more than one segment. For instance, the cluster may be iteratively filtered until the size of the cluster is less than an area-based threshold. By way of example and as shown inFIG.8, if a cluster is required to be ten segments or smaller, then cluster851would satisfy the threshold and be excluded from additional filtering like that described above. However, because cluster850has more than ten segments, it would continue to be filtered until it reaches the size shown inFIG.9.

The filtered graph represents a clustered map.FIG.10provides an example how a clustered map containing one or more clusters may be shown to a user.

Each cluster of segments may be further filtered based on the physical locations of the POI relative to road segments, intersections and each other.FIG.11shows a graph where the location of the edges, nodes and POI markers in the graph are in scale relative to the geographic locations of the associated road segment, road intersections and POI.

One of the criteria for further filtering may prune segments based on the geographic location of POI relative to intersections. As shown inFIG.12, if there are no POI within a threshold distance of an intersection, then all of the edges that are connected to the intersection's associated node may be removed from the graph.

Another criteria for pruning may be based on the density of a road segment's POI relative to the physical length of the segment. For instance and as shown inFIG.13, a virtual length value may be calculated for each edge based on the physical length of the edge's associated segment and the number of POI located on the segment. The virtual distance between pairs of intersections may be used to prune additional road segments from the cluster. For example, the system may determine the shortest path from each node to every other node based on the edge's virtual lengths, and any edge that does not lie along at least one of those paths may be removed from the graph. In that regard,FIG.14illustrates the shortest path between nodes A and E andFIG.15illustrates the shortest path between a node C and every other node.FIG.16illustrates how the graph would appear when any edge that is not on the shortest path between at least one pair of nodes is removed.

Clusters of road segments may be used to identify and display regions that may be of interest to users.FIG.17illustrates a map where road segments750-51were identified as a result of the aforementioned filtering and pruning. As shown inFIG.18, a polygon may be generated for each of those segments, wherein each edge of each polygon is a fixed distance away from an edge of the segment's footprint.

A polygon may also be generated for each building having a characteristic that is associated with one of the segment. For example and as shown inFIG.19, a polygon may be generated for any building having an access route on the segment (e.g., a door or driveway) and contains a POI meeting certain criteria (e.g., the category used to select the POIs described in connection withFIG.2). The edge of the polygons may be a fixed distance away from the edges of the footprint of the relevant building.

As shown inFIGS.20and21, all of the building-specific polygons that intersect a segment-specific polygon may be selected and combined with the segment-specific polygons to form one large polygon. As shown inFIG.21, holes inside the polygon and narrow spaces on the edge of the polygon may be filled in and small protrusions on the outer edge may be removed.

As shown inFIG.22, the polygon may be displayed to a user on a map, thus highlighting a region containing a relatively dense population of POI that may be of interest to the user. A name for the region may be determined and displayed by selecting the name of the town or neighborhood in which the region appears, a category that was used to select the POIs, a category of business that is common in that region, or by selecting the name of the longest road.

Example Systems

FIG.1illustrates one possible system100in which technology disclosed herein may be implemented. In this example, system100may include computing devices110and160. Computing device110may contain one or more processors112, memory114and other components typically present in general purpose computing devices. AlthoughFIG.1functionally represents each of the processor112and memory114as a single block within device110, which is also represented as a single block, the system may include and the methods described herein may involve multiple processors, memories and devices that may or may not be stored within the same physical housing. For instance, various methods described below as involving a single component (e.g., processor112) may involve a plurality of components (e.g., multiple processors in a load-balanced server farm). Similarly, various methods described below as involving different components (e.g., device110and device120) may involve a single component (e.g., rather than device120performing a determination described below, device120may send the relevant data to device110for processing and receive the results of the determination for further processing or display).

Memory114of computing device110may store information accessible by processor112, including instructions116that may be executed by the processor. Memory114may also include data118that may be retrieved, manipulated or stored by processor112. Memory114may be any type of storage capable of storing information accessible by the relevant processor, such as media capable of storing non-transitory data. By way of example, memory114may be a hard-disk drive, a solid state drive, a memory card, RAM, DVD, write-capable memory or read-only memory. In addition, the memory may include a distributed storage system where data, such as data118, is stored on a plurality of different storage devices which may be physically located at the same or different geographic locations.

The instructions116may be any set of instructions to be executed by processor112or other computing device. In that regard, the terms “instructions,” “application,” “steps” and “programs” may be used interchangeably herein. The instructions may be stored in object code format for immediate processing by a processor, or in another computing device language including scripts or collections of independent source code modules, that are interpreted on demand or compiled in advance. Functions, methods and routines of the instructions are explained in more detail below. Processor112may be any conventional processor, such as a commercially available CPU. Alternatively, the processor may be a dedicated component such as an ASIC or other hardware-based processor.

Data118may be retrieved, stored or modified by computing device110in accordance with the instructions116. For instance, although the subject matter described herein is not limited by any particular data structure, the data may be stored in computer registers, in a relational database as a table having many different fields and records, or XML documents. The data may also be formatted in any computing device-readable format such as, but not limited to, binary values, ASCII or Unicode. Moreover, the data may comprise any information sufficient to identify the relevant information, such as numbers, descriptive text, proprietary codes, pointers, references to data stored in other memories such as at other network locations, or information that is used by a function to calculate the relevant data.

The computing device110may be at one node of a network160and capable of directly and indirectly communicating with other nodes of network160. Although only a few computing devices are depicted inFIG.1, a typical system may include a large number of connected computing devices, with each different computing device being at a different node of the network160. The network160and intervening nodes described herein may be interconnected using various protocols and systems, such that the network may be part of the Internet, World Wide Web, specific intranets, wide area networks, or local networks. The network may utilize standard communications protocols, such as Ethernet, Wi-Fi and HTTP, protocols that are proprietary to one or more companies, and various combinations of the foregoing. As an example, computing device110may be a web server that is capable of communicating with computing device120via the network160. Computing device120may be a client computing device, and server110may display (or provide for display) information by using network160to transmit and present information to a user125of device120via display122. Although certain advantages are obtained when information is transmitted or received as noted above, other aspects of the subject matter described herein are not limited to any particular manner of transmission of information.

Computing device120may be configured similarly to the server110, with a processor, memory and instructions as described above. Computing device120may be a personal computing device intended for use by a user and have all of the components normally used in connection with a personal computing device such as a central processing unit (CPU), memory storing data and instructions, a display such as display122(e.g., a monitor having a screen, a touch-screen, a projector, a television, or other device that is operable to display information), user input device162(e.g., a mouse, keyboard, touchscreen, microphone, etc.), and camera163.

Computing device120may also be a mobile computing device capable of wirelessly exchanging data with a server over a network such as the Internet. By way of example only, device120may be a mobile phone or a device such as a wireless-enabled PDA, a tablet PC, a wearable computing device or a netbook that is capable of obtaining information via the Internet. The device may be configured to operate with an operating system such as Google's Android operating system, Microsoft Windows or Apple iOS. In that regard, some of the instructions executed during the operations described herein may be provided by the operating system whereas other instructions may be provided by an application installed on the device. Computing devices in accordance with the systems and methods described herein may include other devices capable of processing instructions and transmitting data to and from humans and/or other computers including network computers lacking local storage capability and set top boxes for televisions.

Computing device120may include a component130to determine the geographic location and orientation of the device. For example, the component may contain circuits such as a GPS receiver131to determine the device's latitude, longitude and altitude position. The component may include software for determining the position of the device based on other signals received at the client device120, such as signals received at a cell phone's antenna from one or more cell phone towers if the client device is a cell phone. It may also include a magnetic compass132, accelerometer133and gyroscope134to determine the direction in which the device is oriented.

The server may store map-related information, such as the names and locations of roads. The location of a road may be stored as one or more road segments, where each segment represents a road, or a portion of road, that extends between two geographic locations. For example, if a road named “Main Street” intersected roads named “First Street”, “Second Street” and “Third Street”, respectively, the portion of Main Street extending between First Street and Second Street may be stored as one segment and the portion of Main Street extending between Second Street and Third Street may be stored as another segment. An individual road segment may be stored in memory as a series of smaller road segments. For instance, if the segment of Main Street extending between the intersection with First Street and Second Street is curvy, that segment may be stored as a series of linear road segments, where each linear road segment is defined by a pair of latitude/longitude positions located on the road. The segment between First Street and Second Street may also be stored as a series of parabolic road segments, where each parabolic road segment is defined by three latitude/longitude positions located on the road. Road segments may optionally represent other geographically-oriented pathways, such as a pedestrian-only trail.

The map-related information may include points of interest (POI), such as a restaurant, business, building, park, lake or any other item of potential interest to users that is associated with a geographical location. In addition to the POI's name and location, the system may associate a POI with one or categories (e.g., “Restaurant”).

Locations may be stored in memory using one or more reference systems, e.g., latitude/longitude positions, street addresses, street intersections, an x-y coordinate with respect to the edges of a map (such as a pixel position when a user clicks on a map), building names, and other information in other reference systems that is capable of identifying a geographic location (e.g., lot and block numbers on survey maps). A geographic location may also be stored as a range of the foregoing (e.g., the location of a city may be defined by the geographic position of its borders) and the system may translate locations from one reference system to another. For example, server110may access a geocoder to convert a location stored as a street address into a latitude/longitude coordinate (e.g., from “1500 Amphitheatre Parkway, Mountain View, CA” to “37.423021°, −122.083939° ”).

The system may also store information from which the footprint of a geographically-located object may be determined. For example, the server may store a building's footprint as a polygon whose vertices correspond with specific latitude/longitude positions. Footprints may also be determined based on one or more assumptions. By way of example, if the system only has access to the latitude/longitude of a road segment's endpoints, the system may determine that the footprint of the road segment is a rectangle that extends between the two endpoints and is as wide as a typical two-lane road.

The system may also indicate whether a building has an access route to a road segment. For example, data118may indicate that a building has a public entrance that is facing and within a certain distance of a particular road segment (in which case an access road to the road segment might be assumed) or that there is a sidewalk between a particular road segment and a public entrance.

Example Methods

A method of determining, and displaying a map of, a commercial, geographic region of interest to users will now be described. It should be understood that the following operations do not have to be performed in the precise order described below. Rather, various steps can be handled in different order or simultaneously.

The geographic region may be within a larger geographic area identified by the system. For instance, server110may receive a request for information about a specific town from user125via client device120. Server110may also identify the geographic area by iteratively selecting and processing towns stored in data118.

The system may retrieve map information associated with the geographic area to be processed.FIG.2provides a map as an example of such an area. In that regard, map200is composed of interconnected road segments such as segments210-212.

The map information may include the location and categories of POI within the area. Geographic areas containing a relatively high concentration of restaurants that are within walking distance from other each are often popular with users. Therefore, the system may identify the region of interest based on POI that are associated with the restaurant category. The locations of restaurants are shown in map200as teardrop shapes. Map200thus indicates that there are four restaurants located on segment210, one restaurant located on segment211and one restaurant located on segment212. Another category of POI may include consumer-oriented shops.

The system may generate a graph based on the map information wherein each edge represents a road segment and each node represents the intersection of one or more road segments with another road segment. In that regard, edges310,311and312inFIG.3represent road segments210,211and212, respectively, and node321represents the intersection of road segment210and road segment211.

Each edge of the graph may be associated with a score value that is based on the number of POI located on the associated road segment. For example, the edges of310,311and312may be initially assigned a score of 4, 1 and 1 based on the number of restaurants located on road segments210,211and212, respectively. (For ease of reference, the remaining figures mostly refer to the nodes and the edges by letter instead of reference numbers.) A POI may be considered to be located on a segment only when it has an access route to the segment. Additionally or alternatively, a POI may be considered to be located on a segment when it is within a threshold distance of the segment or has a street address that is within the range of address numbers associated with the segment.

The total score may also depend on the score assigned to individual POI. For instance, restaurants appearing higher in a search for all restaurants in the area may be assigned a higher score than other restaurants, in which case road segments with equal numbers of restaurants may initially have unequal scores.

The score assigned to a road segment may also be based on the score of an adjacent segment. As noted above, score331of edge310(hereafter, edge “AB”) may be initially assigned a value of 4 because there are 4 POI located on road segment211. Because edge AB directly intersects with edge BC at node B, a portion of the initial score of edge AB may be added to the score of edge BC. For example, a value that is one less than the score331of edge AB may be added score332of edge BC, i.e., the value of score332may be increased by 3. Edge CD directly intersects edge BC at node C, so score333of edge CD may be increased as well, but by an amount that is less than the increase to edge BC. By way of example, since score331of edge BC was increased by 3, score333of edge CD may be increased by 2. A portion of that increase is added, in turn, to adjacent edge DE, e.g., score334of edge ED may be increased by 1. The amount of the increases attributable to the original source edge may continue to decline until there is nothing left to increase. For example, the score of edge EF is not increased because subtracting 1 from the increase to edge ED (+1) equates to an increase of 0.

Any edge that is adjacent to an edge having a score that was updated may have its score updated as well. As a result, the changes from a single edge may diffuse throughout the graph. As shown inFIG.4, the scores of edges CG, GH, GI, CJ are also increased because of the score assigned to edge AB.

The score associated with a road segment may thus be based on not only the number of the POI located on the segment but the number of the POI located on many other segments. For example and as shown inFIGS.5and6, score532of edge BC is based on the number of POI located on its associated segment (1) and the increase (+3) due to score331of adjacent edge AB, resulting in a total score of 4. Edge GI has no POI on its associated road segment (segment240ofFIG.2). Even so, score540of edge GI is relatively high because of increases of +1, +2 and +1 it received from initial scores331,541and542assigned to edges AB, IK and KL, respectively.

In the foregoing example, the increase to a road segment due to a different road segment is directly and inversely proportional to the lowest number of road intersections between the two segments. However, the scores of adjacent edges may be adjusted in other ways as well. By way of example, the extent of the increase may decrease exponentially with each intersection, may be based on the lowest number of intersections on two different paths, and may be based on the physical distance between the segments.

Rather than selecting potentially-interesting segments based solely on their associated edges' initial and updated scores, the graph may also be filtered based on a variety of criteria.

That criteria may include characteristics that are specific to a single edge/segment. By way of example, the score of each edge may be compared to a predetermined threshold and discarded from the graph if it has a score below that threshold.FIG.7shows the result of removing any edges, such as edges DE and EF, that cannot satisfy the criteria “score≥2”.

Such filtering of the graph may iteratively continue with increasingly large thresholds, which may cause the graph to eventually represent clusters of connected road segments that are disconnected from other clusters of connected road segments. By way of example and as shown inFIG.8, two clusters of edges850and851may remain in the graph after edges that cannot satisfy criteria “score≥3” are discarded.

The graph may also be filtered based on criteria that depends on more than one segment. For instance, the aforementioned iterative filtering may continue until a cluster of edges reaches a particular size relative to an area-based threshold. By way of example and as shown inFIG.8, if clusters are required to be ten segments or smaller, cluster851would satisfy the threshold because it only has three segments (PQ, QN, QR). As a result, cluster851would be excluded from additional filtering. Cluster850, on the other hand, has more than ten segments so it would continue to be filtered, e.g., the segment-based threshold for cluster850may be increased to “score≥4”. As shown inFIG.9, cluster850thereupon satisfies the area-based criteria. The area-based threshold may also define a range. For example, if an increase in the threshold score causes a cluster to get too small, the entire cluster may be removed from the graph altogether.

In the foregoing example, the size of a road segment cluster is based on the total number of its associate edges. However, the size of a cluster may be determined in other ways as well. By way of example, the size may be based on the combined physical length of all segments, the number of segments in the shortest or longest non-overlapping path of segments, the physical length of the shortest or longest non-overlapping path of segments, the total hectares (acres) within a polygon defined by the geographic locations of the outermost intersections in the cluster, or combinations of the foregoing.

The filtered graph represents a clustered map that may be displayed to a user.FIG.10provides an example of how a clustered map containing one or more clusters may be shown to a user. Browser1010displays a map1020similar to the map described in connection withFIG.2, but the map also includes a visual characteristic that identifies the clusters of segments1050and1051associated with graph clusters850and851, respectively.

Each cluster of segments may be further filtered by pruning the graph based on the geographic locations of the POI relative to road segments, intersections and each other. By way of illustration,FIG.11shows a graph1110where the length of the edges, and the location of the nodes and associated POI, are roughly in scale relative to the geographic locations associated road segments, intersections and POI. For example, edge AB represents a first road segment that is 100 m long. Edge AF represents a second road segment that intersects with the first road segment, and the distance from that intersection to the next intersection is 144 m. Each teardrop shape represents a POI, e.g., the positions of POI indicators1180-82on graph1110relative to nodes C and E are to scale with respect to the geographic position of three POI on a road segment extending between the intersections associated with those nodes. By way of further example, the geographic distance from POI1150to the intersection represented by node H is 32 m.

One criteria for pruning may be based on the geographic location of POI relative to intersections. For instance, if there are no POI within a threshold distance of an intersection, then all of the edges that are connected to the intersection's associated node may be removed from the graph. By way of example, reference circle1280ofFIG.12illustrates a threshold distance of 25 m (radius). Reference circle1280is centered around crosshair1290, which corresponds with the location of POI1180. As shown in the Figure, node C is within the 25 m threshold distance of cross hair1290, i.e., the location of POI1180. Therefore, there is at least one POI within a threshold distance of node C so node C survive pruning based on this particular criteria. The same is true with respect to reference circle1281(representing the area that is 25 m from the location of POI1182) and node E. Since both nodes C and E survive pruning, edge CE does as well. Alternatively, edges may be pruned by determining a score based on the number of their POI that are within a threshold distance of an intersection and discarding edges with scores below a threshold.

On the other hand, there are no POI within the threshold distance of node H. As shown by reference circle1250, the closest POI is POI1150and it is more than 25 m away from the intersection represented by node H. Therefore, node H and all of the edges connected to the node (e.g., edges BH and CH) are discarded from graph1110.

The threshold distance may be selected based on the likelihood that pedestrians are willing to walk a particular distance when exploring different POI. In that regard and in at least some circumstances, the threshold distance is set to 50 m. The predetermined threshold may be determined based on data received by the system. For example, if pedestrian traffic data in a particular city indicates that pedestrians tend to walk longer distances per day than average, then the predetermined threshold distance associated with that city may be automatically set to a value that is proportionally greater than the average threshold set for other cities.

Another criteria for pruning may be based on the density of POI along a road segment. For instance and as shown inFIG.13, a score associated with a segment may represent a virtual length value that is calculated for each edge based on the physical length of the edge's associated segment and the number of POI located on the segment. The value may be calculated in accordance with the function
Vs=max(L−D*N,0)
where
Vs=virtual length of segmentS,
max(x,0)=afunction returningxor 0,whichever is larger,
L=physical length of segmentS,
D=acoefficient equal to(benchmark length)/(preferred minimum number ofPOIwithin the benchmark length), and
N=number ofPOI'slocatedonsegmentS.

The values shown inFIG.13are based on a preferred minimum of 4 POI for each 100 m of road, i.e., D=100/4=25. By way of example, since there are three POI located on edge AB and the physical length associated with the edge is 100 m, the virtual length1310of AB=max(100-25*3, 0)=25. There are no POI located on edge FG, so its virtual length1320equals its physical length of 100 m. Edge CE is 70 m long and there are 3 POI located on it, which means edge CE has an average density of 4.2 POI every 100 m. This exceeds the preferred minimum of 4 POI for each 100 m of road and, as a consequence, the virtual distance1330of edge CE is zero.

The virtual distance between pairs of intersections may be used to prune road segments from the cluster. By way of example, the system may determine the shortest path from each node to every other node based on the edge's virtual lengths, and any edge that does not lie along at least one of those paths may be removed from the graph. As shown inFIG.14, the virtual length1310of edge AB and the virtual length1425of edge BC is 50. Therefore, the virtual distance of node C from A via edges AB and BC is 75. The virtual length1330of edge CE is zero, so the total virtual distance1340of node C from A via edges AB, BC and CE is 75. The virtual length of any other path from node A to node E would be longer than 75. As a result, edges AB, BC and CE collectively represent the shortest path between nodes A and E and, as a result, those edges will not be discarded based on POI density.

FIG.15illustrates the shortest possible paths from node C to each of the other nodes in graph1110. For example, the shortest path from node C to node F is along edges CD and CF. Edges AB, BC, CD, DF, CE and EG are also on the shortest path from node C to at least one other node, so they will not be pruned based on POI density. Standard all-pairs shortest path algorithms may be used to identify the shortest paths between all node pairs. Standard all-pairs shortest path algorithms may be used to identify the shortest paths between all node pairs.

FIG.16shows all of the edges that are on the shortest path from at least one node to any other node of graph1110. Edges AF, CG, DG and FG were not on any of the shortest paths and were thus pruned from graph1110. As a result, surviving edges AB, BC, CE, CD, EG and DF may represent road segments that collectively identify a geographic region of particular interest to pedestrians based on POI.

By reducing the size of clusters, the system may decrease the likelihood that a cluster will represent a ball of non-commercial (e.g., residential) road segments around a core of commercial road segments, or a single cluster will include two separate commercial regions that are connected through a non-commercial region. On the other hand, by initially diffusing scores as described above, the system may decrease the likelihood that clusters of segments are separated by a small gap of road segments. Moreover, when the virtual distance is calculated as described above, the surviving road segments tend to form paths that follow highly-commercial streets.

In the foregoing example, the system generated the graph shown inFIG.16by filtering the graph in multiple stages, including filtering based on the number of POI on the edge's road segment, the number of POI on road segments neighboring the edge's road segment, the total number of connected segments, the proximity of POI to road intersections, and the density of POI, in roughly that order. However, other embodiments of system100may forego one or more of those stages, apply the stages in a different order, or use scores and criteria discussed in connection with one stage with another stage. By way of example, the initial score discussed in connection withFIG.3may be based on the segment's POI density, the virtual distance discussed inFIG.13may be based on a score that reflects the number of a segment's POI within a threshold distance of an intersection as discussed in connection withFIG.12, and the system may forego the pruning discussed in connection withFIG.12.

FIG.10provided one example of how a region of interest may be displayed to users.FIGS.17-22provide another example of displaying a region of interest.

FIG.17shows a map of road segments, where road segments1750and1751were determined to be of potential interest to users. The map also shows the footprints of nearby buildings, such as buildings1701-03.

The system may generate polygons that are associated with specific road segments. For example and as shown inFIG.18, polygon1861may be generated based on footprint1851of road segment1751. As shown in the close-up view1810of the right side of footprint1851, each edge of polygon1861may be a parallel to and a fixed distance away from the edge of the footprint. Polygon1860may be may be similarly generated based on footprint1850of road segment1750.

A polygon may also be generated for each building having a characteristic associated with one or more segments. By way of example and as shown inFIG.19, that characteristic may require the building to have an access route to the relevant segment. In that regard, the system may generate a polygon1901for building1701because it has a sidewalk1921from the building to road segment1851. Although building1702is closer to road segment1851than building1701, the system may not generate a polygon for building1702because its access route1922does not extend to segments1850or1851. A polygon would be generated for building1704because, even though it has an access route1934to a road segment other than segments1850-51, it also has an access route1924to segment1850. An additional or alternative characteristic may require the building's footprint to be within a threshold distance of the relevant segments. Another characteristic may require the building to have at least one POI that matches the criteria used to select POI for identifying the segments that may be of interest to users. For instance, if segments1850-51were identified based on how many restaurants are located on the segment or nearby segments, no polygon would be generated for building1705if it does not contain a restaurant.

The edges of the polygons generated for the buildings may be parallel to and a fixed distance1945from the edge of building's footprint.

All of the generated polygons may be combined into a single polygon. As shown inFIG.20, all of the polygons1901-05that were generated based on the footprint of buildings and all of the polygons1860-61that were generated based on the footprint of road segments may be combined together. In that regard, the unshaded portion2130of polygon2100shown inFIG.21represents the union of polygons1901-05and1860-61. Holes inside polygon2100like hole2150may be filled in, narrow gaps2140along the outer edges such as gaps2140-541may be filled in, and narrow protrusions like protrusion2160may be removed.

The polygon may be displayed to a user on a map in order to highlight the region of potential interest to the user. By way of example, browser2200may display the polygon2100on map2210at a position corresponding with the relevant road and building footprints. The visual characteristics of the objects shown in the map may change based on their relevance to the polygon. By way of example, the colors of one or more of the following items may be the same or different: background2290of polygon2100, building footprints1701,1702,1704,1706and1707that are within the polygon and are associated with buildings containing relevant POI, a building footprint1705that is within the polygon and not associated with a building containing relevant POI, road footprints2240that are within the polygon, building footprints1702and1703that are outside of the polygon, road footprints that are outside of the polygon, and the background of the map outside of the polygon.

A name for the region may also be determined and displayed. For instance, name2250may be determined by selecting the name of the town or neighborhood in which the region appears, the name of the neighborhood or road with the largest number of POI, the category that was used select the POIs, a category of business common in the region, or the name of the road with the greatest footprint area with the polygon. When the region is based on a neighborhood name and there are a number of names coinciding with neighborhoods that are within, contain or are otherwise proximate to the region, the names may be ranked and a name may be selected based on how closely the associated neighborhood's geographic boundaries coincide with the boundaries of the region and the online popularity of the name.

Although many of the foregoing examples focussed on using restaurants to identify commercial corridors, other categories of POI may be used to identify other types of areas of interest. By way of example only, such as identifying areas with many museums, tourist attractions, expensive boutiques and child-friendly restaurants. Moreover, POI that are associated with a cultural identity may be used to identify areas that are also associated with that cultural identity (e.g., Little Italy of New York City).

FIG.23is a flowchart of a computer-implemented method of processing map information to identify regions of interest. At block2310, a map is received that that includes a plurality of nodes connected by a plurality of edges, in which each edge has an assigned score based on predetermined criteria. At block2320, the map is filtered by comparing the score of each edge to a predetermined filtering threshold, and discarding edges having a score below the threshold. At block2330, the filtered map is processed by identifying one or more clusters containing contiguous edges and generating a clustered map containing the one or more clusters. At block2340, the size of each of the one or more clusters is compared with an area threshold and identifying clusters smaller than the area threshold as regions of interest. At block2350, regions of interested are removed from the clustered map. At block2360, it is determined if all of the clusters identified at block2340are smaller than the threshold. If so, at block2380, a processed map comprising each of the identified regions of interest is outputted. If not, then at block2370the predetermined filtering threshold is increased and the method returns to block2320. The method thus continues to iteratively perform blocks2320-2350, wherein the clustered map with the regions removed is filtered at block2330with an increased predetermined filtering threshold, wherein the iteration is performed until all clusters identified at block2340are smaller than the area threshold.

FIG.24is a flowchart of a computer-implemented method of displaying a map. At block2410, a road segment is identified based on the number of POI located on the segment. At block2420, a geographically-located object having a characteristic associated with the road segment is identified. At block2430, a polygon is generated wherein the locations of the polygon's edges are based on the footprint of the road segment and the footprint of the geographically-located object. At block2440, a map that displays the road segments and the polygon relative to the geographic locations of the road segments is provided.

As these and other variations and combinations of the features discussed above can be utilized without departing from the invention as defined by the claims, the foregoing description of the embodiments should be taken by way of illustration rather than by way of limitation of the invention as defined by the claims. The provision of examples of the invention (as well as clauses phrased as “such as,” “e.g.”, “including” and the like) should not be interpreted as limiting the invention to the specific examples; rather, the examples are intended to illustrate only some of many possible aspects. Similarly, references to “based on” and the like means “based at least in part on”.