Sorting a dataset of incrementally received data

• US 8,843,502 B2
• Filed: 06/24/2011
• Issued: 09/23/2014
• Est. Priority Date: 06/24/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Elson, Jeremy Eric, Nightingale, Edmund Bernard, Hofmann, Owen Sebastian
• Primary Examiner(s): ALAM, SHAHID AL
• Application Number:
  US13/168,491
• Publication Number:
  US 20120330979A1
• Time in Patent Office: 1,187 Days
• Field of Search: 707/752, 707/609, 707/661, 707/803, 707/662, 707/673, 707/694, 707/715, 707/740, 707/769, 707/792, 707/802, 707/825, 707/827, 707/948, 709/201, 709/203, 709/225, 709/229, 709/246
• US Class Current: 707/752
• CPC Class Codes: G06F 16/2308 Concurrency control transaction processing G06F9/466
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/90348 by searching ordered data, e.g. alpha-numerically ordered data

Abstract

A method of sorting a dataset includes incrementally receiving data from the dataset, and incrementally storing the received data as individual input data subsets as the data is received, thereby sequentially generating a plurality of filled data subsets of unsorted data. The method includes individually sorting each filled data subset of unsorted data concurrently with receiving data for a next one of the individual input data subsets, thereby sequentially generating a plurality of sorted input data subsets, and performing a merge sort on the plurality of sorted input data subsets, thereby incrementally generating a sorted version of the dataset.

Claims

1. A method of sorting a dataset, comprising:

incrementally receiving data from the dataset;

incrementally storing the received data as individual input data subsets as the data is received, thereby sequentially generating a plurality of filled data subsets of unsorted data;

individually sorting each filled data subset of unsorted data concurrently with receiving data for a next one of the individual input data subsets, thereby sequentially generating a plurality of sorted input data subsets;

performing a merge sort on the plurality of sorted input data subsets, thereby incrementally generating a sorted version of the dataset, wherein the sorted version of the dataset includes a plurality of sequentially generated sorted output data subsets;

varying a size of the individual input data subsets based on a size of the dataset; and

outputting each of the sorted output data subsets concurrently with generating a next one of the sorted output data subsets.

2. The method of claim 1, wherein the sorted output data subsets each have a same size as the individual input data subsets.

3. The method of claim 1, wherein the outputting each of the sorted output data subsets comprises outputting each of the sorted output data subsets to a storage medium.

4. The method of claim 1, wherein the outputting each of the sorted output data subsets comprises outputting each of the sorted output data subsets to a network file system.

5. The method of claim 1, wherein the individual input data subsets each have a size that is a predetermined fraction of a size of the dataset.

6. The method of claim 1, wherein the dataset is stored as a plurality of portions on a plurality of computing devices, and wherein the data from the dataset is incrementally received from the plurality of computing devices.

7. The method of claim 1, wherein the individually sorting each filled data subset of unsorted data is performed using a quick-sort algorithm.

8. The method of claim 1, wherein the data incrementally received from the dataset is received from a storage medium.

9. The method of claim 1, wherein the data incrementally received from the dataset is received from a network file system.

10. A computer-readable storage medium storing computer-executable instructions that when executed by at least one processor cause the at least one processor to perform a method of sorting a dataset, the method comprising:

incrementally receiving data from the dataset;

sequentially generating a plurality of filled data subsets by incrementally storing the received data as individual input data subsets as the data is received;

sequentially generating a plurality of sorted input data subsets by individually sorting each filled data subsets concurrently with receiving data for a next one of the individual data subsets;

incrementally generating a sorted version of the dataset by performing a merge sort on the plurality of sorted input data subsets, wherein the sorted version of the dataset includes a plurality of sequentially generated sorted output data subsets; and

outputting each of the sorted output data subsets concurrently with generating a next one of the sorted output data subsets.

11. The computer-readable storage medium of claim 10, wherein the sorted output data subsets each have a same size as the individual input data subsets.

12. The computer-readable storage medium of claim 10, wherein the method further comprises:

varying a size of the individual input data subsets based on a size of the dataset.

13. The computer-readable storage medium of claim 10, wherein the individual input data subsets each have a size that is a predetermined fraction of a size of the dataset.

14. The computer-readable storage medium of claim 10, wherein the dataset is stored as a plurality of portions on a plurality of computing devices, and wherein the data from the dataset is incrementally received from the plurality of computing devices.

15. The computer-readable storage medium of claim 10, wherein the individually sorting each filled data subsets is performed using a quick-sort algorithm.

16. The computer-readable storage medium of claim 10, wherein the filled data subsets have a non-uniform size.

17. A method of sorting a dataset, comprising:

incrementally receiving data from the dataset;

sequentially generating a plurality of filled data subsets by incrementally storing the received data as individual input data subsets as the data is received;

sequentially generating a plurality of sorted input data subsets by individually sorting each filled data subset concurrently with receiving data for a subsequent one of the individual input data subsets;

incrementally generating a sorted version of the dataset by performing a merge sort on the plurality of sorted input data subsets, wherein the sorted version of the dataset includes a plurality of sequentially generated sorted output data subsets; and

outputting each of the sorted output data subsets concurrently with generating a subsequent one of the sorted output data subsets.