Named Area Generation

• US 20130328882A1
• Filed: 06/08/2012
• Published: 12/12/2013
• Est. Priority Date: 06/08/2012
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Pirwani, Imran A., Petrov, Alexander
• Application Number:
  US13/492,607
• Publication Number:
  US 20130328882A1
• Time in Patent Office: Days
• US Class Current: 345/441
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 18/23213 with fixed number of clusters, e.g. K-means clustering

Abstract

Systems, methods, and computer program products for named area generation are disclosed. In some implementations, documents are processed to uncover pairs of text strings and geographical regions (e.g., a collection of simple convex polygons). For any string/polygon pair, each polygon defines a geographical region whose name is the associated string.

Claims

1. A method comprising:

generating collections of locations grouped by a common string; and

for each collection, generating one or more polygons representing the common string geographically,

wherein the method is performed by one or more hardware processors.

2. The method of claim 1 further comprising:

organizing the one or more polygons in a database for spatial indexing;

3. The method of claim 2, further comprising:

using the database for a mapping service to define one or more geographic regions.

4. The method of claim 1, where generating collections of locations grouped by a common string further comprises:

generating collections of locations grouped by a common string according to the equation

C={(s_i,{p_ij}_j=1ⁿⁱ)}_i=1^L,

where p_ij is a location, s_i is a string, L is a total number of strings, n_i is the number of points that are associated with the i^th string, and the strings s_i are distinct in the collection C, such that for every i≠

j, s_i≠

s_j.

5. The method of claim 1, where generating polygons further comprises:

performing a first process to each collection to generate one or more clusters of locations.

6. The method of claim 5, where the first process is k-means clustering, where k is a small positive integer.

7. The method of claim 6, further comprising:

performing a second process on at least one cluster to modify the shape of the cluster.

8. The method of claim 7, where the second process uses a L-minimum spanning tree (L-MST), where L is a positive integer.

9. The method of claim 1, where the polygons are generating based on a set of parameters including one or more of:

i) the maximum number of polygons, the minimum separation between a pair of centers of polygons, ii) the maximum allowable diameter of a polygon, iii) the fraction of the total points that the polygon will cover, and iv) the fraction of points assigned to the polygon that the polygon will cover.

10. A system comprising:

one or more processors;

memory coupled to the one or more processors and configured to store instructions, which, when executed by the one or more processors, causes the one or more processors to perform operations comprising;

generating collections of locations grouped by a common string; and

for each collection, generating one or more polygons representing the common string geographically.

11. The system of claim 10 where the memory stores instructions, which, when executed by the one or more processors, causes the one or more processors to perform operations comprising:

organizing the one or more polygons in a database for spatial indexing;

12. The system of claim 11, where the memory stores instructions, which when executed by the one or more processors, causes the one or more processors to perform operations comprising:

using the database for a mapping service to define one or more geographic regions.

13. The system of claim 10, where generating collections of locations grouped by a common string further comprises:

generating collections of locations grouped by a common string according to the equation

C={(s_i,{p_ij}_j=1ⁿⁱ)}_i=1^L,

where p_ij is a location, s_i is a string, L is a total number of strings, n_i is the number of points that are associated with the i^th string, and the strings s_i are distinct in the collection C, such that for every i≠

j, s_i≠

s_j.

14. The system of claim 10, where generating polygons further comprises:

performing a first process to each collection to generate one or more clusters of locations.

15. The system of claim 14, where the first process is k-means clustering, where k is a small positive integer.

16. The system of claim 15, where the memory stores instructions, which when executed by the one or more processors, causes the one or more processors to perform operations comprising:

performing a second process on at least one cluster to modify the shape of the cluster.

17. The system of claim 16, where the second process uses a L-minimum spanning tree (L-MST), where L is a positive integer.

18. The system of claim 10, where the polygons are generating based on a set of parameters including one or more of:

i) the maximum number of polygons, the minimum separation between a pair of centers of polygons, ii) the maximum allowable diameter of a polygon, iii) the fraction of the total points that the polygon will cover, and iv) the fraction of points assigned to the polygon that the polygon will cover.

19. A non-transitory computer-readable storage medium storing instructions, which, when executed by one or more processors, causes the one or more processors to perform operations comprising:

generating collections of locations grouped by a common string; and

for each collection, generating one or more polygons representing the common string geographically,

wherein the method is performed by one or more hardware processors.

20. The computer-readable medium of claim 19 further including instructions, which, when executed by the one or more processors, causes the one or more processors to perform the operation of:

organizing the one or more polygons in a database for spatial indexing;