Digital signal processing over data streams

• US 10,178,161 B2
• Filed: 05/11/2016
• Issued: 01/08/2019
• Est. Priority Date: 05/11/2016
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Chandramouli, Badrish, Goldstein, Jonathan D., Nikolic, Milos
• Primary Examiner(s): Survillo, Oleg
• Assistant Examiner(s): Doan, Tan
• Application Number:
  US15/152,369
• Publication Number:
  US 20170331881A1
• Time in Patent Office: 972 Days
• Field of Search: 709217
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: H04L 47/82 Miscellaneous aspects
• CPC Class Codes: H04L 49/9042 Separate storage for different parts of the packet, e.g. header and payload
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks

Abstract

The techniques and systems described herein are directed to providing deep integration of digital signal processing (DSP) operations with a general-purpose query processor. The techniques and systems provide a unified query language for processing tempo-relational and signal data, provide mechanisms for defining DSP operators, and support incremental computation in both offline and online analysis. The techniques and systems include receiving streaming data, aggregating and performing uniformity processing to generate a uniform signal, and storing the uniform signal in a batched columnar representation. Data can be copied from the batched columnar representation to a circular buffer, where DSP operations are applied to the data. Incremental processing can avoid redundant processing. Improvements to the functioning of a computer are provided by reducing an amount of data that to be passed back and forth between separate query databases and DSP processors, and by reducing a latency of processing and/or memory usage.

Claims

1. A computer-implemented method comprising:

receiving streaming data from one or more sensors, wherein the streaming data includes a first functional payload associated with a first time interval and a second functional payload associated with a second time interval;

applying an aggregation operation to the streaming data to generate aggregated streaming data;

applying a uniformity operation to the aggregated streaming data to generate a uniform signal, wherein applying the uniformity operation comprises;

generating a first materialized value based on the first functional payload; and

generating a second materialized value based on the second functional payload;

storing the uniform signal in a batched columnar representation in a memory, wherein the uniform signal includes the first materialized value and the second materialized value;

accessing, from the batched columnar representation stored in the memory, a columnar array including a plurality of field values;

storing a portion of the plurality of the field values in a circular buffer in accordance with a data window, the data window associated with a digital signal processing (DSP) operation; and

applying the DSP operation to the portion of the plurality of the field values stored in the circular buffer to generate a DSP output.

2. The computer-implemented method of claim 1, wherein the portion of the plurality of the field values is a first portion, and wherein the DSP output is a first DSP output, the computer-implemented method further comprising:

storing a second portion of the plurality of the field values in the circular buffer in accordance with an incremental data window size;

applying the DSP operation to the second portion of the plurality of the field values to generate a second DSP output; and

generating an updated DSP output based at least in part on the first DSP output and the second DSP output.

3. The computer-implemented method of claim 2, further comprising maintaining a state of the DSP operation between generating the first DSP output and generating the second DSP output.

4. The computer-implemented method of claim 1, the uniformity operation including at least a sampling operation to generate a plurality of values at time values associated with a uniform sampling period.

5. The computer-implemented method of claim 1, the uniformity operation including at least an interpolation operation to generate at least one interpolated value at a time value associated with a uniform sampling period.

6. The computer-implemented method of claim 1, wherein storing the uniform signal in the batched columnar representation in the memory comprises generating at least a first batch and a second batch, the first batch associated with a first array of grouping keys based in part on a first time interval, and the second batch associated with a second array of grouping keys based in part on a second time interval.

7. The computer-implemented method of claim 1, further comprising selecting, as the DSP operation, at least one of a Fast Fourier Transform, a convolution, a Finite Impulse Response, an Infinite Impulse Response, and a digital filter.

8. The computer-implemented method of claim 1, wherein applying the aggregation operation to the streaming data to generate the aggregated streaming data includes grouping streaming data from at least a first sensor and a second sensor of the one or more sensors.

9. The computer-implemented method of claim 1, wherein each value of the plurality of field values is written to the circular buffer once in association with applying the DSP operation.

10. The computer-implemented method of claim 1, wherein the aggregation function comprises adding the first functional payload with a third functional payload, wherein a lambda function expresses the addition.

11. The computer-implemented method of claim 1, wherein generating the first materialized value based on the first functional payload comprises evaluating an identity function.

12. A system comprising:

one or more processors; and

memory storing modules that, when executed by the one or more processors, cause the system to perform operations comprising;

receiving streaming data from one or more sensors, wherein the streaming data includes a first functional payload associated with a first time interval and a second functional payload associated with a second time interval;

