Systems and methods for processing changing data

• US 20060282474A1
• Filed: 01/18/2006
• Published: 12/14/2006
• Est. Priority Date: 01/18/2005
• Status: Abandoned Application

• Current Assignee: Everypoint, Inc.
• Original Assignee: Everypoint, Inc.
• Inventors: MacKinnon, Allan Stuart Jr.
• Application Number:
  US11/334,036
• Publication Number:
  US 20060282474A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/202 where processing functionality is redundant redundant communication control functionality G06F11/2005, redundant storage control functionality G06F11/2089
• CPC Class Codes: G06F 11/2051 in regular structures
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 9/4494 data driven
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Systems and methods for data processing using incremental algorithms. Embodiments of the invention decompose complex or monolithic data processing problems into one or more incremental computations called flows. These flows may be distributed across a networked cluster of commodity computers, facilitating the easy scaling of the system and robust recovery functionality. Once a request is submitted to the system, its solution may be maintained from that point in time forward, such that whenever changes are made to a problem'"'"'s data the solution is efficiently recomputed.

Claims

1. A method for data processing, the method comprising:

receiving a request for execution against a data set;

decomposing the request into at least one incremental computation; and

in response to a change in the data set, executing the at least one incremental computation against the change in the data set.

2. The method of claim 1 further comprising executing the at least one incremental computation against the data set.

3. The method of claim 2 further comprising storing the result of executing the at least one incremental computation against the data set.

4. The method of claim 1 further comprising storing the result of executing the at least one incremental computation against the change in the data set.

5. The method of claim 1 further comprising assigning at least one of the at least one incremental computation to a computing resource for execution.

6. The method of claim 5 wherein the computing resource is a server computer.

7. The method of claim 5 wherein the computing resource is a core in a multicore processor.

8. The method of claim 1 further comprising replicating an assigned incremental computation to a second computing resource for execution.

9. The method of claim 8 further comprising synchronizing the replicated incremental computation with the original incremental computation.

10. The method of claim 9 further comprising establishing communications between the replicated incremental computation and the original incremental computation.

11. The method of claim 8 further comprising establishing communications with the replicated incremental computation in response to a loss of communications with the original incremental computation.

12. The method of claim 1 wherein the change in the data set is selected from the group consisting of an insertion, an update, or a deletion.

13. The method of claim 1 further comprising updating an indicator value upon completion of execution of the incremental computation.

14. The method of claim 1 further comprising:

receiving a request for a transaction history including an indicator value;

constructing a response to the request indicating the difference between the current state of the incremental computation and the state of the incremental computation associated with the indicator value.

15. A method for data processing, the method comprising:

receiving a request for execution against a data set;

decomposing the request into at least two incremental computations;

configuring the first incremental computation to receive an input selected from the group consisting of the data set and a second incremental computation; and

in response to a change in the input, executing the first incremental computation against the change in the input.

16. The method of claim 15 further comprising providing the result of the execution as an output of the first incremental computation.

17. The method of claim 16 further comprising providing an abort message as an output of the first incremental computation if the execution against the change in the input is aborted.

18. The method of claim 15 further comprising setting the state of the first incremental computation using a transmitted state from the second incremental computation.

19. The method of claim 15 further comprising storing the state of the first incremental computation prior to executing the first incremental computation against the change in the input.

20. The method of claim 19 further comprising restoring the stored state of the first incremental computation if the execution against the change in the input is aborted.

21. The method of claim 15 wherein the change in the input is selected from the group consisting of an insertion, an update, or a deletion.

26. The memory of claim 21, the instructions further comprising instructions for initializing the incremental computation using the state of another incremental computation.

27. The memory of claim 21, the instructions further comprising instructions for reverting the state of the incremental computation to an earlier stored state.

28. The memory of claim 21, the instructions further comprising instructions for transmitting the current state of the incremental computation across a communication channel.

29. The memory of claim 21, the instructions further comprising instructions for synchronizing the current state of the incremental computation with the state of another incremental computation.

22. A computer-readable memory comprising machine-executable instructions, the machine-executable instructions comprising:

instructions for receiving a request for execution against a data set;

instructions for decomposing the request into at least one incremental computation; and

instructions for executing the at least one incremental computation against a change in the data set in response to the change in the data set.

23. The memory of claim 22, the instructions further comprising instructions for providing the current state of the incremental computation.

24. The memory of claim 23, the instructions further comprising instructions for storing the current state of the incremental computation.

25. The memory of claim 24, wherein the instructions for storing the current state of the incremental computation utilize a partially-persistent data structure.