Back to results
US 8,412,667 B2Granted
Comparing and identifying similar tracks
AssigneeMicrosoft Corporation
InventorsLi Zhang, Maya Haridasan, Chandramohan A. Thekkath
Life of this patent
Estimating the term…
Abstract
The location of a user over time is monitored by a mobile device. The monitored locations are organized into tracks that describe a path or route that the user took over a period of time. Segments that correspond to each of the tracks are determined. The segments may correspond to road on a map, or some other standardization. The segments are associated with their corresponding tracks, and used to identify similar tracks or to generate similarity scores for pairs of tracks.
Claims15
A method comprising:
- receiving a plurality of tracks by a computing device, wherein each track comprises a plurality of location identifiers;
- receiving a plurality of segments by the computing device;
- for each track in the plurality of tracks, determining one or more segments from the plurality of segments that correspond to the track by the computing device;
- receiving an identifier of a track by the computing device;
- determining one or more segments from the plurality of segments that correspond to the identified track by the computing device;
- determining one or more tracks from the plurality of tracks that are similar to the identified track based on the one or more segments that correspond to the identified track and the one or more segments that correspond to each of the plurality of tracks by the computing device;
- generating a node corresponding to each segment;
- associating each node with the tracks that correspond to the segment of the node;
- identifying pairs of nodes that correspond to adjacent segments;
- and
- for each identified pair of nodes:
- determining if the pair of nodes is associated with at least one common track, and if so:
- generating a node for the identified pair of nodes, wherein the generated node is a parent of the identified pair of nodes and the identified pair of nodes are children of the generated node;
- and
- associating the generated node with the tracks associated with the identified pair of nodes;
- identifying a node that is in more than one identified node pair;
- determining the node pair that includes the identified node that has the greatest number of associated tracks;
- and
- removing at least one node pair from the identified pairs of nodes that includes the identified node that does not have the greatest number of associated tracks.
16 more elements
A method comprising:
- receiving a plurality of tracks by a computing device, wherein each track comprises a plurality of location identifiers;
- receiving a plurality of segments by the computing device;
- for each track in the plurality of tracks, determining one or more segments from the plurality of segments that correspond to the track by the computing device;
- receiving an identifier of a track by the computing device;
- determining one or more segments from the plurality of segments that correspond to the identified track by the computing device;
- determining one or more tracks from the plurality of tracks that are similar to the identified track based on the one or more segments that correspond to the identified track and the one or more segments that correspond to each of the plurality of tracks by the computing device:
- generating a node corresponding to each segment;
- associating each node with the tracks that correspond to the segment of the node;
- identifying pairs of nodes that correspond to adjacent segments;
- and
- for each identified pair of nodes:
- determining if the pair of nodes is associated with at least one common track, and if so:
- generating a node for the identified pair of nodes, wherein the generated node is a parent of the identified pair of nodes and the identified pair of nodes are children of the generated node;
- and
- associating the generated node with the tracks associated with the identified pair of nodes,
- wherein determining one or more tracks from the plurality of tracks that are similar to the identified track based on the one or more segments that correspond to the identified track and the one or more segments that correspond to each of the plurality of tracks comprises:
- determining nodes that are associated with the identified track;
- determining tracks from the plurality of tracks that are associated with the determined nodes;
- ranking the determined tracks, wherein a determined track associated with a parent node is ranked higher than a determined track associated with children nodes of the parent node;
- and
- selecting tracks that have a determined rank that is greater than a threshold rank as the one or more tracks from the plurality of tracks that are similar to the identified track.
18 more elements
A method comprising:
- receiving an identifier of a first track and an identifier of a second track by a computing device, wherein the first and second track each comprise a plurality of location identifiers;
- determining a first plurality of segments associated with the first track;
- determining a second plurality of segments associated with the second track;
- determining a third plurality of segments based on the first plurality of segments and the second plurality of segments, wherein the third plurality of segments comprises segments that are in both the first plurality of segments and the second plurality of segments;
- determining a fourth plurality of segments based on the first plurality of segments and the second plurality of segments, wherein the fourth plurality of segments comprises segments that are in either the first plurality of segments or the second plurality of segments;
- and
- determining a similarity score for the first and second tracks based on the third plurality of segments and the fourth plurality of segments.
4 more elements
Dependencies are inferred from the claim text.