Expediting pattern matching queries against time series data

1. A method, comprising:

obtaining activity profiles of more than 10,000 individuals, each activity profile corresponding to a respective individual, and each activity profile including a plurality of activity records, each activity record indicating a geolocation, a timestamp indicating when the individual was at the geolocation, and an attribute of the geolocation other than geospatial or temporal attributes, the activity profiles being based, at least in part, on network traffic generated by the individuals with respective mobile computing devices;

for each activity profile, sorting the activity records in order of the timestamps to form respective sorted activity profiles;

obtaining a query having a rule specifying criteria to select a subset of the individuals, the criteria comprising:

an activity pattern comprising an activity, an amount of instances of the activity, a first relational operator, and a pattern duration of time over which the activity pattern is evaluated to determine whether the amount of instances of the activity satisfy a first condition specified by the first relational operator; and

a quantifier comprising an amount of instances of the activity pattern, a second relational operator, and a quantifier duration of time over which the quantifier is evaluated to determine whether the amount of instances of the activity pattern satisfies a second condition specified by the second relational operator;

for each sorted activity profile, with one or more processors:

initializing an activity pattern count;

initializing a quantifier count;

iterating through the sorted activity records in sorted order and at each iteration:

determining whether the attribute of the geolocation of the respective activity record matches the activity of the activity pattern and, in response to determining a match:

determining the activity pattern count;

determining whether the activity pattern count satisfies the first condition and, in response to determining that the first condition is satisfied:

 initializing the activity pattern count;

 determining the quantifier count; and

 determining whether the quantifier count satisfies the second condition and, in response to determining that the second condition is satisfied, designating the individual corresponding to the respective sorted activity profile as responsive to the query.

2. The method of claim 1 , comprising:

assigning different subsets of the 10,000 or more individuals to more than five computers; and

concurrently, for each of the subsets, determining, with the respective computer, which individuals are responsive to the query.

3. The method of claim 1 , wherein the query has a plurality of rules, and wherein the method comprises concurrently or consecutively evaluating each of the rules for each iteration through the sorted activity records before advancing to a next iteration.

4. The method of claim 1 , wherein the query has more than 10 rules, and wherein the method comprises:

assigning different subsets of the 10,000 or more individuals to 20 or more computers; and

concurrently, for each of the subsets, determining, with the respective computers, which individuals are responsive to the query, wherein determining which individuals are responsive to the query comprises concurrently or consecutively evaluating each of the rules for each iteration through the sorted activity records before advancing to a next iteration on a given computer among the 20 or more computers.

5. The method of claim 1 , wherein the activity of the activity pattern comprises a plurality of facets of geolocations in a geographic information system, and wherein a plurality of activity pattern counts corresponding to the plurality of facets are maintained when iterating through the sorted activity records.

6. The method of claim 5 , comprising:

while iterating through the sorted activity records, updating a mapping of the timestamps within a given instance of the pattern duration to activity pattern count and activity pairs.

7. The method of claim 5 , comprising:

while iterating through the sorted activity records, updating a mapping of the plurality of facets to respective activity pattern counts.

8. The method of claim 5 , comprising:

while iterating through the sorted activity records, updating a mapping of the plurality of facets to respective ones of a plurality of quantifier counts.

9. The method of claim 1 , wherein the activity pattern comprises a frequency, and wherein respective activity pattern counts are adjusted once or less within each cycle of the frequency.

10. The method of claim 1 , comprising performing steps for selecting content based on the query response.

11. A tangible, machine-readable, non-transitory media storing instructions that when executed by one or more computing devices effectuate operations comprising:

obtaining activity profiles of more than 10,000 individuals, each activity profile corresponding to a respective individual, and each activity profile including a plurality of activity records, each activity record indicating a geolocation, a timestamp indicating when the individual was at the geolocation, and an attribute of the geolocation other than geospatial or temporal attributes, the activity profiles being based, at least in part, on network traffic generated by the individuals with respective mobile computing devices;

for each activity profile, sorting the activity records in order of the timestamps to form respective sorted activity profiles;

obtaining a query having a rule specifying criteria to select a subset of the individuals, the criteria comprising:

an activity pattern comprising an activity, an amount of instances of the activity, a first relational operator, and a pattern duration of time over which the activity pattern is evaluated to determine whether the amount of instances of the activity satisfy a first condition specified by the first relational operator; and

a quantifier comprising an amount of instances of the activity pattern, a second relational operator, and a quantifier duration of time over which the quantifier is evaluated to determine whether the amount of instances of the activity pattern satisfies a second condition specified by the second relational operator;

for each sorted activity profile:

initializing an activity pattern count;

initializing a quantifier count;

iterating through the sorted activity records in sorted order and at each iteration:

determining whether the attribute of the geolocation of the respective activity record matches the activity of the activity pattern and, in response to determining a match:

determining the activity pattern count;

determining whether the activity pattern count satisfies the first condition and, in response to determining that the first condition is satisfied:

 initializing the activity pattern count;

 determining the quantifier count; and

 determining whether the quantifier count satisfies the second condition and, in response to determining that the second condition is satisfied, designating the individual corresponding to the respective sorted activity profile as responsive to the query.

12. The media of claim 11 , the operations comprising:

assigning different subsets of the 10,000 or more individuals to more than five computers; and

concurrently, for each of the subsets, determining, with the respective computer, which individuals are responsive to the query.

13. The media of claim 11 , wherein the query has a plurality of rules, and wherein the method comprises concurrently or consecutively evaluating each of the rules for each iteration through the sorted activity records before advancing to a next iteration.

14. The media of claim 11 , wherein the query has more than 10 rules, and wherein the operations comprise:

assigning different subsets of the 10,000 or more individuals to 20 or more computers; and

concurrently, for each of the subsets, determining, with the respective computers, which individuals are responsive to the query, wherein determining which individuals are responsive to the query comprises concurrently or consecutively evaluating each of the rules for each iteration through the sorted activity records before advancing to a next iteration on a given computer among the 20 or more computers.

15. The media of claim 11 , wherein the activity of the activity pattern comprises a plurality of facets of geolocations in a geographic information system, and wherein a plurality of activity pattern counts corresponding to the plurality of facets are maintained when iterating through the sorted activity records.

16. The media of claim 15 , the operations comprising:

while iterating through the sorted activity records, updating a mapping of the timestamps within a given instance of the pattern duration to activity pattern count and activity pairs.

17. The media of claim 15 , the operations comprising:

while iterating through the sorted activity records, updating a mapping of the plurality of facets to respective activity pattern counts.

18. The media of claim 15 , the operations comprising:

while iterating through the sorted activity records, updating a mapping of the plurality of facets to respective ones of a plurality of quantifier counts.

19. The media of claim 11 , wherein the activity pattern comprises a frequency, and wherein respective activity pattern counts are adjusted once or less within each cycle of the frequency.

20. The media of claim 11 , the operations comprising performing steps for selecting content based on the query response.