DETERMINING USER SIMILARITIES BASED ON LOCATION HISTORIES

• US 20100111372A1
• Filed: 11/03/2008
• Published: 05/06/2010
• Est. Priority Date: 11/03/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/264,038
• Publication Number:
  US 20100111372A1
• Time in Patent Office: Days
• US Class Current: 382/113
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration

Abstract

Method for determining similarities between a first user and a second user in a network, including receiving one or more Global Positioning System (GPS) logs from each user in the network, constructing a first hierarchal graph for the first user'"'"'s GPS log and a second hierarchical graph for the second user'"'"'s GPS log, and calculating a similarity score between the first user and the second user based on the first hierarchal graph and the second hierarchical graph.

Claims

1. A method for determining similarities between a first user and a second user in a network, comprising:

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

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

calculating a similarity score between the first user and the second user based on the first hierarchal graph and the second hierarchical graph.

2. The method of claim 1, wherein constructing the first hierarchal graph and the second hierarchical graph comprises:

consolidating information of the GPS logs into a hierarchal framework;

creating the first hierarchical graph for the first user'"'"'s GPS log based on the hierarchal framework; and

creating the second hierarchical graph for the second user'"'"'s GPS log based on the hierarchal framework.

3. The method of claim 2, wherein consolidating the information of the GPS logs comprises:

formulating a first location history describing one more locations traveled by each user in a chronological order based on each user'"'"'s GPS log;

determining one or more stay points along each first location history;

grouping the stay points into one or more clusters;

grouping the stay points in the clusters into one or more subclusters; and

mapping the clusters into one or more higher layers of the hierarchal framework; and

mapping the subclusters into one or more lower layers of the hierarchical framework.

4. The method of claim 3, wherein determining the stay points comprises:

identifying a portion of the one or more locations that are within a predetermined distance threshold, wherein a time interval between a first location and a last location in the portion exceeds a predetermined time threshold;

extracting a latitude coordinate and a longitude coordinate for each identified location;

calculating an average of the latitude coordinates and the longitude coordinates of the portion of the locations; and

creating a stay point at the average of the latitude coordinates and the longitude coordinates.

5. The method of claim 3, wherein the stay points are grouped into the clusters and the subclusters using a density-based clustering algorithm.

6. The method of claim 3, wherein creating the first hierarchical graph comprises:

formulating a second location history describing the stay points traveled by the first user in a chronological order based on the first user'"'"'s GPS log;

mapping the stay points of the second location history to the clusters or subclusters in each layer of the hierarchical framework; and

creating a graph for each layer of the hierarchical framework, wherein the graph describes the clusters or subclusters traveled by the first user.

7. The method of claim 3, wherein creating the second hierarchical graph comprises:

formulating a third location history describing the stay points traveled by the second user in a chronological order based on the second user'"'"'s GPS log;

mapping the stay points of the third location history to the clusters or subclusters in each layer of the hierarchical framework; and

creating a graph for each layer of the hierarchical framework, wherein the graph describes the clusters or subclusters traveled by the second user.

8. The method of claim 3, wherein calculating the similarity score between the first user and the second user comprises:

extracting a sequence of clusters or subclusters traveled by the first user and the second user from one or more graphs in the first hierarchical graph and the second hierarchical graph, wherein each graph in the first hierarchical graph describes the clusters or subclusters traveled by the first user and each graph in the second hierarchical graph describes the clusters or subclusters traveled by the second user;

partitioning each sequence into one or more subsequences;

identifying a subsequence traveled by the first user and the second user having a maximum number of clusters or subclusters in common;

quantifying a popularity of each cluster or subcluster in the subsequence using an inverse document frequency methodology, wherein the inverse document frequency of the clusters or subclusters in common is defined as

9. The method of claim 8, wherein the maximum number of clusters or subclusters in common are in a same chronological order.

10. The method of claim 8, wherein a travel time between each cluster or subcluster in the maximum number of clusters or subclusters in common is substantially similar.

11. The method of claim 8, wherein partitioning each sequence comprises:

determining whether an amount of time between two consecutive clusters or subclusters in the sequence exceeds a time value; and

partitioning the sequence into subsequences where the two consecutive clusters or subclusters exceeds the time value.

12. The method of claim 8, wherein calculating the similarity score between the first user and the second user further comprises:

assigning a weight to the similarity score of each cluster or subcluster in common based on the maximum number of clusters or clusters in common.

13. The method of claim 8, wherein calculating the similarity score between the first user and the second user further comprises:

assigning a weight to the similarity score of each cluster or subcluster in common based on a layer in which the maximum number of clusters or clusters in common are located on the hierarchal framework.

14. 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 two or more users in the network;

consolidate information of the GPS logs into a hierarchal framework;

create a first hierarchical graph for the first user'"'"'s GPS log based on the hierarchal framework;

create a second hierarchical graph for the second user'"'"'s GPS log based on the hierarchal framework; and

calculate a similarity score between the first user and the second user based on the first hierarchal graph and the second hierarchical graph.

15. The computer system of claim 14, wherein the program instructions executable by the processor to consolidate information of the GPS logs into the hierarchal framework comprise program instructions executable by the processor to:

formulate a first location history describing one or more locations traveled by each user in a chronological order based on each user'"'"'s GPS log;

determine one or more stay points along each first location history;

group the stay points into one or more clusters;

group the stay points in the clusters into one or more subclusters; and

map the clusters into one or more higher layers of the hierarchal framework; and

map the subclusters into one or more lower layers of the hierarchical framework.

16. The computer system of claim 15, wherein the program instructions executable by the processor to determine the stay points comprise program instructions executable by the processor to:

identify a portion of the one or more locations that are within a predetermined distance threshold, wherein a time interval between a first location and a last location in the portion exceeds a predetermined time threshold;

extract a latitude coordinate and a longitude coordinate for each identified location;

calculate an average of the latitude coordinates and the longitude coordinates of the portion of the locations; and

create a stay point at the average of the latitude coordinates and the longitude coordinates.

17. The computer system of claim 15, wherein the stay points are grouped into the clusters and the subclusters using a density-based clustering algorithm.

18. 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 two or more users in the network;

formulate a first location history describing one or more locations traveled by each user in a chronological order based on each user'"'"'s GPS log;

determine one or more stay points along each first location history;

group the stay points into one or more clusters;

group the stay points in the clusters into one or more subclusters; and

map the clusters into one or more higher layers of a hierarchal framework;

map the subclusters into one or more lower layers of the hierarchical framework;

create a first hierarchical graph for the first user'"'"'s GPS log based on the hierarchal framework;

create a second hierarchical graph for the second user'"'"'s GPS log based on the hierarchal framework; and

calculate a similarity score between the first user and the second user based on the first hierarchal graph and the second hierarchical graph.

19. The computer-readable medium of claim 18, wherein the computer-executable instructions to calculate the similarity score between the first user and the second user are configured to:

extract a sequence of clusters or subclusters traveled by the first user and the second user from one or more graphs in the first hierarchical graph and the second hierarchical graph, wherein each graph in the first hierarchical graph describes the clusters or subclusters traveled by the first user and each graph in the second hierarchical graph describes the clusters or subclusters traveled by the second user;

partition each sequence into one or more subsequences;

identify a subsequence traveled by the first user and the second user having a maximum number of clusters or subclusters in common;

quantify a popularity of each cluster or subcluster in the subsequence using an inverse document frequency methodology, wherein the inverse document frequency of the clusters or subclusters in common is defined as

20. The computer-readable medium of claim 18, wherein the stay points are grouped into the clusters and the subclusters using a density-based clustering algorithm.