applying an aggregation operation to the streaming data to generate aggregated streaming data;

applying a uniformity operation to the aggregated streaming data to generate a uniform signal, wherein applying the uniformity operation comprises;

generating a first materialized value based on the first functional payload; and

generating a second materialized value based on the second functional payload;

storing the uniform signal in a batched columnar representation in a memory, wherein the uniform signal includes the first materialized value and the second materialized value;

accessing, from the batched columnar representation stored m the memory, a columnar array including a plurality of field values;

storing a portion of the plurality of the field values in a circular buffer in accordance with a data window, the data window associated with a digital signal processing (DSP) operation; and

applying the DSP operation to the portion of the plurality of the field values stored in the circular buffer to generate a DSP output.

13. The system as recited in claim 12, wherein the portion of the plurality of the field values is a first portion, and wherein the DSP output is a first DSP output, the operations further comprising:

storing a second portion of the plurality of the field values in the circular buffer in accordance with an incremental data window size;

applying the DSP operation to the second portion of the plurality of the field values to generate a second DSP output; and

generating an updated DSP output based at least in part on the first DSP output and the second DSP output.

14. The system as recited in claim 12, wherein storing the uniform signal in the batched columnar representation in the memory comprises generating at least a first batch and a second batch, the first batch associated with a first array of grouping keys based in part on a first time interval, and the second batch associated with a second array of grouping keys based in part on a second time interval.

15. The system as recited in claim 12, wherein applying the aggregation operation to the streaming data to generate the aggregated streaming data includes grouping streaming data from at least a first sensor and a second sensor of the one or more sensors.

16. A system comprising:

one or more processors; and

memory storing modules that, when executed by the one or more processors, cause the system to perform operations comprising;

receiving streaming data from a plurality of sensors, the streaming data including a first plurality of payloads associated with a first time value and a second plurality of payloads associated with a second time value;

applying an aggregation operation to the streaming data to generate aggregated streaming data, the aggregated streaming data including a first single payload associated with the first time value and a second single payload associated with the second time value;

applying an interpolation operation to the aggregated streaming data to generate a uniform signal, wherein the uniform signal includes a first interpolated value based on the first single payload and a second interpolated value based on the second single payload, wherein the first interpolated value and the second interpolated value are associated with a uniform sampling period and an offset value;

storing the uniform signal in a batched columnar representation in the memory, wherein the batched columnar representation comprises at least a first columnar array and a second columnar array, the first columnar array comprising a plurality of data fields stored in the memory, a first data field of the plurality of data fields storing the first interpolated value and a second data field of the plurality of data fields storing the second interpolated value, the second columnar array comprising at least a first array of grouping keys associated with a first data batch and a second array of grouping keys associated with a second data batch;

accessing, from the batched columnar representation stored in the memory, the first columnar array, the accessing performed without accessing the second columnar array;

storing at least the first data field and the second data field in a circular buffer in accordance with a data window, the data window associated with a digital signal processing (DSP) operation; and

applying the DSP operation to the first data field and the second data field stored in the circular buffer to generate a first DSP output.

17. The system of claim 16, wherein:

the streaming data further includes a third plurality of payloads associated with a third time value;

the aggregated streaming data further includes a third single payload associated with the third time value;

the uniform signal further includes a third interpolated value based on the third single payload, and wherein the third interpolated value is associated with the uniform sampling period and the offset value; and

the first columnar array further stores the third interpolated value in a third data field of the plurality of data fields; and

wherein the operations further comprise;

determining that the DSP operation has processed the first data field and the second data field associated with the data window;

storing at least the third field value in the circular buffer in accordance with an incremental data window associated with the DSP operation;

applying the DSP operation to the third data field stored in the circular buffer to generate a second DSP output; and

determining an updated DSP output based at least in part on the first DSP output and the second DSP output.

18. The system of claim 16, wherein the accessing the first columnar array without accessing the second columnar array improves a functioning of the system by reducing a memory usage and a processing time of the system.

19. The system of claim 16, wherein the first single payload includes a functional payload, and wherein generating the uniform signal includes at least evaluating the functional payload at the first time value to generate the first interpolated value.

20. The system of claim 16, wherein the operations further comprise processing a plurality of data batches stored in the batched columnar representation, the processing including inserting a latency control message between the first data batch of the plurality of data batches and the second data batch of the plurality of data batches, the latency control message to initiate a completion of the processing of the first data batch.