System and method for determining a boundary of a geographic area

• US 9,706,352 B2
• Filed: 01/06/2012
• Issued: 07/11/2017
• Est. Priority Date: 01/06/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Byun, Jungkhun
• Primary Examiner(s): Pham, Tuan A
• Application Number:
  US13/345,604
• Publication Number:
  US 20150172861A1
• Time in Patent Office: 2,013 Days
• Field of Search: None
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

Systems, methods, and machine-readable media for determining a boundary of a geographical area is provided. The system may include a pattern detection module, a location module, and a boundary module. The pattern detection module may be configured to identify a plurality of point of interest (POI) names associated with the geographical area from one or more web documents. The location module may be configured to identify a plurality of location coordinates corresponding to the identified POI names and the boundary module may be configured determine the boundary of the geographical area based on the location coordinates derived from the POI names.

Claims

1. A method for determining a boundary of a geographical area, the method comprising:

identifying, by one or more computing devices, a plurality of point of interest (POI) names associated with the geographical area from one or more web documents, wherein identifying the plurality of POI names comprises retrieving the one or more web documents using a web crawling component and detecting, in the one or more web documents, a plurality of patterns from a list of predetermined patterns, each pattern including a POI name and a geographical area name arranged in a predetermined manner;

locating, by the one or more computing devices, in a POI database, a plurality of POI listings corresponding to the identified POI names;

determining, by the one or more computing devices, location coordinates derived from each of the POI listings;

when a number of instances of detection of the geographic area reaches a threshold, calculating, by the one or more computing devices, the boundary of the geographical area, wherein the calculating step includes;

identifying at one or more outlier location coordinates from the location coordinates derived from the POI listings;

generating an updated list of location coordinates associated with the geographical area based on removing the outlier location coordinates from the location coordinates derived from the POI listings; and

calculating the boundary of the geographical area based on the updated list of location coordinates associated with the geographical area; and

storing, by the one or more computing devices, data indicative of the boundary of the geographical area in a database containing information associated with the geographical area.

2. The method of claim 1, wherein the calculating of the boundary of the geographical area comprises generating a convex hull using the updated list of location coordinates derived from the POI listings.

3. The method of claim 1, further comprising updating a boundary associated with the geographic area stored in a database with the calculated boundary for the geographic area.

4. The method of claim 1, wherein the POI database contains a plurality of POI listings wherein each POI listing includes a POI name and a location coordinate.

5. The method of claim 1, wherein the plurality of POI listings includes at least one business listing.

6. A system for determining a boundary of a geographical area, the system comprising:

one or more processors; and

a machine-readable medium comprising instructions stored therein, which when executed by the one or more processors, cause the one or more processors to perform operations comprising;

identifying a plurality of point of interest (POI) names associated with the geographical area from one or more web documents, wherein identifying the plurality of POI names comprises retrieving the one or more web documents using a web crawling component and detecting, in the one or more web documents, a plurality of patterns from a list of predetermined patterns, each pattern including a POI name and a geographical area name arranged in a predetermined manner;

identifying a plurality of location coordinates corresponding to the identified POI names;

when a number of instances of detection of the geographic area reaches a threshold, determining the boundary of the geographical area, wherein the determining step includes;

identifying at one or more outlier location coordinates from the location coordinates corresponding to the identified POI names;

generating an updated list of location coordinates associated with the geographical area based on removing the outlier location coordinates from the location coordinates corresponding to the identified POI names; and

calculating the boundary of the geographical area based on the updated list of location coordinates associated with the geographical area; and

storing data indicative of the boundary of the geographical area in a database containing information associated with the geographical area.

7. The system of claim 6, wherein the determining of the boundary of the geographical area comprises generating a convex hull using the updated list of location coordinates derived from the POI names.

8. The system of claim 6, wherein the operations further comprise updating a boundary associated with the geographic area stored in a database with the determined boundary for the geographic area.

9. The system of claim 6, wherein the identifying of the plurality of location coordinates corresponding to the identified POI names comprises identifying a plurality of POI listings in a POI database using the identified POI names and determining location coordinates associated with each of the POI listings.

10. A non-transitory machine-readable medium comprising instructions stored therein, which when executed by a machine, cause the machine to perform operations comprising:

identifying a plurality of point of interest (POI) names associated with the geographical area from one or more web documents, wherein identifying the plurality of POI names comprises retrieving the one or more web documents using a web crawling component and detecting, in the one or more web documents, a plurality of patterns from a list of predetermined patterns, each pattern including a POI name and a geographical area name arranged in a predetermined manner;

determining a plurality of location coordinates corresponding to the identified POI names; and

calculating boundary information for the geographical area, wherein the calculating step includes;

identifying at one or more outlier location coordinates from the location coordinates corresponding to the identified POI names;

generating an updated list of location coordinates associated with the geographical area based on removing the outlier location coordinates from the location coordinates corresponding to the identified POI names; and

calculating the boundary of the geographical area based on the updated list of location coordinates associated with the geographical area; and

storing data indicative of the boundary of the geographical area in a database containing information associated with the geographical area.

11. The non-transitory machine-readable medium of claim 10, wherein the identifying step comprises detecting a pattern in each of the one or more web documents, the pattern comprising a POI name and a name of the geographical area.

12. The non-transitory machine-readable medium of claim 10, wherein the operations further include updating boundary information associated with the geographic area stored in a database with the calculated boundary for the geographic area.

13. The non-transitory machine-readable medium of claim 10, wherein the determining step comprises identifying a plurality of POI listings in a POI database using the identified POI names and determining location coordinates associated with each of the POI listings.