PARALLEL PROCESSING OF AN ORDERED DATA STREAM
First Claim
1. A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:
- processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements;
storing the plurality of sets of output data elements in a plurality of buffers, each buffer associated with one of the worker units; and
outputting an ordered output data stream while the input data stream is being processed by outputting selected output data elements from the buffers in an order that is based on the order keys.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, with each order key associated with one of the input data elements, includes processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements. The plurality of sets of output data elements is stored in a plurality of buffers, with each buffer associated with one of the worker units. An ordered output data stream is output while the input data stream is being processed by outputting selected output data elements from the buffers in an order that is based on the order keys.
45 Citations
20 Claims
-
1. A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:
-
processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements; storing the plurality of sets of output data elements in a plurality of buffers, each buffer associated with one of the worker units; and outputting an ordered output data stream while the input data stream is being processed by outputting selected output data elements from the buffers in an order that is based on the order keys. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A computer-readable storage medium storing computer-executable instructions for performing a method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:
-
processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a corresponding plurality of sets of output data elements; storing the plurality of sets of output data elements in a corresponding plurality of buffers, each buffer associated with one of the worker units; selecting output data elements from the buffers in an order based on the order keys; and outputting the selected output data elements from the buffers in an ordered output data stream while the input data stream is being processed. - View Dependent Claims (18, 19)
-
-
20. A method of parallel processing an ordered input data stream that includes a plurality of input data elements and a corresponding plurality of order keys for indicating an ordering of the input data elements, each order key associated with one of the input data elements, the method comprising:
-
processing the input data stream in a parallel manner with a plurality of worker units, thereby generating a plurality of sets of output data elements; storing the plurality of sets of output data elements in a plurality of buffers, each buffer associated with one of the worker units; generating a data structure that includes a plurality of entries, each entry associated with one of the buffers and identifying a next output data element to be output from its associated buffer; and outputting an ordered output data stream while the input data stream is being processed by outputting selected output data elements from the buffers based on the data structure.
-
Specification