System and method for reducing the size of data difference representations

• US 7,028,251 B2
• Filed: 02/15/2001
• Issued: 04/11/2006
• Est. Priority Date: 03/02/2000
• Status: Expired due to Fees

• Current Assignee: iOra Software Limited
• Original Assignee: Iora Limited (Infonic Plc)
• Inventors: Draper, Stephen P. W.
• Primary Examiner(s): Shah, Sanjiv
• Application Number:
  US09/785,080
• Publication Number:
  US 20030004990A1
• Time in Patent Office: 1,881 Days
• Field of Search: 715/500.1, 715/511, 715/501.1, 715/500, 707/203, 709/219, 709/231
• US Class Current: 715/229
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/80 Responding to QoS

Abstract

An improved system and method for reducing the size of data difference representations. The input data stream may be split into one or more output data streams such that the output data streams may be recombined and used to regenerate the original input data stream. Each of the output data streams may be independently differenced against the equivalent data stream from the previous version of the data. Non-localized changes in the input data stream may be converted into localized changes in a subset of the output data streams. The subset of output data streams no longer containing non-localized changes produce efficient (i.e., small) difference representations. The difference representations of each of these streams may be packaged into a single stream for transmission over a computer network. The receiving computer may reconstruct the multiplicity of difference representations, and recreate the multiplicity of translated data streams representing the updated data.

Claims

1. A method of reducing a size of data difference representations, the method comprising:

identifying an original version of an input data stream in an original form;

dividing the original form of the original version of the input data stream into separate original version output data streams through the use of a pre-processor;

identifying an updated version of the input data stream in the original form;

dividing the original form of the updated version of the input data stream into separate updated version output data streams through the use of the pre-processor; and

differencing at least two of the separate updated version output data streams with a corresponding separate original version output data stream to produce data difference representations.

2. The method of claim 1, wherein the data difference representations are smaller than a data difference representation created by differencing the original form of the updated version of the input data stream with the original form of the original input data stream.

3. The method of claim 1, further comprising:

reconstructing the separate updated version output data streams from the data difference representations and the original version output data streams; and

combining the separate updated version output data streams into the original form of the updated version of the input data stream through the use of a post-processor.

4. The method of claim 1 wherein the original form of the original version of the input data stream is empty.

5. The method of claim 1 wherein the pre-processor comprises decompression algorithms.

6. The method of claim 1 wherein the dividing separates volatile components of the input data stream from less volatile components of the input data stream.

7. The method of claim 6 wherein the input data stream is executable code.

8. The method of claim 7 wherein the volatile components comprise branch targets.

9. The method of claim 7 wherein the volatile components comprise data addresses.

10. The method of claim 7 wherein the less volatile components comprise instruction code.

11. The method of claim 7 wherein the less volatile components comprise immediate data.

12. The method of claim 6, wherein the volatile components are substantially dynamically changing components and wherein the less volatile components are substantially static components.

13. The method of claim 1, further comprising:

packaging the data difference representations into a single data stream;

compressing the single data stream; and

storing the single data stream.

14. The method of claim 13, further comprising:

transmitting the single data stream;

uncompressing the single data stream; and

unpackaging the single data stream into the data difference representations.

15. The method of claim 1, wherein dividing the original form of the updated version of the input data stream into separate updated version output data streams includes parsing the input data stream according to a data type of the input data stream.

16. The method of claim 1, wherein differencing at least two of the separate updated version output data streams with a corresponding separate original version output data stream to produce data difference representations comprises differencing each of the separate updated version output data streams with a corresponding separate original version output data stream to produce data difference representations.

17. The method of claim 1,

wherein the dividing separates first components of the input data stream from second components of the input data stream, and

wherein the first components are components of the input data stream that are statistically more likely to have changed between the original version of the input data stream and the updated version of the input data stream than the second components.

18. The method of claim 17, wherein a pattern template is used to separate the first components and the second components.

19. A system of reducing a size of data difference representations, the system compnsing:

a network;

a first computer system coupled to the network;

a system memory coupled to the first computer system, wherein the system memory stores one or more computer programs executable by the first computer system;

wherein the computer programs are executable to;

identify an original version of an input data stream in an original form;

divide the original form of the original version of the input data stream into separate original version output data streams through the use of a pre-processor;

identify an updated version of the input data stream in the original form;

