# US 10,310,910 B1 · Iterative autocorrelation calculation for big data using components > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,310,910 B1 - Document ID: US10310910B1 - Status: Granted - Kind: B1 - Application number: 14/964,084 - Filed: 2015-12-09 - Granted: 2019-06-04 - Earliest claimed: 2014-12-09 - Assignees: Cloud & Stream Gears LLC - Applicants: Jizhu Lu - Inventors: Jizhu Lu - Web page: https://patentgrep.com/patent/US10310910B1 ## CPC - H04L 47/20: Traffic policing - G06F 9/5083: {Techniques for rebalancing the load in a distributed system} - G06F 16/955: using information identifiers, e.g. uniform resource locators [URL] - G06F 17/15: Correlation function computation {including computation of convolution operations (arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00)} - G06F 17/153: {Multidimensional correlation or convolution} - H04L 67/60: Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources (admission control or resource allocation H04L47/70) - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - Y02D 10/00: Energy efficient computing, e.g. low power processors, power management or thermal management - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - Y02D: CLIMATE CHANGE MITIGATION TECHNOLOGIES IN INFORMATION AND COMMUNICATION TECHNOLOGIES [ICT], I.E. INFORMATION AND COMMUNICATION TECHNOLOGIES AIMING AT THE REDUCTION OF THEIR OWN ENERGY USE ## Abstract The present invention extends to methods, systems, and computing system program products for iteratively calculating autocorrelation at a specified lag for Big Data or streamed data in real time by iteratively calculating one or more components of autocorrelation at the specified lag l for a computation window of size n. Embodiments of the invention include iteratively calculating one or more components of autocorrelation at the specified lag l for an adjusted computation window based on the one or more components of the autocorrelation at the specified lag l calculated for a previous computation window and then calculating the autocorrelation at the specified lag l using the components. Iteratively calculating autocorrelation avoids visiting all data elements in the adjusted computation window and performing redundant computations thereby increasing calculation efficiency, saving computing resources and reducing computing system's power consumption. ## Claims ### Claim 1 A computing-system-implemented method for generating an autocorrelation at a specified lag for an adjusted computation window on a computing-device-based computing system which comprises one or more computing devices and one or more storage media, each of the one or more computing devices comprising one or more processors, the method comprising: initializing, by the computing-device-based computing system, a sum or a mean or both, and one or more components of an autocorrelation at a specified lag l (l>0) other than a sum and a mean for a pre-adjusted computation window of a specified size n (n>2*(l+1)), wherein the pre-adjusted computation window has two sides and contains n data elements of a data set on at least one of the one or more storage media; generating, by the computing-device-based computing system, an autocorrelation at lag l for the pre-adjusted computation window based on one or more of the initialized components; accessing or receiving, by the computing-device-based computing system, a data element to be removed from a side of the pre-adjusted computation window and a data element to be added to the other side of the pre-adjusted computation window; adjusting, by the computing-device-based computing system, the pre-adjusted computation window by: removing the to be removed data element from the pre-adjusted computation window; and adding the to be added data element to the pre-adjusted computation window; iteratively deriving, by the computing-device-based computing system, a sum or a mean or both for the adjusted computation window; directly iteratively deriving, by the computing-device-based computing system and based at least in part on the one or more components of the autocorrelation at lag l other than a sum and a mean for the pre-adjusted computation window, one or more components of an autocorrelation at lag l other than a sum and a mean for the adjusted computation window, wherein the directly iteratively deriving includes: accessing or receiving l data elements not including the added data element from each side of the adjusted computation window respectively without accessing or receiving all data elements in the adjusted computation window to reduce data access latency thereby saving computing resources and reducing the computing-device-based computing system's power consumption; accessing the one or more components of the autocorrelation at lag l other than a sum and a mean for the pre-adjusted computation window; and removing any contribution of the removed data element from each of the one or more accessed components and adding any contribution of the added data element to each of the one or more accessed components based on the removed data element, the added data element and/or the l data elements from each side of the adjusted computation window without using all data elements in the adjusted computation window thereby resulting in faster computation time; and generating, by the computing-device-based computing system and based on one or more of the derived components of the autocorrelation at lag l for the adjusted computation window, the autocorrelation at lag l for the adjusted computation window. ### Claim 2 (depends on 1) The computing-system-implemented method of claim 1, wherein the generating the autocorrelation at lag l further comprises indirectly iteratively deriving, by the computing-device-based computing system, one or more components of the autocorrelation at lag l for the adjusted computation window, wherein the indirectly iteratively deriving of the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 3 (depends on 1) The computing-system-implemented method of claim 1, wherein accessing or receiving a data element to be removed and a data element to be added includes accessing or receiving a plurality of z (z>1) data elements to be removed from the pre-adjusted computation window and accessing or receiving a plurality of z (z>1) data elements to be added to the pre-adjusted computation window, and wherein the method further comprises performing, for each of the respective z data elements to be removed and each of the respective z data elements to be added, the adjusting the pre-adjusted computation window, the iteratively deriving a sum or a mean or both for the adjusted computation window, the directly iteratively deriving one or more components of an autocorrelation at lag l for the adjusted computation window, and the generating the autocorrelation at lag l for the adjusted computation window. ### Claim 4 (depends on 3) The computing-system-implemented method of claim 3, wherein the generating the autocorrelation at lag l for the adjusted computation window comprises indirectly iteratively deriving, by the computing-device-based computing system, one or more components at lag l for the adjusted computation window, wherein the indirectly iteratively deriving the one or more components at lag l includes individually calculating each respective one of the one or more components at lag l based on one or more components other than the respective one component. ### Claim 5 (depends on 3) The computing-system-implemented method of claim 3, wherein the generating the autocorrelation at lag l for the adjusted computation window comprises generating an autocorrelation at lag l for the adjusted computation window only when the autocorrelation is accessed. ### Claim 6 (depends on 5) The computing-system-implemented method of claim 5, wherein the generating the autocorrelation at lag l for the adjusted computation window further comprises indirectly iteratively deriving, by the computing-device-based computing system, one or more components of the autocorrelation at lag l for the adjusted computation window, wherein the indirectly iteratively deriving the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 7 (depends on 1) The computing-system-implemented method of claim 1, wherein accessing or receiving a data element to be removed and a data element to be added includes accessing or receiving a plurality of z (z>1) data elements to be removed from the pre-adjusted computation window and accessing or receiving a plurality of z (z>1) data elements to be added to the pre-adjusted computation window, and wherein the method further consists of performing, for each of the respective z data elements to be removed and each of the respective z data elements to be added, the adjusting the pre-adjusted computation window, the iteratively deriving a sum or a mean or both for the adjusted computation window, the directly iteratively deriving one or more components of an autocorrelation at lag l for the adjusted computation window. ### Claim 8 A computing system, the computing system comprising: one or more computing devices; each computing device comprising one or more processors; one or more storage media having stored a data set; and one or more calculation modules that, when executed by at least one of the one or more computing devices, determine an autocorrelation at a specified lag for an adjusted computation window of a specified size of the data set, wherein determination of the autocorrelation includes to: a. initialize a sum or a mean or both, and one or more components of an autocorrelation at a specified lag l (l>0) other than a sum and a mean for a pre-adjusted computation window of a specified size n (n>2*(l+1)), wherein the pre-adjusted computation window contains n data elements of the data set and has two sides; b. generate an autocorrelation at lag l for the pre-adjusted computation window based on one or more of the initialized components; c. access or receive a data element to be removed from a side of the pre-adjusted computation window and a data element to be added to the other side of the pre-adjusted computation window; d. adjust the pre-adjusted computation window, including to: remove the to-be-removed data element from the pre-adjusted computation window; and add the to-be-added data element to the pre-adjusted computation window; e. iteratively calculate a sum or a mean or both for the adjusted computation window; f. directly iteratively calculate one or more components of an autocorrelation at lag l other than a sum and a mean for the adjusted computation window, including to: access or receive l data elements not including the added data element from each side of the adjusted computation window respectively without accessing or receiving all data elements in the adjusted computation window to reduce data access latency thereby saving computing resources and reducing the computing system's power consumption; access each of the one or more components of the autocorrelation at lag l other than a sum and a mean for the pre-adjusted computation window; and calculate each of the one or more components at lag l for the adjusted computation window by removing any contribution of the removed data element from each of the one or more accessed components and adding any contribution of the added data element to each of the one or more accessed components based on the removed data element, the added data element and/or the l data elements from each side of the adjusted computation window without using all data elements in the adjusted computation window thereby resulting in faster computation time; and g. generate, based on one or more of the calculated components of the autocorrelation at lag l for the adjusted computation window, the autocorrelation at lag l for the adjusted computation window. ### Claim 9 (depends on 8) The computing system of claim 8, wherein the generating the autocorrelation at lag l includes to indirectly iteratively calculate one or more components of the autocorrelation at lag l for the adjusted computation window, wherein indirectly iteratively calculating the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 10 (depends on 8) The computing system of claim 8, wherein one or more calculation modules that, when executed by at least one of the one or more computing devices, perform c, d, e, and f multiple times. ### Claim 11 (depends on 8) The computing system of claim 8, wherein one or more calculation modules that, when executed by at least one of the one or more computing devices, perform c, d, e, f, and g multiple times. ### Claim 12 (depends on 11) The computing system of claim 11, wherein the performing g comprises to indirectly iteratively calculate one or more components of the autocorrelation at lag l for the adjusted computation window, wherein indirectly iteratively calculating one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 13 (depends on 11) The computing system of claim 11, wherein the performing g comprises generating the autocorrelation at lag l for the adjusted computation window only when the autocorrelation is accessed. ### Claim 14 (depends on 13) The computing system of claim 13, wherein the generating the autocorrelation at lag l for the adjusted computation window further comprises to indirectly iteratively calculate one or more components of the autocorrelation at lag l for the adjusted computation window, wherein indirectly iteratively calculating the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 15 A computing system program product for use at a configured computing system that comprises one or more computing devices and one or more storage media, each computing device comprising one or more processors, the computing program product for implementing a method for generating an autocorrelation at a specified lag for an adjusted computation window, the computing system program product comprising one or more non-transitory computing-device-readable storage media having stored thereon computing-device-executable instructions that, when executed by at least one of the one or more computing devices in the configured computing system, cause the configured computing system to perform the method, the method including steps to: initialize, by the configured computing system, a sum or a mean or both, and one or more components of an autocorrelation at a specified lag l (l≥0) other than a sum and a mean for a pre-adjusted computation window of a specified size n (n>2*(l+1)), the pre-adjusted computation window having two sides and containing n data elements of a data set on at least one of the one or more storage media; generate, by the configured computing system, an autocorrelation at lag l for the pre-adjusted computation window based on one or more of the initialized components; access or receive, by the configured computing system, a data element to be removed from a side of the pre-adjusted computation window and a data element to be added to the other side of the pre-adjusted computation window; adjust, by the configured computing system, the pre-adjusted computation window, including to: remove the to-be-removed data element from the pre-adjusted computation window; and add the to-be-added data element to the pre-adjusted computation window; iteratively calculate, by the configured computing system, a sum or a mean or both for the adjusted computation window; directly iteratively calculate, by the configured computing system, one or more components of an autocorrelation at lag l other than a sum and a mean for the adjusted computation window based at least in part on the one or more components of the autocorrelation at lag l other than a sum and a mean calculated for the pre-adjusted computation window, including to: access or receive l data elements not including the added data element from each side of the adjusted computation window respectively without accessing or receiving all data elements in the adjusted computation window to reduce data access latency thereby saving computing resources and reducing the configured computing system's power consumption; access each of the one or more components of the autocorrelation at lag l other than a sum and a mean for the pre-adjusted computation window; and remove any contribution of the removed data element from each of the one or more accessed components and add any contribution of the added data element to each of the one or more accessed components based on the removed data element, the added data element and/or the l data elements from each side of the adjusted computation window without using all data elements in the adjusted computation window thereby resulting in faster computation time; and generate, by the configured computing system, the autocorrelation at lag l for the adjusted computation window based on one or more of the calculated components of the autocorrelation at lag l for the adjusted computation window. ### Claim 16 (depends on 15) The computing system program product of claim 15, wherein the computing-device-executable instructions that, when executed, cause the configured computing system to generate the autocorrelation comprise computing-device-executable instructions that, when executed, further cause the configured computing system to indirectly iteratively calculate one or more components of the autocorrelation at lag l for the adjusted computation window, wherein indirectly iteratively calculating the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 17 (depends on 15) The computing system program product of claim 15, wherein the computing-device-executable instructions that, when executed, further cause the configured computing system to access or receive the data element to be removed and the data element to be added, to adjust the pre-adjusted computation window, to iteratively calculate a sum or a mean or both for the adjusted computation window, to directly iteratively calculate the one or more components of an autocorrelation at lag l other than a sum and a mean for the adjusted computation window, and to generate the autocorrelation at lag l for the adjusted computation window for each of multiple data elements to be removed and each of multiple data elements to be added. ### Claim 18 (depends on 17) The computing system program product of claim 17, wherein the computing-device-executable instructions that, when executed, cause the configured computing system to generate the autocorrelation at lag l comprise computing-device-executable instructions that, when executed, cause the configured computing system to generate an autocorrelation at lag l for the adjusted computation window only when the autocorrelation is accessed. ### Claim 19 (depends on 18) The computing system program product of claim 18, wherein the computing-device-executable instructions that, when executed, cause the configured computing system to generate the autocorrelation at lag l comprise computing-device-executable instructions that, when executed, further cause the configured computing system to indirectly iteratively calculate one or more components of the autocorrelation at lag l for the adjusted computation window, wherein indirectly iteratively calculating the one or more components includes individually calculating each respective one of the one or more components based on one or more components other than the respective one component. ### Claim 20 (depends on 15) The computing system program product of claim 15, wherein the computing-device-executable instructions that, when executed, further cause the configured computing system to access or receive the data element to be removed and the data element to be added, to adjust the pre-adjusted computation window, to iteratively calculate a sum or a mean or both for the adjusted computation window, and to directly iteratively calculate the one or more components of an autocorrelation at lag l other than a sum and a mean for the adjusted computation window for each of multiple data elements to be removed and each of multiple data elements to be added.