Back to results
US 11,232,085 B2Granted
Outlier detection for streaming data
AssigneeAmazon Technologies, Inc.
InventorsNina Mishra, Daniel Blick, Sudipto Guha, Okke Joost Schrijvers
Life of this patent
Estimating the term…
Abstract
Random cut trees are generated with respective to respective samples of a baseline set of data records of a data set for which outlier detection is to be performed. To construct a particular random cut tree, an iterative splitting technique is used, in which the attribute along which a given set of data records is split is selected based on its value range. With respect to a newly-received data record of the stream, an outlier score is determined based at least partly on a potential insertion location of a node representing the data record in a particular random cut tree, without necessarily modifying the random cut tree.
Claims21
A system, comprising:
- one or more computing devices of a network-accessible analytics service implemented at a provider network, wherein the one or more computing devices respectively comprise one or more processors and memory;
- wherein the one or more computing devices are configured to:
- receive a request, via a programmatic interface from a client, to perform outlier detection on observation records of a streaming data source, wherein individual ones of the observation records comprise values of a plurality of attributes;
- collect a baseline set of observation records of the streaming data source;
- generate a plurality of random cut trees corresponding to respective samples of the baseline set of observation records, wherein generation of a particular random cut tree corresponding to a particular sample of the observation records comprises one or more iterations of:
- select a particular attribute from among the plurality of attributes of the observation records to define a split of the particular sample of the observation records, based at least in part on a size of a range of values of the particular attribute over the particular sample of the observation records being larger than a size of a range of values of one or more other attributes of the plurality of attributes over the particular sample of the observation records;
- and
- split at least a portion of the particular sample of the observation records into two different groups of observation records based on a split value selected for the particular attribute;
- in response to obtaining a particular observation record which is not included in the baseline set of the observation records,
- compute an outlier score for the particular observation record based at least in part on a potential insertion location within the particular random cut tree identified for the particular observation record;
- and
- in response to a determination, made according to a probabilistic stream sample update algorithm, that the sample corresponding to the particular random cut tree is to include the particular observation record, insert a node representing the particular observation record into the particular random cut tree;
- and
- in response to determining that the outlier score meets a result reporting criterion, provide an indication of the outlier score to the client.
11 more elements
A method, comprising:
- performing, by one or more computing devices:
- determining that outlier detection is to be performed on data records of a stream, wherein individual ones of the data records comprise values of a plurality of attributes;
- collecting a baseline set of data records of the stream;
- generating one or more random cut trees corresponding to respective samples of the baseline set of data records of the stream, wherein generation of a particular random cut tree corresponding to a particular sample of the data records comprises one or more iterations of:
- selecting a particular attribute from among the plurality of attributes of the data records to define a split of the particular sample of the data records, based at least in part on a size of a range of values of the particular attribute over the particular sample of the data records being larger than a size of a range of values of one or more other attributes of the plurality of attributes over the particular sample of the data records;
- and
- splitting at least a portion of the particular sample of the data records into two different groups of data records based on a split value selected for the particular attribute;
- in response to obtaining a particular data record which is not included in the baseline set of the data records,
- computing an outlier score computed for the particular data record based at least in part on a potential insertion location within the particular random cut tree identified for the particular data record;
- and
- providing an indication of the outlier score to a client.
8 more elements
A non-transitory computer-accessible storage medium storing program instructions that when executed by one or more processors:
- collect a baseline set of data records of a data set;
- generate one or more random cut trees corresponding to respective samples of the baseline set of data records of the data set, wherein individual ones of the data records comprise values of a plurality of attributes, wherein generating a particular random cut tree corresponding to a particular sample of the data records comprises one or more iterations of:
- select a particular attribute from among the plurality of attributes of the data records to define a split of the particular sample of the data records, based at least in part on a size of a range of values of the particular attribute over the particular sample of the data records being larger than a size of a range of values of one or more other attributes of the plurality of attributes over the particular sample of the data records;
- and
- split at least a portion of the particular sample of the data records into two different groups of data records based on a split value selected for the particular attribute;
- obtain a particular data record of the data set, wherein the particular data record is not included in the baseline set of the data records;
- compute an outlier score for the particular data record based at least in part on a potential insertion location within the particular random cut tree identified for the particular data record;
- and
- provide an indication of the outlier score to a client.
6 more elements
Dependencies are inferred from the claim text.