Coded data generation or conversion – Digital code to digital code converters – Adaptive coding
Reexamination Certificate
2006-07-18
2006-07-18
Jeanglaude, Jean Bruner (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Adaptive coding
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.
Shapira Dana
Storer James Andrew
LandOfFree
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.
Profile ID: LFUS-PAI-O-3585559