System and method for changepoint detection in streaming data

A computing device, comprising:

• a processor;
• and
• a non-transitory computer-readable medium having stored thereon instructions that, when executed by the processor, cause the processor to perform operations including:
• receiving a data stream comprised of a plurality of data points that are received one by one in an arbitrary order and wherein a number of data points in the plurality of data points is not fixed;
• performing a set of operations resulting in a detection of one or more changepoints in the data stream, wherein the set of operations includes:
• maintaining a listing of starting indices for each run within the data stream in a buffer of size_L wherein each index of the listing has a run length probability representing a likelihood of being a changepoint, wherein a run is a sequence of data points, and wherein the size_L represents a first size of the buffer being a first number of data points,
• receiving a new data point within the data stream and adding a new index to the buffer resulting in the buffer having size_L+1, and wherein the size_L+1 represents a second size of the buffer being a second number of data points that is one greater than the first size,
• calculating a posterior run length probability that the new data point is a new changepoint, and
• removing an index from the listing that has a lowest run length probability resulting in a return of the buffer to size_L;
• and
• when a determination is made indicating the index removed from the listing does not correspond to the new data point, identifying a changepoint associated with the new data point;
• and
• when a determination is made indicating that the index removed from the listing does correspond to the new data point, identifying that the new data point is not associated with the changepoint.

A non-transitory computer-readable medium having stored thereon instructions that, when executed by one or more processors, cause the one or more processors to perform operations including:

• receiving a data stream comprised of a plurality of data points that are received one by one in an arbitrary order and wherein a number of data points in the plurality of data points is not fixed;
• performing a set of operations resulting in a detection of one or more changepoints in the data stream, wherein the set of operations includes:
• maintaining a listing of starting indices for each run within the data stream in a buffer of size_L wherein each index of the listing has a run length probability representing a likelihood of being a changepoint, wherein a run is a sequence of data points, and wherein the size_L represents a first size of the buffer being a first number of data points,
• receiving a new data point within the data stream and adding a new index to the buffer resulting in the buffer having size_L+1, and wherein the size_L+1 represents a second size of the buffer being a second number of data points that is one greater than the first size,
• calculating a posterior run length probability that the new data point is a new changepoint, and
• removing an index from the listing that has a lowest run length probability resulting in a return of the buffer to size_L;
• and
• when a determination is made indicating the index removed from the listing does not correspond to the new data point, identifying a changepoint associated with the new data point;
• and
• when a determination is made indicating that the index removed from the listing does correspond to the new data point, identifying that the new data point is not associated with the changepoint.