LARGE-SCALE HUMAN MOBILITY PATTERN RECOGNITION
First Claim
1. A method executed by a computer processor for grouping a plurality of trips of a mobile device, where each trip in the plurality of trips includes a set of trip traces from a plurality of traces for the mobile device, where the plurality of traces is collected from a plurality of base stations and stored in a trace storage, where each base station in the plurality of base stations includes a unique station-ID, where each trace in the plurality of traces includes a station-ID of a base station in the plurality of base stations and an association time indicating when the mobile device was associated with the base station, and where the mobile device is associated with at most one base station at any point in time, the method to group a first trip in the plurality of trips and a second trip in the plurality of trips by calculating an edit distance between the first trip and the second trip using an approximate string matching algorithm, the method comprising the steps of:
- identifying a first set of trip traces for the first trip and a second set of trip traces for the second trip in the plurality of traces for the mobile device;
extracting a first ordered set of station-IDs from the first set of trip traces and a second ordered set of station-IDs from the second set of trip traces, wherein each ordered set of station-IDs is ordered by association time;
calculating the edit distance between the first trip and the second trip by applying the approximate string matching algorithm to the first ordered set of station-IDs and the second ordered set of station-IDs;
checking that the edit distance between the first trip and the second trip is less than a preset edit distance threshold; and
grouping the first trip and the second trip into a group of trips in response to determining that the edit distance is less than the preset edit distance threshold.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for grouping trips of a mobile device, a trip including a set of trip traces from a plurality of traces collected from base stations. Each base station includes a unique station-ID. Each trace includes a station-ID and an association time indicating when the mobile device was associated with the base station. The mobile device is associated with at most one base station at any point in time. The method to group two trips by calculating an edit distance using an approximate string matching algorithm. The method includes identifying traces for the two trips, extracting ordered sets of station-IDs from the traces, calculating the edit distance between the two trips by applying the approximate string matching algorithm, to the ordered sets of station-IDs, checking if the edit distance is less than a preset edit distance threshold, and grouping the two trips into a group of trips.
-
Citations
24 Claims
-
1. A method executed by a computer processor for grouping a plurality of trips of a mobile device, where each trip in the plurality of trips includes a set of trip traces from a plurality of traces for the mobile device, where the plurality of traces is collected from a plurality of base stations and stored in a trace storage, where each base station in the plurality of base stations includes a unique station-ID, where each trace in the plurality of traces includes a station-ID of a base station in the plurality of base stations and an association time indicating when the mobile device was associated with the base station, and where the mobile device is associated with at most one base station at any point in time, the method to group a first trip in the plurality of trips and a second trip in the plurality of trips by calculating an edit distance between the first trip and the second trip using an approximate string matching algorithm, the method comprising the steps of:
-
identifying a first set of trip traces for the first trip and a second set of trip traces for the second trip in the plurality of traces for the mobile device; extracting a first ordered set of station-IDs from the first set of trip traces and a second ordered set of station-IDs from the second set of trip traces, wherein each ordered set of station-IDs is ordered by association time; calculating the edit distance between the first trip and the second trip by applying the approximate string matching algorithm to the first ordered set of station-IDs and the second ordered set of station-IDs; checking that the edit distance between the first trip and the second trip is less than a preset edit distance threshold; and grouping the first trip and the second trip into a group of trips in response to determining that the edit distance is less than the preset edit distance threshold. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A system for grouping a plurality of trips of a mobile device, wherein each trip in the plurality of trips includes a set of trip traces from a plurality of traces for the mobile device, wherein the plurality of traces is collected from a plurality of base stations, wherein each base station in the plurality of base stations includes a unique station-ID, wherein each trace in the plurality of traces includes a station-ID of a base station in the plurality of base stations and an association time indicating when the mobile device was associated with the base station, and wherein the mobile device is associated with at most one base station at any point in time, the system to group a first trip in the plurality of trips and a second trip in the plurality of trips by calculating an edit distance between the first trip and the second trip using an approximate string matching algorithm, the system comprising:
-
a trace storage configured to store the plurality of traces; a trip finding module coupled to the trace storage and configured to identify a first set of trip traces for the first trip and a second set of trip traces for the second trip in the plurality of traces for the mobile device; an edit distance calculation module configured to; extract a first ordered set of station-IDs from the first set of trip traces and a second ordered set of station-IDs from, the second set of trip traces, wherein each ordered set of station-IDs is ordered by association time, and calculate the edit distance between the first trip and the second trip by applying the approximate string matching algorithm to the first ordered set of station-IDs and the second ordered set of station-IDs; and a trip grouping module configured to; check that the edit distance between the first trip and the second trip is less than a preset edit distance threshold, and group the first trip and the second trip into a group of trips in response to determining that the edit distance is less than the preset edit distance threshold. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification