Recommending points of interests in a region

• US 9,501,577 B2
• Filed: 03/16/2015
• Issued: 11/22/2016
• Est. Priority Date: 09/25/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zheng, Yu, Sheng, Chang, Xie, Xing
• Primary Examiner(s): WILLOUGHBY, ALICIA M
• Application Number:
  US14/659,125
• Publication Number:
  US 20150186389A1
• Time in Patent Office: 617 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/444 Spatial browsing, e.g. 2D maps, 3D or virtual spaces
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries

Abstract

Techniques for searching and providing geographical regions are described. The process searches and recommends points of interests based on a user-specified region. Points of interests include spatial objects (e.g., buildings, landmarks, rivers, parks) and their distributions in a geographical region. The process searches and recommends points of interests by partitioning a spatial map into grids to identify representative categories located in each of the grids. In response to the user-specified region, a set of geographical candidates containing the representative categories is retrieved. The process determines whether the user-specified region and the set of geographical candidates include similar or common representative categories and similar or common spatial distributions of the representative categories. Then the process provides the top ranked set of geographical candidates that have similar content information.

Claims

1. A method implemented at least partially by one or more processors, the method comprising:

providing a spatial map containing geographical regions partitioned into grids;

identifying a user-specified region with a first plurality of points of interests in each of one or more representative categories in the spatial map;

searching for a set of geographical region candidates with a second plurality of points of interests in each of the one or more representative categories based at least in part on a spatial similarity to comparable points of interest in the one or more representative categories in the user-specified region, the spatial similarity comprises comparable distribution of respective points of interests of the user-specified region and the set of geographical region candidates in the one or more representative categories; and

presenting a predefined number of top geographical region candidates of the set of geographical region candidates based at least in part on a result of the searching.

2. The method of claim 1, further comprising pruning plurality of of geographical region candidates to create the set of geographical region candidates before the searching.

3. The method of claim 2, wherein the pruning comprises:

calculating frequencies of one or more categories within each region of the spatial map;

calculating an inverse region frequency of the one or more categories within each region based at least in part on a total number of the grids within the respective region that include points of interest with the respective category;

identifying the representative categories of each region based at least in part on the calculated frequencies of the one or more categories and the inverse region frequency of the one or more categories;

extracting spatial features from the representative categories based at least in part on the identified representative categories; and

calculating bounds of non-extracted spatial features from the representative categories,

wherein the pruning is based at least in part on the bounds of the non-extracted spatial features.

4. The method of claim 3, wherein the calculating the frequencies of the one or more categories comprises determining a category frequency value for a first category of the one or more categories within a first region of the geographical regions based at least in part on a ratio of a number of points of interest for the first category in the first region to a total number of points of interest in the first region.

5. The method of claim 3, wherein the calculating the bounds comprises determining a ratio of a minimum number of points of interest of a first category of the representative categories in a first region of the geographical regions to a maximum number of points of interest of the first category in the first region.

6. The method of claim 3, wherein the calculating the bounds comprises determining a ratio of a minimum distance between a pair of the representative categories in a first region of the geographical regions to a maximum distance between the pair of the representative categories in the first region.

7. The method of claim 3, wherein the calculating the bounds comprises determining a ratio of a minimum reference distance vector for a pair of the representative categories in a first region of the geographical regions to a maximum reference distance vector for the pair of the representative categories in the first region.

8. The method of claim 1, wherein the providing the spatial map comprises creating a hierarchical structure with a root node denoting one of the geographical regions and imposing the grids on the spatial map to correspond to partitioned cells from a parent'"'"'s cell.

9. The method of claim 8, wherein the identifying representative categories comprises identifying the representative categories for the user-specified region and the grids used by the searching based at least in part on the hierarchical structure.

10. A system comprising:

a memory;

one or more processors coupled to the memory to perform acts comprising;

providing a spatial map containing geographical regions partitioned into grids;

identifying a user-specified region with a first plurality of points of interests in each of one or more representative categories in the spatial map;

