Method and apparatus for window matching in delta compressors

Details Method and apparatus for window matching in delta compressors Method and apparatus for window matching in delta compressors

2004-07-19

2008-11-18

Alam, Hosain T (Department: 2166)

Data processing: database and file management or data structures

Database design

Data structure types

C341S076000, C341S143000, C707S793000, C707S793000

Reexamination Certificate

active

07454431

ABSTRACT:
The present invention significantly improves the performance of matching target file window partitions to source file window partitions in delta compression. In particular, the present invention enhances delta compression performance of delta compressors based on the idea of modeling a dataset with the frequencies of its n-grams and employs a method to compute good source and target window matching in linear time.

REFERENCES:
patent: 4823201 (1989-04-01), Simon et al.
patent: 5285276 (1994-02-01), Citta
patent: 5806068 (1998-09-01), Shaw et al.
patent: 5838834 (1998-11-01), Saito
patent: 5946692 (1999-08-01), Faloutsos et al.
patent: 6031671 (2000-02-01), Ayres
patent: 6263444 (2001-07-01), Fujita
patent: 6351229 (2002-02-01), Wang
patent: 6487535 (2002-11-01), Smyth et al.
patent: 6653954 (2003-11-01), Rijavec
patent: 6667700 (2003-12-01), McCanne et al.
patent: 6959300 (2005-10-01), Caldwell et al.
patent: 7017043 (2006-03-01), Potkonjak
patent: 7031972 (2006-04-01), Ren et al.
patent: 7043077 (2006-05-01), Rijavec
patent: 7072889 (2006-07-01), Ogawa
patent: 7096311 (2006-08-01), Chiang
patent: 2001/0004739 (2001-06-01), Sekiguchi et al.
patent: 2002/0010702 (2002-01-01), Ajtai et al.
patent: 2002/0169784 (2002-11-01), Cha et al.
patent: 2003/0009596 (2003-01-01), Tonomura
patent: 2003/0055833 (2003-03-01), Chan et al.
patent: 2003/0115041 (2003-06-01), Chen et al.
patent: 2003/0138045 (2003-07-01), Murdock et al.
patent: 2003/0140337 (2003-07-01), Aubury
patent: 2003/0174897 (2003-09-01), Le Leannec et al.
patent: 2004/0039839 (2004-02-01), Kalyanaraman et al.
patent: 2004/0062130 (2004-04-01), Chiang
patent: 2004/0190635 (2004-09-01), Ruehle
patent: 2004/0221192 (2004-11-01), Motta et al.
patent: 2005/0198056 (2005-09-01), Dumais et al.
patent: 2005/0210056 (2005-09-01), Pomerantz et al.
Ajtai, et al., “Compacting Encoding Unstructured Inputs with Differential Compression”, May 2002, Journal of the ACM, vol. 49, No. 3, p. 318-327, 330-331, 337, 362-363.
Klein, “Efficient Recompression Techniques for Dynamic Full-Text Retrieval Systems”, Jul. 13, 1995, Proceedings of SIGIR'95, ACM Press, p. 39-47.
Muthitacharoen et al., “A Low-bandwidth Network File System”, ACM Symposium on Operating Systems SIGOPS, Oct. 2001, ACM Press, p. 174-187.
Fukumoto et al., “An Automatic Extraction of Key Paragraphs Based on Context Dependency”, Mar. 1997, Proceedings of the Fifth Conference on Applied Natural Language Processing, Morgan Kaufmann Publishers, p. 291-298.
Kukich, “Techniques for Automatically Correcting Words in Text”, Dec. 1992, ACM Computing Surveys, vol. 24, No. 4, p. 377-439.
Shapira et al, “In-Place Differential File Compression of Non-Aligned Files With Applications to File Distribution, Backups, and String Similarity”, Mar. 23, 2004, Data Compression Conference 2004, IEEE Press, p. 1-10.
van Hoff et al, “Generic Diff Format Specification”, Aug. 25, 1997, W3C.org, p. 1-4. <http://www.w3.org/TR/NOTE-gdiff-19970825.html>.
Korn et al, “Engineering a Differencing and Compression Data Format”, Nov. 3, 2002, USENIX Conference, ACM, p. 1-10.
Vo et al, “Using Column Dependency to Compress Tables”, Mar. 23, 2040, Data Compression Conference 2004, IEEE Press, p. 1-10.
Liefke et al, “XMill: an Efficient Compressor for XML Data”, May 14, 2000, Proc. of SIGMOD, ACM, p. 1-12.
Burrows et al, “A Block-sorting Lossless Data Compression Algorithm”, May 10, 1994, Digital Systems Research Center, p. 1-18.
Buchsbaum et al, “Improving Table Compression with Combinatorial Optimization”, Jan. 2002, Proc 13th ACM-SIAM Symposium on Discrete Algorithms, p. 1-10.
Hunt et al, “Delta Algorithms: An Empirical Analysis”, 1998, ACM Transactions on Software Engineering and Methodology, vol. 7, p. 192-214.
Buchsbaum et al, “Engineering the Compression of Massive Tables: An Experimental Approach”, Jan. 9, 2000, Proc. 11th ACM-SIAM Symp. of Discrete Algorithms, p. 1-10.
Korn et al, “The VCDIFF Generic Differencing and Compression Data Format”, Jun. 2002, RFC 3284, Standards Track, p. 1-29.
Xu et al, “A Brief Survey of Program Sliciing”, Mar. 2004, ACM SIGSOFT Software Engineering Notes, vol. 30, No. 2, p. 1-36.
Mogul et al, “Potential benefits of delta encoding and data compression for HTTP (Corrected Version)”, Dec. 1997, WRL Research Report 97/4a, Digital Western Research Laboratory,p. 1-50.
Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Sep. 1952, Proceedings of the IRE, vol. 40, No. 9, p. 1098-1101.
Fiala, et al., “Data Compression with Finite Windows”, Communications of ACM, vol. 32, issue 4, Apr. 1998, pp. 490-505.

Affiliated with

Also associated with

Rating

Method and apparatus for window matching in delta compressors does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Method and apparatus for window matching in delta compressors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for window matching in delta compressors will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4051239