# US 11,907,227 B1 · System and method for changepoint detection in streaming data > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,907,227 B1 - Document ID: US11907227B1 - Status: Granted - Kind: B1 - Application number: 17/591,511 - Filed: 2022-02-02 - Granted: 2024-02-20 - Earliest claimed: 2021-12-03 - Assignees: Splunk Inc. - Applicants: Splunk, Inc. - Inventors: Zhaohui Wang; Ryan Gannon; Xiao Lin; Abhinav Mishra; Chandrima Sarkar; Ram Sriharsha - Web page: https://patentgrep.com/patent/US11907227B1 ## CPC - G06Q 10/063112: {Skill-based matching of a person or a group to a task} - G06F 11/3452: {Performance evaluation by statistical analysis} - G06F 16/215: Improving data quality; Data cleansing, e.g. de-duplication, removing invalid entries or correcting typographical errors - G06F 16/22: Indexing; Data structures therefor; Storage structures - G06F 16/244: {Grouping and aggregation} - G06F 16/24552: {Database cache management} - G06F 16/24568: {Data stream processing; Continuous queries} - G06F 16/2462: {Approximate or statistical queries} - G06Q 10/1053: Employment or hiring - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A computerized method is disclosed including operations of receiving a data stream, performing a changepoint detection resulting in a detection of changepoints in the data stream including: 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, 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, calculating a posterior run length probability that the new data point is a changepoint, and removing an index from the listing that has a lowest run length probability thereby returning the buffer to size L, and responsive to determining the index removed from the listing does not correspond to the new data point, identifying a changepoint associated with the new data point. ## Claims ### Claim 1 A computerized method, comprising: 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; 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. ### Claim 2 (depends on 1) The computerized method of claim 1, wherein maintaining the listing of starting indices for each run within the data stream in the buffer of size_L includes storing each identified changepoint as a starting index. ### Claim 3 (depends on 1) The computerized method of claim 1, further comprising: detecting covariance data drift when the data stream includes multivariate data by obtaining a closed form posterior. ### Claim 4 (depends on 3) The computerized method of claim 3, wherein obtaining the closed form posterior includes specifying a multivariate normal distribution and a normal inverse Wishart prior. ### Claim 5 (depends on 3) The computerized method of claim 3, wherein the closed form posterior is a posterior Student's T-distribution. ### Claim 6 (depends on 1) The computerized method of claim 1, wherein calculating the posterior run length probability includes calculating a change in a parameter of a regression model based on Bayesian statistics. ### Claim 7 (depends on 1) The computerized method of claim 1, wherein performing the set of operations resulting in the detection of the one or more changes is the data stream is performed by one or more machine learning algorithms. ### Claim 8 (depends on 1) The computerized method of claim 1, wherein performing the set of operations resulting in the detection of the one or more changes is the data stream results in a storage requirement of O(size_L). ### Claim 9 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. ### Claim 10 (depends on 9) The computing device of claim 9, wherein maintaining the listing of starting indices for each run within the data stream in the buffer of size_L includes storing each identified changepoint as a starting index. ### Claim 11 (depends on 9) The computing device of claim 9, wherein the instructions that, when executed by the processor, cause the processor to perform further operations including: detecting covariance data drift when the data stream includes multivariate data by obtaining a closed form posterior. ### Claim 12 (depends on 11) The computing device of claim 11, wherein obtaining the closed form posterior includes specifying a multivariate normal distribution and a normal inverse Wishart prior. ### Claim 13 (depends on 11) The computing device of claim 11, wherein the closed form posterior is a posterior Student's T-distribution. ### Claim 14 (depends on 9) The computing device of claim 9, wherein calculating the posterior run length probability includes calculating a change in a parameter of a regression model based on Bayesian statistics, and wherein performing the set of operations resulting in the detection of the one or more changes is the data stream results in a storage requirement of O(size_L). ### Claim 15 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. ### Claim 16 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein maintaining the listing of starting indices for each run within the data stream in the buffer of size_L includes storing each identified changepoint as a starting index. ### Claim 17 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein the instructions that, when executed by the processor, cause the processor to perform further operations including: detecting covariance data drift when the data stream includes multivariate data by obtaining a closed form posterior. ### Claim 18 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein obtaining the closed form posterior includes specifying a multivariate normal distribution and a normal inverse Wishart prior. ### Claim 19 (depends on 17) The non-transitory computer-readable medium of claim 17, wherein the closed form posterior is a posterior Student's T-distribution. ### Claim 20 (depends on 15) The non-transitory computer-readable medium of claim 15, wherein calculating the posterior run length probability includes calculating a change in a parameter of a regression model based on Bayesian statistics, and wherein performing the set of operations resulting in the detection of the one or more changes is the data stream results in a storage requirement of O(size_L).