Efficient optimization over uncertain data

• US 8,650,180 B2
• Filed: 06/20/2011
• Issued: 02/11/2014
• Est. Priority Date: 06/20/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nath, Suman K., Lee, Seung Ho, Smyl, Slawomir, Loboz, Charles Z., Kennedy, Oliver Andrzej
• Primary Examiner(s): Jami, Hares
• Application Number:
  US13/164,573
• Publication Number:
  US 20120323926A1
• Time in Patent Office: 967 Days
• Field of Search: 707/713, 707/736, 707/758, 707/769, 703/22
• US Class Current: 707/713
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06F 30/20 Design optimisation, verification or simulation optimisation, verification or simulation of circuit designs G06F30/30
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

The subject disclosure is directed towards using fingerprints, comprising lists of simulation results corresponding to partial (random sampled) simulation results, to determine whether a full simulation may be avoided by reusing simulation results from a previous full simulation. Before running a full simulation, a current fingerprint is obtained via a partial simulation. If a previous fingerprint matches (is identical or similar to) the current fingerprint, the associated previous results are reused. Also described is indexing fingerprint data to facilitate efficient lookup-based fingerprint matching.

Claims

1. In a computing environment, a computer-implemented method performed at least in part on at least one processor, comprising, obtaining a current fingerprint representative of a current parameter combination for use in an uncertain data simulation, determining whether a previous fingerprint was obtained that matches the current fingerprint, and if so, reusing simulation results associated with the fingerprint that matches to provide simulation results for the current parameter combination, and if not, running a simulation using the current parameter combination to obtain the simulation results for the current parameter combination.

2. The computer-implemented method of claim 1 wherein obtaining the current fingerprint representative of the current parameter combination comprises running a partial simulation using the current parameter combination to obtain partial results, and using the partial results in the current fingerprint.

3. The computer-implemented method of claim 2 further comprising selecting a set of random tables for running the partial simulation to obtain the partial results, in which the random tables correspond to random tables selected for obtaining each previous fingerprint.

4. The computer-implemented method of claim 1 wherein a similar fingerprint does not exist, and further comprising, maintaining data representative of the current fingerprint in association with the simulation results for the current parameter combination.

5. The computer-implemented method of claim 1 wherein determining whether a previous fingerprint exists that matches the current fingerprint comprises determining that a fingerprint that matches is similar to the current fingerprint by way of having a mathematical relationship with the current fingerprint.

6. The computer-implemented method of claim 5 wherein reusing the simulation results associated with the similar fingerprint to provide simulation results for the current parameter combination comprises adjusting the simulation results for the current parameter based upon the mathematical relationship.

7. The computer-implemented method of claim 1 wherein determining whether a previous fingerprint exists that matches the current fingerprint comprises determining that a fingerprint that matches is similar to the current fingerprint by way of having a linear relationship with the current fingerprint.

8. The computer-implemented method of claim 1 wherein determining whether a previous fingerprint exists that matches the current fingerprint comprises maintaining the previous fingerprint as a normalized representation of the previous fingerprint, normalizing the current fingerprint into a normalized representation of the current fingerprint, and determining whether the normalized representation of the previous fingerprint matches the normalized representation of the current fingerprint.

9. The computer-implemented method of claim 1 wherein reusing the simulation results associated with the fingerprint that matches to provide simulation results for the current parameter combination comprises adjusting the simulation results for the current parameter to account for the normalizing.

10. The computer-implemented method of claim 1 further comprising, maintaining an index representative of a set of previously obtained fingerprints.

11. The computer-implemented method of claim 10 wherein maintaining the index comprises maintaining normalized representations of at least some of the previously obtained fingerprints.

12. The computer-implemented method of claim 10 wherein maintaining the index comprises determining an identifier representative of a fingerprint based upon sorting results in the fingerprint, and using position information of the results in the identifier.

13. The computer-implemented method of claim 12 wherein determining whether a previous fingerprint exists that is similar or identical to the current fingerprint comprises determining an identifier representative of the current fingerprint based upon sorting results in the current fingerprint, using the identifier to retrieve candidate fingerprints from the index, and determining whether a candidate fingerprint is similar or identical to the current fingerprint.

14. In a computing environment, a system comprising:

a memory coupled to a bus system, wherein the memory comprises computer useable program code;

one or more processing units, wherein the one or more processing units execute the computer useable program code to provide for;

a probabilistic database system analysis tool, the probabilistic database system analysis tool configured to process data maintained in probabilistic database tables, the probabilistic database system analysis tool coupled to a fingerprint mechanism, and the fingerprint mechanism configured to maintain fingerprint data representative of subsets of probabilistic database table processing operations, wherein the probabilistic database system analysis tool is configured to obtain a current fingerprint representative of a current parameter combination for use in an uncertain data simulation, to determine whether a previous fingerprint was obtained that matches the current fingerprint, and if so, to reuse simulation results associated with the fingerprint that matches to provide simulation results for the for the current parameter combination, and if not, to run a simulation using the current parameter combination to obtain the simulation results for the current parameter combination.

15. The system of claim 14 wherein the subsets of table processing operations comprise simulations for different parameter combinations.

16. The system of claim 14 wherein the subsets of table processing operations correspond to inter-model dependency processing.

17. The system of claim 14 wherein the subsets of table processing operations correspond to refinement, validation, or exploration processing tasks.

18. One or more computer hardware storage devices having computer-executable instructions, which when executed perform steps, comprising:

running a simulation using a parameter combination to obtain simulation results;

obtaining a fingerprint representative of part of the simulation results;

maintaining fingerprint data corresponding to the fingerprint in association with the simulation results;

obtaining a current fingerprint representative of part of partial simulation results for another parameter combination;

determining from the fingerprint data whether the current fingerprint matches a fingerprint for which simulation results were obtained, and if so, using the simulation results associated with the identical or similar fingerprint to provide simulation results for the current fingerprint.

19. The one or more computer hardware storage devices of claim 18 wherein maintaining the fingerprint data comprises maintaining an index by which data corresponding to the current fingerprint is used to look for a fingerprint that matches.

20. The one or more computer hardware storage devices of claim 18 wherein the current fingerprint matches a fingerprint for which simulation results were obtained by being similar thereto, and wherein using the simulation results associated with the fingerprint that matches to provide simulation results for the current fingerprint comprises adjusting the simulation results based upon a similarity relationship between the current fingerprint and the fingerprint that matches.