extracting one or more geographical region candidates from a set of geographical region candidates;

searching the extracted set of geographical region candidates with a second plurality of points of interests in each of the one or more representative categories based at least in part on a spatial similarity to comparable points of interest in the one or more representative categories in the user-specified region, the spatial similarity comprises comparable distribution of respective points of interests of the user-specified region and the set of geographical region candidates in the one or more representative categories; and

presenting a predefined number of top geographical region candidates based at least in part on a result of the searching.

11. The system of claim 10, wherein the extracting comprises:

calculating frequencies of one or more categories within each region of the spatial map;

calculating an inverse region frequency of the one or more categories within each region based at least in part on a total number of the grids within the respective region that include points of interest with the respective category;

identifying the representative categories of each region based at least in part on the calculated frequencies of the one or more categories and the inverse region frequency of the one or more categories;

extracting spatial features from the representative categories based at least in part on the identified representative categories; and

calculating one or more bounds of non-extracted spatial features from the representative categories,

wherein the extracting the one or more geographical region candidates is based at least in part on the one or more bounds of the non-extracted spatial features.

12. The system of claim 11, wherein the calculating the frequencies of the categories comprises determining a category frequency value for a first category of the one or more categories within a first region of the geographical regions based at least in part on a ratio of a number of points of interest for the first category in the first region to a total number of points of interest in the first region.

13. The system of claim 11, wherein the calculating the one or more bounds comprises determining a ratio of a minimum number of points of interest of a first category of the representative categories in a first region of the geographical regions to a maximum number of points of interest of the first category in the first region.

14. The system of claim 11, wherein the calculating the one or more bounds comprises determining a ratio of a minimum distance between a pair of the representative categories in a first region of the geographical regions to a maximum distance between the pair of the representative categories in the first region.

15. The system of claim 11, wherein the calculating the one or more bounds comprises determining a ratio of a minimum reference distance vector for a pair of the representative categories in a first region of the geographical regions to a maximum reference distance vector for the pair of the representative categories in the first region.

16. The system of claim 11, wherein the providing the spatial map comprises building a quadtree structure with a root node denoting a region and imposing grids on the spatial map to correspond to partitioned cells from a parent'"'"'s cell.

17. The system of claim 16, wherein the identifying the representative categories comprises identifying the representative categories for a query region and each of the grids to be searched based at least in part on the quadtree structure.

18. The system of claim 16, wherein the identifying the representative categories comprises identifying the representative categories for a query region and each of the grids to be searched based at least in part on an inverted tree list.

19. A computing device comprising:

one or more processors;

a computer-readable storage medium in communication with the one or more processors, the computer-readable storage medium having computer-executable instructions that, when executed, cause the one or more processors to perform acts comprising;

providing a spatial map containing geographical regions partitioned into grids;

identifying a user-specified region with a first plurality of points of interests in each of one or more representative categories in the spatial map;

pruning a set of geographical region candidates;

searching from the pruned set of geographical region candidates for geographical region candidates having a second plurality of points of interests in each of the one or more representative categories based at least in part on a spatial similarity to comparable points of interest in the one or more representative categories of the user specified region, the spatial similarity comprises comparable distribution of respective points of interests of the user-specified region and the set of geographical region candidates in the representative categories; and

presenting a predefined number of top geographical region candidates based at least in part on a result of the searching.

20. The computing device of claim 19, wherein the pruning comprises:

calculating frequencies of one or more categories within each region of the spatial map;

calculating an inverse region frequency of the one or more categories within each region based at least in part on a total number of the grids within the respective region that include points of interest with the respective category;

identifying the representative categories of each region based at least in part on the calculated frequencies of the one or more categories and the inverse region frequency of the one or more categories;

extracting spatial features from the representative categories based at least in part on the identified representative categories; and

calculating one or more bounds of non-extracted spatial features from the representative categories,

wherein the pruning is based at least in part on the one or more bounds of the non-extracted spatial features.