Making Friend and Location Recommendations Based on Location Similarities

• US 20100153292A1
• Filed: 12/11/2008
• Published: 06/17/2010
• Est. Priority Date: 12/11/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Xie, Xing, Zheng, Yu
• Application Number:
  US12/332,371
• Publication Number:
  US 20100153292A1
• Time in Patent Office: Days
• US Class Current: 705/347
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: G06Q 50/01 Social networking

Abstract

Method for making a recommendation to a first user in a computing network, including calculating one or more similarity scores between the first user and one or more remaining users in the network, identifying a portion of the remaining users having a highest similarity scores, identifying one or more locations visited by the portion of the remaining users but not by the first user, determining an interest level of the first user in each location, ranking the locations based on the interest levels, and displaying the locations based on the ranking as a first recommendation.

Claims

1. A method for making a recommendation to a first user in a computing network, comprising:

calculating one or more similarity scores between the first user and one or more remaining users in the network;

identifying a portion of the remaining users having a highest similarity scores;

identifying one or more locations visited by the portion of the remaining users but not by the first user;

determining an interest level of the first user in each location;

ranking the locations based on the interest levels; and

displaying the locations based on the ranking as a first recommendation.

2. The method of claim 1, wherein calculating the one or more similarity scores comprises:

receiving one or more Global Positioning System (GPS) logs from each user in the network;

constructing a hierarchal graph for the first user'"'"'s GPS log;

constructing a hierarchal graph for each remaining user'"'"'s GPS log; and

determining the similarity scores based on one or more similarities between the hierarchal graph for the first user'"'"'s GPS log and the hierarchal graph for each remaining user'"'"'s GPS log.

3. The method of claim 2, wherein identifying the locations visited by the portion of the remaining users comprises:

comparing the first user'"'"'s hierarchal graph with each remaining user'"'"'s hierarchal graph; and

identifying the locations that are on each remaining user'"'"'s hierarchal graph but are not on the first user'"'"'s hierarchal graph.

4. The method of claim 1, further comprising displaying the portion of the remaining users having the highest similarity scores as a second recommendation.

5. The method of claim 1, wherein determining the interest level comprises:

determining a number of visits made to each location by each user;

determining an implicit rating of each location for each user based on the number of visits; and

using a collaborative filtering-based method to quantify the interest level based on the implicit ratings.

6. The method of claim 1, wherein determining the interest level comprises:

representing the one or more locations as one or more vectors, each vector indicating one or more point of interest categories (POI) that exist in each location;

receiving a desired POI category of the first user;

identifying a subset of the vectors having a concentration of the desired POI category that exceeds a predetermined level; and

associating the locations that correspond to the subset of vectors.

7. The method of claim 6, wherein the POI categories comprise restaurants, entertainment, sports, and travel destinations.

8. The method of claim 6, wherein each vector indicates a number of restaurants, entertainment, sports, and travel destinations that exist in each location.

9. The method of claim 1, wherein determining the interest level comprises:

creating a first set of vectors for each location visited by the first user;

creating a second set of vectors for each location visited by the portion of the remaining users but not by the first user;

comparing the first set of vectors with the second set of vectors; and

inferring the interest level of the first user in each vector of the second set of vectors based on similarities between the first set of vectors and the second set of vectors.

10. The method of claim 9, wherein inferring the interest level comprises using a cosine similarity measurement.

11. A computer-readable medium having stored thereon computer-executable instructions which, when executed by a computer, cause the computer to:

receive one or more Global Positioning System (GPS) logs from each user in a network;

construct a hierarchal graph for the first user'"'"'s GPS log;

construct a hierarchal graph for each remaining user'"'"'s GPS log;

determine one or more similarity scores based on one or more similarities between the hierarchal graph for the first user'"'"'s GPS log and the hierarchal graph for each remaining user'"'"'s GPS log;

identify a portion of the remaining users having a highest similarity scores;

identify one or more locations visited by the portion of the remaining users but not by the first user;

determine an interest level of the first user in each location;

rank the locations based on the interest levels; and

display the locations based on the ranking as a first recommendation.

12. The computer-readable medium of claim 11, wherein the computer-executable instructions which, when executed by a computer, cause the computer to identify the locations visited by the portion of the remaining users comprises computer-executable instructions which, when executed by a computer, cause the computer to:

compare the first user'"'"'s hierarchal graph with each remaining user'"'"'s hierarchal graph; and

identify the locations that are on each remaining user'"'"'s hierarchal graph but are not on the first user'"'"'s hierarchal graph.

13. The computer-readable medium of claim 11, wherein the computer-executable instructions which, when executed by a computer, further comprises computer-executable instructions which, when executed by a computer, cause the computer to display the portion of the remaining users having the highest similarity scores as a second recommendation.

14. The computer-readable medium of claim 11, wherein the computer-executable instructions which, when executed by a computer, cause the computer to determine the interest level comprises computer-executable instructions which, when executed by a computer, cause the computer to:

determine a number of visits made to each location by each user;

determine an implicit rating of each location for each user based on the number of visits; and

use a collaborative filtering-based method to quantify the interest level based on the implicit ratings.

15. The computer-readable medium of claim 11, wherein the computer-executable instructions which, when executed by a computer, cause the computer to determine the interest level comprises computer-executable instructions which, when executed by a computer, cause the computer to:

represent the one or more locations as one or more vectors, each vector indicating one or more point of interest categories (POI) that exist in each location;

receive a desired POI category of the first user;

identify a subset of the vectors having a concentration of the desired POI category that exceeds a predetermined level; and

associate the locations that correspond to the subset of vectors.

16. A computer system, comprising:

a processor; and

a memory comprising program instructions executable by the processor to;

receive one or more Global Positioning System (GPS) logs from each user in a network;

construct a hierarchal graph for the first user'"'"'s GPS log;

construct a hierarchal graph for each remaining user'"'"'s GPS log;

determine one or more similarity scores based on one or more similarities between the hierarchal graph for the first user'"'"'s GPS log and the hierarchal graph for each remaining user'"'"'s GPS log;

identify a portion of the remaining users having a highest similarity scores;

identify one or more locations visited by the portion of the remaining users but not by the first user;

determine an interest level of the first user in each location;

rank the locations based on the interest levels;

display the locations based on the ranking as a first recommendation; and

display the portion of the remaining users having the highest similarity scores as a second recommendation.

17. The computer system of claim 16, wherein the program instructions executable by the processor to identify the locations visited by the portion of the remaining users comprise program instructions executable by the processor to:

compare the first user'"'"'s hierarchal graph with each remaining user'"'"'s hierarchal graph; and

identify the locations that are on each remaining user'"'"'s hierarchal graph but are not on the first user'"'"'s hierarchal graph.

18. The computer system of claim 16, wherein the program instructions executable by the processor to determine the interest level comprise program instructions executable by the processor to:

represent the one or more locations as one or more vectors, each vector indicating one or more point of interest categories (POI) that exist in each location;

receive a desired POI category of the first user;

identify a subset of the vectors having a concentration of the desired POI category that exceeds a predetermined level; and

associate the locations that correspond to the subset of vectors.

19. The computer system of claim 18, wherein the POI categories comprise restaurants, entertainment, sports, and travel destinations.

20. The computer system of claim 16, wherein the program instructions executable by the processor to determine the interest level comprise program instructions executable by the processor to:

create a first set of vectors for each location visited by the first user;

create a second set of vectors for each location visited by the portion of the remaining users but not by the first user;

compare the first set of vectors with the second set of vectors; and

infer the interest level of the first user in each vector of the second set of vectors based on similarities between the first set of vectors and the second set of vectors.