divide the original form of the updated version of the input data stream into separate updated version output data streams through the use of the pre-processor; and

difference at least two of the separate updated version output data streams with a corresponding separate original version output data stream to produce data difference representations.

20. The system of claim 19, wherein the data difference representations are smaller than a data difference representation created by differencing the original form of the updated version of the input data stream with the original form of the original input data stream.

21. The system of claim 19, further comprising:

a second computer system coupled to the network;

a system memory coupled to the second computer system, wherein the system memory stores one or more computer programs executable by the second computer system;

wherein the pre-processor is located in the first computer system; and

wherein the post-processor is located in the second computer system.

22. The system of claim 21, wherein the computer programs are further executable to:

reconstruct the separate updated version output data streams from the data difference representations and the original version output data streams; and

combine the separate updated version output data streams into the original form of the updated version of the input data stream through the use of a post-processor.

23. The system of claim 21 wherein the original form of the original version of the input data stream is empty.

24. The system of claim 21 wherein the pre-processor comprises decompression algonthms.

25. The system of claim 21 wherein the dividing separates volatile components of the input data stream from less volatile components of the input data stream.

26. The system of claim 25 wherein the input data stream is executable code.

27. The system of claim 26 wherein the volatile components comprise branch targets.

28. The system of claim 26 wherein the volatile components comprise data addresses.

29. The system of claim 26 wherein the less volatile components comprise instruction code.

30. The system of claim 26 wherein the less volatile components comprise immediate data.

31. The system of claim 21, wherein the computer programs are further executable to:

package the data difference representations into a single data stream;

compress the single data stream; and

store the single data stream on a memory medium coupled to the first computer system.

32. The system of claim 31, wherein the computer programs are further executable to:

transmit the single data stream from the memory medium coupled to the first computer system to a second computer system over a computer system network;

uncompress the single data stream; and

unpackage the single data stream into the data difference representations.

33. The system of claim 19, wherein dividing the original form of the updated version of the input data stream into separate updated version output data streams includes parsing the input data stream according to a data type of the input data stream.

34. A carrier medium which stores program instructions, wherein the program instructions are executable to implement reducing a size of data difference representations comprising:

identifying an original version of an input data stream in an original form;

dividing the original form of the original version of the input data stream into separate original version output data streams through the use of a pre-processor;

identifying an updated version of the input data stream in the original form;

dividing the original form of the updated version of the input data stream into separate updated version output data streams through the use of the pre-processor; and

differencing at least two of the separate updated version output data streams with a corresponding separate original version output data stream to produce data difference representations.

35. The carrier medium of claim 34, wherein the data difference representations are smaller than a data difference representation created by differencing the original form of the updated version of the input data stream with the original form of the original input data stream.

36. The carrier medium of claim 34, wherein the program instructions are further executable to implement:

reconstructing the separate updated version output data streams from the data difference representations and the original version output data streams; and

combining the separate updated version output data streams into the original form of the updated version of the input data stream through the use of a post-processor.

37. The carrier medium of claim 34 wherein the original form of the original version of the input data stream is empty.

38. The carrier medium of claim 34 wherein the pre-processor comprises decompression algorithms.

39. The carrier medium of claim 34 wherein the dividing separates volatile components of the input data stream from less volatile components of the input data stream.

40. The carrier medium of claim 39 wherein the input data stream is executable code.

41. The carrier medium of claim 40 wherein the volatile components comprise branch targets.

42. The carrier medium of claim 40 wherein the volatile components comprise data addresses.

43. The carrier medium of claim 40 wherein the less volatile components comprise instruction code.

44. The carrier medium of claim 40 wherein the less volatile components comprise immediate data.

45. The carrier medium of claim 34, wherein the program instructions are further executable to implement:

packaging the data difference representations into a single data stream;

compressing the single data stream; and

storing the single data stream on a memory medium coupled to a first computer system.

46. The carrier medium of claim 45, wherein the program instructions are further executable to implement:

transmitting the single data stream from the memory medium coupled to the first computer system to a second computer system over a computer system network;

uncompressing the single data stream; and

unpackaging the single data stream into the data difference representations.

47. The carrier medium of claim 34, wherein the carrier medium is a memory medium.

48. The carrier medium of claim 34, wherein dividing the original form of the updated version of the input data stream into separate updated version output data streams includes parsing the input data stream according to a data type of the input data stream.