Systems and methods for managing duplication of operations

Patent metadata

Field	Value
Publication number	US-9563409-B2
Application number	US-201213668772-A
Country	US
Kind code	B2
Filing date	Nov 5, 2012
Priority date	Nov 5, 2012
Publication date	Feb 7, 2017
Grant date	Feb 7, 2017

Abstract

The present invention generally relates to systems and methods for executing scripts (a sequence of declarative operations) on large data sets. Some implementations store descriptions of previously-executed operations and associated input and output data sets. When executing similar operations on the same, a subset of, a superset of, or any fragment of data subsequently, some implementations detect duplication of operations and access previously-stored output data sets in order to re-use data and reduce the amount of execution, thus avoiding time-consuming duplicative computations.

First claim

What is claimed is:

1. A computer implemented method of executing a script comprising one or more operations, the method comprising:
parsing each of a plurality of operations into an operation name and an associated input data set description to obtain one or more parsed operation descriptions;
determining, using a selected parsed operation description corresponding to a selected operation, that the selected operation has previously been executed on an associated previous execution input data set, wherein the associated previous execution input data set is a proper subset of at least one associated input data set for the selected operation;
reducing the at least one associated input data set based on an overlap between the associated previous execution input data set and the at least one associated input data set, thereby producing a reduced input data set that includes a portion of the at least one associated input data set and excludes the overlap;
linking an output of the selected operation to a stored output of the selected operation previously executed on the associated previous execution input data set and an execution output of the selected operation executed on the reduced input data set, thereby producing a revised script; and
executing the revised script.

2. The method of claim 1 , wherein the determining comprises calculating a hash of the selected parsed operation description.

3. The method of claim 1 , wherein the determining comprises matching the selected parsed operation description to a stored parsed operation description.

4. The method of claim 1 , wherein the parsing comprises providing at least one associated input data set description that comprises a description of a decomposition of the at least one associated input data set.

5. The method of claim 4 , wherein the description of the at least one associated input data set comprises a description of the at least one associated input data set in entirety and a description of the proper subset of the at least one associated input data set.

6. The method of claim 5 , wherein the description of the at least one associated input data set further comprises a description of an elemental portion of the at least one associated input data set.

7. The method of claim 1 , further comprising logging at least one operation name of the selected operation, at least one associated input data set description for the selected operation, and at least one associated output data set description for the selected operation.

8. The method of claim 7 , wherein the at least one input data set description comprises a decomposition.

9. The method of claim 7 , wherein the at least one output data set description comprises a decomposition.

10. A system for executing a script comprising one or more operations, the system comprising:
a memory, storing a set of instructions; and
at least one processor that executes the stored set of instructions to:
parse each of a plurality of operations into an operation name and an associated input data set description to obtain one or more parsed operation descriptions;
determine, using a selected parsed operation description corresponding to a selected operation, that the selected operation has previously been executed on an associated previous execution input data set, wherein the associated previous execution input data set is a proper subset of at least one associated input data set for the selected operation;
reduce the at least one associated input data set based on an overlap between the associated previous execution input data set and the at least one associated input data set, thereby producing a reduced input data set that includes a portion of the at least one associated input data set and excludes the overlap;
link an output of the selected operation to a stored output of the selected operation previously executed on the associated previous execution input data set and an execution output of the selected operation executed on the reduced input data set, thereby producing a revised script; and
execute the revised script.

11. The system of claim 10 , wherein the at least one processor further calculates a hash of the selected parsed operation description.

12. The system of claim 10 , wherein the at least one processor further matches the selected parsed operation description to a stored parsed operation description.

13. The system of claim 10 , wherein the at least one processor further provides at least one associated input data set description that comprises a description of a decomposition of the at least one associated input data set.

14. The system of claim 13 , wherein the description of the at least one associated input data set comprises a description of the at least one associated input data set in entirety and a description of the proper subset of the at least one associated input data set.

15. The system of claim 14 , wherein the description of the at least one associated input data set further comprises a description of an elemental portion of the at least one associated input data set.

16. The system of claim 10 , wherein the at least one processor further logs at least one operation name of the selected operation, at least one associated input data set description for the selected operation, and at least one associated output data set description for the selected operation.

17. The system of claim 16 , wherein the at least one input data set description comprises a decomposition.

18. The system of claim 16 , wherein the at least one output data set description comprises a decomposition.

Assignees

• Xerox Corp

Inventors

• Kim Hyun Joo
• Quiroz Hernandez Andres

Classifications

• G06F17/30693

  Physics · mapped topic

• G06F8/36 Primary

  Software reuse · CPC title

• G06F16/24556 Primary

  Aggregation; Duplicate elimination · CPC title

• G06F16/3349

  Reuse of stored results of previous queries · CPC title