Data processing: database and file management or data structures – Data integrity – Fragmentation – compaction and compression
Reexamination Certificate
2011-04-12
2011-04-12
Corrielus, Jean M (Department: 2162)
Data processing: database and file management or data structures
Data integrity
Fragmentation, compaction and compression
C707S796000, C707S716000
Reexamination Certificate
active
07925639
ABSTRACT:
The present invention provides efficient window partitioning algorithms for entropy-encoding. The present invention enhances compression performance of entropy encoding based on the approach of modeling a dataset with the frequencies of its n-grams. The present invention may then employ approximation algorithms to compute good partitions in time O(s*log s) and O(s) respectively, for any data segment S with length s.
REFERENCES:
patent: 4333160 (1982-06-01), Kobari et al.
patent: 4823201 (1989-04-01), Simon et al.
patent: 5081675 (1992-01-01), Kittirutsunetorn
patent: 5251273 (1993-10-01), Betts et al.
patent: 5285276 (1994-02-01), Citta
patent: 5295159 (1994-03-01), Kerpez
patent: 5594435 (1997-01-01), Remillard
patent: 5806068 (1998-09-01), Shaw et al.
patent: 5838834 (1998-11-01), Saito
patent: 5870036 (1999-02-01), Franaszek et al.
patent: 5946692 (1999-08-01), Faloutsos et al.
patent: 6031671 (2000-02-01), Ayres
patent: 6122379 (2000-09-01), Barbir
patent: 6249902 (2001-06-01), Igusa et al.
patent: 6253165 (2001-06-01), Malvar
patent: 6256608 (2001-07-01), Malvar
patent: 6260033 (2001-07-01), Tatsuoka
patent: 6263444 (2001-07-01), Fujita
patent: 6301571 (2001-10-01), Tatsuoka
patent: 6351229 (2002-02-01), Wang
patent: 6381628 (2002-04-01), Hunt
patent: 6487535 (2002-11-01), Smyth et al.
patent: 6499137 (2002-12-01), Hunt
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: 7155657 (2006-12-01), Bordes et al.
patent: 7296030 (2007-11-01), Vo et al.
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/0167307 (2003-09-01), Filepp et al.
patent: 2003/0174897 (2003-09-01), Le Leannec et al.
patent: 2004/0015768 (2004-01-01), Bordes 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.
Edward Mingjun Yan—“Minimizing bandwidth requirement of broadcasting protocol in video-on-demand services”—Mar. 2002, (pp. 1-106).
Wang et al.—“Review of error resilient coding techniques for real-time video communications” IEEE signal processing 2000, (pp. 1-47).
Alajaji et al.—“An unequal error protection trellis coding scheme for still image communication”—Information theory, 1997, IEEE International symposium Jun. 29-Jul. 4, 1997 (p. 447, one page only).
Salvatore T. March - “Techniques for Structuring Database records” - Computer Science, vol. 15, No. 1, Mar. 1983 (pp. 45-79) (ACM Computing Surveys (CSUR).
David Andrew Douglas Tompkins -“Rate Control in Bi-Level Image Coding” - Aug. 2000, The university of Britsh Columbia (pp. 1-152).
Lekatsas et al. - “CoCo: A hardware/Software Platform for Rapid Prototyping of Code Compression technologies” - Proceedings of the 40thAnnual Design Automation Conference (ACM - IEEE) DAC 2003, Jun. 2-6, 2003 Anaheim, California, USA (pp. 306-311).
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, pp. 1-10.
Van Hoff et al., Generic Diff Format Specification, Aug. 25, 1997, W3C.org, pp. 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, pp. 1-10.
Vo et al., “Using Column Dependency to Compress Tables”, Mar. 23, 2004, Data Compression Conference 2004, IEEE Press, pp. 1-10.
Liefke et al., “XMill: an Efficient Compressor for XML Data”, May 14, 2000, Proc. of SIGMOD, ACM, pp. 1-12.
Burrows et al., “A Block-sorting Lossless Data Compression Algorithm”, May 10, 1994, Digital Systems Research Center, pp. 1-18.
Buchsbaum et al., “Improving Table Compression with Combinatorial Optimization”, Jan. 2002, Proc 13thACM-SIAM Symposium on Discrete Algorithms, pp. 1-10.
Hunt et al., “Delta Algorithms: An Empirical Analysis”, 1998, ACM Transactions on Software Engineering and Methodology, vol. 7, pp. 192-214.
Buchsbaum et al., Engineering the Compression of Massive Tables: An Experimental Approach, Jan. 9, 2000, Proc. 11thACM-SIAM Symp. of Discrete Algorithms, pp. 1-10.
Korn et al., “The VCDIFF Generic Differencing and Compression Data Format”, Jun. 2002, RFC 3284, Standards Track, pp. 1-29.
Xu et al., “A Brief Survey of Program Slicing”, Mar. 2004, ACM SIGSOFT Software Engineering Notes, vol. 30, No. 2, pp. 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, pp. 1-50.
Huffman, “A Method for the Construction of Minimum-Redundancy Codes”, Sep. 1952, Proceedings of the IRE, vol. 40, No. 9, pp. 1098-1101.
Fiala, et al., “Data Compression with Finite Windows”, Communications of ACM, vol. 32, issue 4, Apr. 1998, pp. 490-505.
Ajtai, et al., “Compacting Encoding Unstructured Inputs with Differential Compression”, May 2002, Journal of the ACM, vol. 49, No. 3, pp. 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, pp. 39-47.
Muthitacharoen, et al., “A Low-bandwidth Network File System”, ACM Symposium on Operating Systems SIGOPS, Oct. 2001, ACM Press, pp. 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, pp. 291-298.
Kukich, “Techniques for Automatically Correcting Words in Text”, Dec. 1992, ACM Computing Surveys, vol. 24, No. 4, pp. 377-439.
Vo Binh Dao
Vo Kiem-Phong
AT&T Intellectual Property II L.P.
Corrielus Jean M
Ly Anh
LandOfFree
Method and apparatus for windowing in entropy encoding 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 windowing in entropy encoding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for windowing in entropy encoding will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2703577