Identifying physical locations of entities

• US 8,442,716 B2
• Filed: 10/31/2010
• Issued: 05/14/2013
• Est. Priority Date: 10/31/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Epshtein, Boris, Ofek, Eyal
• Primary Examiner(s): Marc, McDieunel
• Application Number:
  US12/916,554
• Publication Number:
  US 20120109942A1
• Time in Patent Office: 926 Days
• Field of Search: 701/300, 701/410, 701/439, 701/454, 701/33.4, 30/32, 30/60, 340/995.24, 705/1.1, 705/14.73, 455/446
• US Class Current: 701/33.4
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Businesses and other entities may be assigned geographic locations based on various types of data. In one example, entities are associated with segments in a street grid. Additionally, data points (e.g., geotagged blog entries or other online information) are associated with segments in the street grid. For a given segment, data points are compared with entities to identify possible matches between the data points and the entities. Each match is assigned a score, and each match represents a possible physical location for a given entity. The locations of entities on the street are assigned, from among the matches, based on which assignment of entities optimizes the aggregate score for the segment, while satisfying one or more physical constraints.

Claims

1. A method of identifying locations of entities, the method comprising:

using a processor to perform acts comprising;

finding entities that fall within a segment of a map;

finding geo-tagged data points that fall within said segment of said map;

finding a set of matches between said entities and said data points;

for each match in said set of matches, assigning, to said match, a score that represents a level of certainty that a data point in said match corresponds to an entity in said match;

creating an optimal assignment of locations of said entity from among said set of matches, said creating of said optimal assignment comprising;

choosing locations, from among said set of matches, that result in a higher aggregate score than would result from any other choice of locations from among said matches, while satisfying a physical constraint;

based on said optimal assignment, generating location coordinates of said entities in said segment; and

storing said location coordinates in a database.

2. The method of claim 1, wherein finding entities and data points that fall within said segment comprises:

assigning an entity or data point to a segment based on said entity or said data point being closer to said segment than to any other segment.

3. The method of claim 1, wherein finding entities that fall within said segment comprises:

assigning an entity to said segment based on said entity having an address that falls within a numerical range, wherein said segment corresponds to addresses falling in said numerical range.

4. The method of claim 1, wherein said physical constraint comprises a condition that no two entities be at the same location.

5. The method of claim 1, wherein said physical constraint comprises a condition that address numbers increase monotonically in a direction through said segment.

6. The method of claim 1, wherein said acts further comprise:

clustering geo-tagged data points on said segment that satisfy a proximity criterion and that are determined to relate to the same entity.

7. The method of claim 1, wherein said map represents a street grid.

8. The method of claim 1, wherein said segment is a side of a street on one block of a street grid.

9. The method of claim 1, wherein a segment is defined as addresses on a street that are within a numerical range and are even numbers, or as addresses on said street within said numerical range that are odd numbers.

10. The method of claim 1, wherein said acts further comprise:

receiving a search query that has a geographic component;

using said database to generate a set of results in response to said query; and

providing, to a user, said set of results.

11. The method of claim 1, wherein said data points comprise microblog entries, wherein each of said microblog entries comprises text provided by a user, and latitude and longitude coordinates of a location from which said microblog entry was made.

12. A system for identifying locations of entities, the system comprising:

a memory;

a processor; and

a component that is stored in said memory and that executes on said processor, wherein said component assigns a set of entities and a set of geo-tagged data points to a segment of a street grid, said segment being an even or odd side of a street within a numerical range, wherein said component assigns said entities and said geo-tagged data points to said segment either based on addresses or based on geographic proximity of said entities and said geo-tagged data points to said segment, wherein said component creates a set of matches between entities and geo-tagged data point in the same segment and assigns, to each match in said set of matches, a score representing a level of certainty that a geo-tagged data point in said match corresponds to an entity in said match, wherein said component finds an assignment of locations of said entities, from among said matches, that creates a higher aggregate score than any other assignment of locations that satisfies a physical constraint, and wherein said component stores said set of locations in a database.

13. The system of claim 12, wherein said physical constraint comprises a condition that addresses of said entities increase monotonically in a direction through said segment.

14. A computer-readable memory that stores executable instructions for identifying locations of entities, the executable instructions, when executed by a computer, causing the computer to perform acts comprising:

finding entities that fall within a segment of a map;

finding geo-tagged data points that fall within said segment of said map;

finding a set of matches between said entities and said data points;

for each match in said set of matches, assigning, to said match, a score that represents a level of certainty that a data point in said match corresponds to an entity in said match;

creating an optimal assignment of locations of said entity from among said set of matches;

based on said optimal assignment, generating location coordinates of said entities in said segment;

storing said location coordinates in a database; and

clustering geo-tagged data points on said segment that satisfy a proximity criterion and that are determined to relate to the same entity.

15. The computer-readable memory of claim 14, wherein finding entities and data points that fall within said segment comprises:

assigning an entity or data point to a segment based on said entity or said data point being closer to said segment than to any other segment.

16. The computer-readable memory of claim 14, wherein finding entities that fall within said segment comprises:

assigning an entity to said segment based on said entity having an address that falls within a numerical range, wherein said segment corresponds to addresses falling in said numerical range.

17. The computer-readable memory of claim 14, wherein said segment is a side of a street on one block of a street grid.

18. The computer-readable memory of claim 14, wherein a segment is defined as addresses on a street that are within a numerical range and are even numbers, or as addresses on said street within said numerical range that are odd numbers.

19. The computer-readable memory of claim 14, wherein said acts further comprise:

receiving a search query that has a geographic component;

using said database to generate a set of results in response to said query; and

providing, to a user, said set of results.

20. The computer-readable memory of claim 14, wherein said data points comprise microblog entries, wherein each of said microblog entries comprises text provided by a user, and latitude and longitude coordinates of a location from which said microblog entry was made.