In-place differential compression

Coded data generation or conversion – Digital code to digital code converters – Adaptive coding

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C341S050000

Reexamination Certificate

active

07079051

ABSTRACT:
To enhance the distribution or backup of data similar to previously distributed or backed up data, to provide similarity testing, and other benefits, a first body of data T of size n is compressed with respect to a second body of data S of size m in-place; that is, the memory containing S is overwritten from left to right so that at no time is more than a total of MAX{m,n}+O(1) memory used.

REFERENCES:
patent: 4366551 (1982-12-01), Holtz
patent: 4558302 (1985-12-01), Welch
patent: 4646061 (1987-02-01), Bledsoe
patent: 4701745 (1987-10-01), Waterworth
patent: 4730348 (1988-03-01), MacCrisken
patent: 4814746 (1989-03-01), Miller et al.
patent: 4876541 (1989-10-01), Storer
patent: 4905297 (1990-02-01), Langdon et al.
patent: 4906991 (1990-03-01), Fiala et al.
patent: 5003307 (1991-03-01), George et al.
patent: 5016009 (1991-05-01), Whiting et al.
patent: 5126739 (1992-06-01), George et al.
patent: 5153591 (1992-10-01), Clark
patent: 5175543 (1992-12-01), Lantz
patent: 5179378 (1993-01-01), Ranganathan et al.
patent: 5253325 (1993-10-01), Clark
patent: 5379036 (1995-01-01), Storer
patent: 5406279 (1995-04-01), Anderson et al.
patent: 5479654 (1995-12-01), Squibb
patent: 5608396 (1997-03-01), Cheng et al.
patent: 5745906 (1998-04-01), Squibb
patent: 5813017 (1998-09-01), Morris
patent: 6018747 (2000-01-01), Burns et al.
patent: 6233589 (2001-05-01), Muralidhar
patent: 6374250 (2002-04-01), Ajtai et al.
patent: 6671703 (2003-12-01), Thompson et al.
Ajtai, Burns, Fagin, and Long. “Compactly Encoding Unstructured Inputs with Differential Compression”, J. of the ACM 49:3, 318-367. (U.S.), vol. 49, No. 3, May 2002.
Apostolico, Browne, and Guerra [1992]. “Fast Linear-Space Computations of Longest Common Subsequences”, Theoretical Computer Science, 92:1, 3-17 (U.S.), vol. 92, No. 1, Jan. 6, 1992.
Burns and Long [1997]. “A Linear Time, Constant Space Differencing Algorithm”, Proc. IEEE Int. Conf. on Perform., Comp., and Communications. (U.S.), Feb. 1997.
Burns and Long [1997b]. “Efficient Distributed Backup and Restore with Delta Compression”, Workshop on I/O in Parallel and Distributed Systems (IOPADS). (U.S.), no month.
Burns, Stockmeyer, and D. D. E. Long [2002]. “Experimentally Evaluating In-Place Delta Reconstruction”, NASA Conf. on Mass Storage Sys. and Tech.,(U.S.), no month.
Cormode, Paterson, Sahinalp and Vishkin [2000]. “Communication Complexity of Document Exchange”, Proc. 11th Symp. on Discrete Algorithms, 197-206. (U.S.), no month.
Factor, Sheinwald, and Yassour [2001]. “Software Compression in the Client/Server Environment”, Proc. Data Compression Conf., IEEE Comp. Society Press, 233-242. (U.S.), Mar. 27-29, 2001.
Fraser and Myers [1987]. “An Editor for Revision Control”, ACM Transactions on Programming Languages and Systems 9:2, 277-295. (U.S.), vol. 9 No. 2, Apr. 1997.
Hunt, Vo, and Tichy [1998]. “Delta algorithms: An Empirical Analysis”, ACM Trans. on Software Engineering and Methodology 7, 192-214. (U.S), vol. 2, No. 2, Apr. 1998.
Huffman [1952]. “A Method for the Construction of Minimum-Redundancy Codes”, Proceedings of the IRE 40, 1098-1101. (U.S.), Sep. 1952.
Lempel and Ziv [1976]. “On the Complexity of Finite Sequences”, IEEE Transactions on Information Theory 22:1, 75-81. (U.S.), no month.
Miller and Myers [1985]. “A File Comparison Program”, Software—Practice and Experience 15:11, 1025-1040. (U.S.), unknown month.
Rick [1995]. “A New Flexible Algorithm for the Longest Common Subsequence Problem”, Proc. 6th Annual Symposium on Combinatorial Pattern Matching, Espoo, Finland, 5-7. (U.S.), unknown month.
Shapira, and Storer [2002]. “Edit Distance with Move Operations”, Proceedings Conference of Combinatorial Pattern Matching (CPM) Springer, 85-98. (U.S.), unknown month.
Reichenberger [1991]. “Delta Storage for Arbitrary Non-Text Files”, Proc. 3rd Int. Workshop on Software Configuration Management, Trondheim, Norway, 12-14 (U.S.), unknown month.
Shapira, and Storer [2003]. “In-Place Differential File Compression”, Proc. 2003 Data Comp. Conf. (published Mar. 25, 2003), IEEE Comp. Soc. Press, 263-272. (U.S.).
Storer and T. G. Szymanski [1978]. “The Macro Model for Data Compression”, Proc. 10th Annual ACM Symposium of the Theory of Computing, San Diego, CA, 30-39. (U.S.), unknown month.
Storer and Szymanski [1982]. “Data Compression Via Textual Substitution”, Journal of the ACM 29:4, 928-951. (U.S.), unknown month.
Storer [1988]. Data Compression: Methods and Theory, Computer Science Press (a subsidiary of W. H. Freeman Press). (U.S.), unknown month.
Storer [2002]. “An Introduction to Data Structures and Algorithms”, Birkhauser—Springer. (U.S.), unknown month.
Tichy [1984]. “The String to String Correction Problem with Block Moves”, ACM Transactions on Computer Systems 2:4, 309-321. (U.S.), unknown month.
Wagner and Fischer [1973]. “The String-to-String Correction Problem”, Journal of the ACM 21:1, 168-173. (U.S.), unknown month.
Weiner [1973]. “Linear Pattern Matching Algorithms”, Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory 1-11. (U.S.), unknown month.
Ziv and Lempel [1977]. “A Universal Algorithm for Sequential Data Compression”, IEEE Transactions on Information Theory 23:3, 337-343. (U.S.), unknown month.
Ziv and Lempel [1978]. “Compression of Individual Sequences Via Variable-Rate Coding”, IEEE Transactions on Information Theory 24:5, 530-536. (U.S.), unknown month.
Burns and Long [1998]. “In-place Reconstruction of Delta Compressed Files”, Proc. ACM Conf. Principles of Distributed Comp. (PODC) (U.S.), no month.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

In-place differential compression does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with In-place differential compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and In-place differential compression will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3585559

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.