RECOMMENDING POINTS OF INTERESTS IN A REGION

• US 20110093458A1
• Filed: 09/25/2009
• Published: 04/21/2011
• Est. Priority Date: 09/25/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sheng, Chang, Xie, Xing, Zheng, Yu
• Granted Patent: US 9,009,177 B2
• Time in Patent Office: Days
• US Class Current: 707/724
• 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 a processor, the method comprising:

accessing a spatial map;

partitioning the spatial map into grids to identify representative categories located in each of the grids;

selecting a query region with a place of interest in a representative category in the spatial map;

in response to the query region, receiving a set of geographical candidates in the spatial map that includes the representative categories;

determining whether the query region and the set of candidates in the spatial map include content information that is similar having common geometric properties, common representative categories, and common spatial distributions of representative categories; and

providing top ranking geographical regions from the set of geographical candidates in the spatial map that have content information that is similar to the query region.

2. The method of claim 1, wherein the spatial map comprises at least one of a spatial dataset of locations based on the representative categories identified for published information of businesses, museums, restaurants, sight attractions;

a spatial dataset identifying objects as rivers, lakes, parks, and buildings;

or a spatial dataset of a geographical region.

3. The method of claim 1, wherein the partitioning comprises using a hierarchical 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.

4. The method of claim 1, further comprising building an inverted-index over grids to facilitate a search for the set of geographical candidates.

5. The method of claim 1, wherein the partitioning the spatial map into grids identifies the representative categories for the query region and each of the grids to be searched based on a quadtree structure and an inverted tree list.

6. The method of claim 1, further comprising calculating the spatial distribution comprises estimating a geographical correlation of each pair of categories, using a vector describing the geographical correlation of each pair by a vector;

and evaluating a similarity between each pair of the regions using the regions'"'"' correlation vectors.

7. The method of claim 1, further comprising calculating the spatial distribution comprises determining at least one of:

a mutual distance, a distance between at least two geographical candidates;

or

a reference distance, an average distance of the geographical candidates to a reference point.

8. The method of claim 1, further comprising pruning the set of geographical candidates based on a category-based pruning and a spatial feature-based pruning.

9. The method of claim 1, further comprising identifying a start level in a quadtree as a seed and gradually expanding seeds to regions of a shape similar to the query region and the seeds have a similarity value to the query region.

10. A system comprising:

a memory;

a processor coupled to the memory to perform acts comprising;

providing a spatial map containing geographical regions partitioned with points of interests based at least in part on representative categories;

identifying a user-specified region with a point of interest in a representative category in the spatial map;

searching for a set of geographical candidates with points of interests in representative categories based at least in part on a content similarity and a spatial similarity to the point of interest in the representative category in the user-specified region; and

presenting top geographical candidates with similar points of interests to the point of interest identified in the user-specified region.

11. The system of claim 10, wherein the partitioned comprises imposing a grid on the spatial map to determine an inverse region frequency of the representative category.

12. The system of claim 10, further comprising calculating the spatial distribution comprises using a spatial vector space model to determine at least one of:

a mutual distance, a distance between at least two geographical candidates;

or

a reference distance, an average distance of the geographical candidates to a reference point.

13. The system of claim 10, wherein the content similarity comprises points of interests and representative categories;

and the spatial similarity comprises distributions of points of interests in representative categories and reference points.

14. The system of claim 10, further comprising performing representative categories pruning and spatial feature-based pruning on the set of geographical candidates.

15. One or more computer-readable media encoded with instructions that, when executed by a processor, perform acts comprising:

selecting a query region with a point of interest in a representative category in the spatial map;

in response to the query region, receiving a set of geographical candidates in the spatial map that includes representative categories;

calculating whether the query region and the set of candidates in the spatial map include content information that is similar having common geometric properties, common content properties, and common spatial properties; and

presenting top geographical regions from the set of candidates that have content information that is similar to the user-specified region.

16. The computer-readable media of claim 15, further comprising providing a spatial map containing geographical regions partitioned with points of interests based at least in part on the representative categories.

17. The computer-readable media of claim 15, wherein the content information comprises geometric properties that include a scale and a shape;

content properties that include points of interests and representative categories; and

spatial properties that include distributions of points of interests of representative categories and reference points.

18. The computer-readable media of claim 15, further comprising analyzing a shape and a size of the query region to determine a quadtree layer to initiate a similar region search for the set of geographical candidates.

19. The computer-readable media of claim 15, further comprising performing representative categories pruning and spatial feature-based pruning on the set of geographical candidates.

20. The computer-readable media of claim 15, further comprising identifying a start level in a quadtree as a seed and gradually expanding seeds to regions of a shape similar to the query region and the seeds have a similarity value to the query region.