OPTIMIZATION OF NON-DETERMINISTIC COMPUTATIONAL PATHS

• US 20120284315A1
• Filed: 05/04/2011
• Published: 11/08/2012
• Est. Priority Date: 05/04/2011
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: WANG, ZHENGHAO, YAN, AN, YAN, SHENGQUAN, LARSSON, JEFFREY ERIC, ZHENG, ZIJIAN
• Application Number:
  US13/100,459
• Publication Number:
  US 20120284315A1
• Time in Patent Office: Days
• US Class Current: 707/822
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

Methods, computer systems and computer readable media for optimizing non-deterministic computational paths are provided. In embodiments, requests are received to generate reports derived from a plurality of series of data files whose metadata attributes form certain mathematical structures that can be used to choose the optimal path in the non-deterministic dependency model. Storage for each of the series of data files is optimized. Available data files needed for the report are processed and missing data files are identified. Based on the mathematical structure of the plurality of series of data files, an optimal transition with the missing data files available is determined. An entry into the transition is triggered and the missing data files are processed. The report is generated and the optimized storage is retained for future requests.

Claims

1. A method for optimizing a non-deterministic computational path, the method comprising:

(a) receiving a request to generate a report;

(b) extracting features and a date range from the request;

(c) merging data files for each extracted feature to satisfy the requested date range to form a series of data files;

(d) merging a plurality of series of data files to form a semi-lattice structure;

(e) identifying an available data file necessary for the report;

(f) identifying a subsuming data file that subsumes the available data file;

(g) removing the available data file from processing;

(h) issuing a transition into the subsuming data file;

(i) repeating steps (d)-(h) until the structure has been reduced;

(j) processing subsuming data files needed for the report;

(k) identifying missing data files needed to complete the report;

(l) calculating the supremum of all missing data files;

(m) identifying a solved series of data files with a partial order relation with the supremum of all missing data files;

(n) issuing a transition into the solved series of data files;

(o) triggering an entry into the transition;

(p) processing the missing data files associated with the transition;

(q) repeating steps (k)-(p) until all missing data files have been processed; and

(r) generating the report.

2. The media of claim 1, further comprising traversing the semi-lattice structure from the bottom up.

3. The media of claim 1, further comprising retaining the optimized storage for future requests.

4. The media of claim 1, wherein the report includes data associated with each of the extracted features for the requested date range.

5. Computer-storage media storing computer-usable instructions, that, when executed by a computing device, perform a method for optimizing a non-deterministic computational path, the method comprising:

receiving a request to generate a report derived from a plurality of series of data files stored in a mathematical structure;

optimizing storage for each of the series of data files;

processing available data files needed for the report;

identifying missing data files needed to complete the report;

based on the mathematical structure, determining a transition with the missing data files available;

triggering an entry into the transition;

processing the missing data files associated with the transition; and

generating the report.

6. The media of claim 5, further comprising traversing the mathematical structure from the bottom up.

7. The media of claim 5, further comprising retaining the optimized storage for future requests.

8. The media of claim 5, further comprising extracting features from the request.

9. The media of claim 5, wherein the request includes a date range.

10. The media of claim 9, further comprising merging data files for each extracted feature to satisfy the requested date range to form a series of data files.

11. The media of claim 10, further comprising merging a plurality of series of data files to form the mathematical structure.

12. The media of claim 6, wherein the mathematical structure is a semi-lattice.

13. The media of claim 5, wherein optimizing storage comprises:

identifying each available data file;

identifying a subsuming data file that subsumes the available data file;

removing the available data file from processing; and

issuing a transition into the subsuming data file.

14. The media of claim 5, wherein determining a transition with the missing data files available comprises:

calculating the supremum of all missing data files;

identifying a solved series of data files with a partial order relation with the supremum of all missing data files; and

issuing a transition into the solved series of data files.

15. The media of claim 9, wherein the report includes each of the extracted features for the requested date range.

16. A computer system for optimizing a non-deterministic computational path, the computer system comprising a processor coupled to a computer-storage medium, the computer-storage medium having stored thereon a plurality of computer software components executable by the processor, the computer software components comprising:

a receiving component for receiving a request to generate a report derived from a plurality of series of data files stored in a mathematical structure;

a reduce component for optimizing storage for each of the series of data files;

a solve component for locating and processing missing data files needed to complete the report; and

a report component for generating the report after the solve component has located and processed all missing data files.

17. The computer system of claim 16, further comprising an extraction component for extracting features from the request.

18. The computer system of claim 16, further comprising a data file merge component for merging data files for each extracted feature to satisfy the requested date range to form a series of data files.

19. The computer system of claim 16, further comprising a series merge component for merging a plurality of series of data files to form a semi-lattice structure.

20. The computer system of claim 16, further comprising a retention component for retaining the optimized storage for future requests.