Scalable system and method for real-time predictions and anomaly detection

1. A method for detecting an event or anomaly in real-time and for triggering an action based thereon, the method comprising:

receiving a stream of data from data sources, the data including at least two categorical features and a real-value measure;

performing sketching on the categorical features using min-wise hashing to create sketches of the data;

learning a regression tree on the sketches so as to minimize a desired loss function;

determining whether the event or anomaly exists; and

triggering the action based on at least one of a type, location or magnitude of the determined event or anomaly.

2. The method according to claim 1 , wherein the desired loss function is a mean squared error, wherein the regression tree is built starting with a tree consisting of a single node which stores the data, wherein each leaf node comprises a mean of the real-value measures, and wherein the leaf nodes are split by partitioning the data based on the categorical features until a reduction of the mean squared error above a predetermined threshold is no longer achievable.

3. The method according to claim 2 , wherein boosting is applied to the regression tree.

4. The method according to claim 1 , further comprising updating the sketches and learning regression trees on the updated sketches.

5. The method according to claim 1 , further comprising estimating, from the sketches, a generalized Jaccard similarity for a given profile and a size of a union sets that define the given profile.

6. The method according to claim 1 , wherein the method is used in a crowd detection system, wherein the categorical features include at least a time and a location and the real-value measure includes a number of detected objects or persons, wherein the event or anomaly is a crowd, and wherein the action includes at least one of:

sending an alert to a public office or official;

automatically opening or closing a road, on-ramp or intersection;

remotely controlling traffic signals and traffic signs;

triggering an alarm; or

sending alternative directions to a navigation-enabled device.

7. The method according to claim 1 , wherein the method is used in a recommendation system, wherein the categorical features include at least a user category and a content-type category and the real-value measure includes a user rating, and wherein the action includes at least one of:

sending a targeted advertisement to a user;

making a recommendation to the user for a particular type of content; or

triggering an alert.

8. The method according to claim 1 , wherein the method is used in a flight management system, wherein the categorical features include at least a time and a location and the real-value measure includes a flight delay length, and wherein the action includes at least one of:

transmitting instructions to reroute a flight;

rescheduling flight departure times; or

changing arrival gates.

9. The method according to claim 1 , wherein the method is used in a weather station, wherein the categorical features include at least a time and a location and the real-value measure includes a temperature, and wherein the action includes transmitting a weather alert.

10. The method according to claim 1 , wherein the regression tree is incrementally built by providing the sketches for each of the categorical features as input to a regression tree algorithm which splits leaf nodes depending on estimates of mean squared error from the sketches for each of the categorical features.

11. A system for detecting an event or anomaly in real-time and for triggering an action based thereon, the system comprising at least one server or processor configured to:

receive a stream of data from data sources, the data including at least two categorical features and a real-value measure;

perform sketching on the categorical features using min-wise hashing to create sketches of the data;

learn a regression tree on the sketches so as to minimize a desired loss function;

determine whether the event or anomaly exists; and

trigger the action based on at least one of a type, location or magnitude of the determined event or anomaly.

12. The system according to claim 11 , wherein the system is a crowd detection system, wherein the categorical features include at least a time and a location and the real-value measure includes a number of detected objects or persons, wherein the event or anomaly is a crowd, and wherein the actions include at least one of:

sending an alert to a public office or official;

automatically opening or closing a road, on-ramp or intersection;

remotely controlling traffic signals and traffic signs;

triggering an alarm; or

sending alternative directions to a navigation-enabled device.

13. The system according to claim 11 , wherein the system is a recommendation system, wherein the categorical features include at least a user category and a content-type category and the real-value measure includes a user rating, and wherein the actions include at least one of:

sending a targeted advertisement to a user;

making a recommendation to the user for a particular type of content; or

triggering an alert.

14. The system according to claim 11 , wherein the system is a flight management system, wherein the categorical features include at least a time and a location and the real-value measure includes a flight delay length, and wherein the actions include at least one of:

transmitting instructions to reroute a flight;

rescheduling flight departure times; or

changing arrival gates.

15. The system according to claim 11 , wherein the system is part of a weather station, wherein the categorical features include at least a time and a location and the real-value measure includes a temperature, and wherein the action includes transmitting a weather alert.

16. A tangible, non-transitory computer medium having instructions thereon which when run on at least one processor or server cause the following steps to be performed:

receiving a stream of data from data sources, the data including at least two categorical features and a real-value measure;

performing sketching on the categorical features using min-wise hashing to create sketches of the data;

learning a regression tree on the sketches so as to minimize a desired loss function;

determining whether the event or anomaly exists; and

triggering the action based on at least one of a type, location or magnitude of the determined event or anomaly.