(12)
`
`United States Patent
`Fallon
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,161,506 B2
`*Jan. 9, 2007
`
`US007161506B2
`
`(54) SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`(75) Inventor: James J. Fallon, Armonk, NY (US)
`
`(73) Assignee: Realtime Data LLC, New York, NY
`(Us)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`
`3/1986 Dang et a1.
`4,574,351 A
`6/1986 Ohkubo et a1.
`4,593,324 A
`7/1987 Mathes et a1.
`4,682,150 A
`3/1988 MacCrisken
`4,730,348 A
`2/1989 Makansi et a1~
`4,804,959 A
`9/1989 Van Maren et a1.
`4,870,415 A
`4,872,009 A 10/1989 Tsukiyama et a1~
`4,876,541 A 10/1989 Storer
`4,888,812 A 12/1989 Dinan et a1.
`4,906,995 A
`3/1990 Swanson
`
`This patent is subject to a terminal dis-
`
`FOREIGN PATENT DOCUMENTS
`
`Clalmer'
`
`DE
`
`4127518
`
`2/1992
`
`(Continued)
`OTHER PUBLICATIONS
`
`(21) Appl. No.: 10/668,768
`
`(22) Filed:
`
`Sep. 22, 2003
`
`(65)
`
`Prior Publication Data
`Us 2004/0056783 A1
`Man 25, 2004
`
`Jack VenbruX, A VLSI Chip Set for High-Speed Lossless Data
`gorgpreission , lIE2ElIE\ITrA2‘1nsj OnlgCgigcuits
`3S9§istem for Video
`
`ec n0 ogy, v0. ,
`
`0.
`
`,
`
`ec.
`
`,PP~
`
`-
`
`.
`
`Related US. Application Data
`
`(Continued)
`
`(63) Continuation of application No. 10/016,355, ?led on
`Oct. 29, 2001, HOW Pat. NO. 6,624,761, which is a
`.
`.
`.
`.
`.
`contlnuatlon-m-part of appl1cat1on No. 09/705,446,
`?led 011 Nov. 3, 2000, HOW Pat. NO. 6,309,424, which
`is a continuation of application No. 09/210,491, ?led
`on Dec. 11, 1998, noW Pat. No. 6,195,024.
`
`(51) Int_ CL
`(200601)
`H03M 7/34
`(52) US. Cl. ......................................... .. 341/51- 341/79
`(58) Field of Classi?cation Search ................ .. 341/50,
`34161 67 79 75
`See application ?le for Complete Search h’isto’ry ’
`'
`
`(56)
`
`References Cited
`
`US. PATENT DOCUMENTS
`
`4,127,518 A 11/1978 Coy et a1.
`4,302,775 A 11/1981 Widergren et 31.
`4,394,774 A
`7/1983 Widergren et a1.
`
`. i .
`.
`Pnmary Examm” Lmh .NguYeI:
`(74) Attorney, Agent, or FzrmiFlsh & Neave 1P Group of
`R0 es & Gm LLP
`p
`y
`(57)
`
`ABSTRACT
`
`Systems and methods for providing fast and e?‘icient data
`compression using a combination of content independent
`data Compression and Content dependent data Compression
`In one aspect’ a method for Compressing data comprises the
`steps of: analyZmg a data block of an lnput data stream to
`identify a data type of the data block, the input data stream
`comprising a plurality of disparate data types; performing
`content dependent data compression on the data block, if the
`data type of the data block is identi?ed; performing content
`independent data compression on the data block, if the data
`type of the data block is not identi?ed.
`
`99 Claims, 34 Drawing Sheets
`
`RAYIO 0F n LEAST cNz
`ENCGDED mm smcx
`
`SELECT EucooEn
`mu BLOCK WITH
`GREATEST
`coMPREssloN RATIO
`
`:22
`
`APPE DNULL
`DESCRIF'IOR TO
`uNEucoDED mpur
`mu BLOCK
`
`m
`
`cnRREsPoNDlNG
`nEscRvPTo
`
`OUTPUT ENCODED
`mu awcx wrm
`nsscwma
`
`25
`
`OUTPUT u ENODDED
`DATA BLOCK WITH
`NULL DEscFuPl‘oR
`
`32°
`
`3:2
`
`YES
`
`\‘ERMWATE um
`COMPRESSION
`PRocsss
`
`RECEYVE NEXT DATA m
`BLOCK FROM 1mm
`STREAM
`
`B
`
`Teradata, Exh. 1001, p. 1 of 58
`
`

`

`US 7,161,506 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`4,929,946
`4,965,675
`5,028,922
`5,045,848
`5,045,852
`5,046,027
`5,049,881
`5,097,261
`5,113,522
`5,121,342
`5,150,430
`5,159,336
`5,175,543
`5,179,651
`5,187,793
`5,191,431
`5,204,756
`5,209,220
`5,212,742
`5,226,176
`5,227,893
`5,231,492
`5,237,460
`5,237,675
`5,243,341
`5,243,348
`5,247,638
`5,247,646
`5,263,168
`5,270,832
`5,287,420
`5,293,379
`5,307,497
`5,309,555
`5,355,498
`5,357,614
`5,379,036
`5,379,757
`5,381,145
`5,394,534
`5,396,228
`5,400,401
`5,403,639
`5,406,278
`5,406,279
`5,412,384
`5,414,850
`5,420,639
`5,452,287
`5,461,679
`5,467,087
`5,471,206
`5,479,587
`5,486,826
`5,495,244
`5,506,844
`5,506,872
`5,530,845
`5,533,051
`5,535,356
`5,537,658
`5,557,551
`5,557,668
`5,557,749
`5,561,824
`5,574,952
`5,574,953
`5,583,500
`5,590,306
`5,596,674
`5,604,824
`
`5/1990
`10/1990
`7/1991
`9/1991
`9/1991
`9/1991
`9/1991
`3/1992
`5/1992
`6/1992
`9/1992
`10/1992
`12/1992
`1/1993
`2/1993
`3/1993
`4/1993
`5/1993
`5/1993
`7/1993
`7/1993
`7/1993
`8/1993
`8/1993
`9/1993
`9/1993
`9/1993
`9/1993
`11/1993
`12/1993
`2/1994
`3/1994
`4/1994
`5/1994
`10/1994
`10/1994
`1/1995
`1/1995
`1/1995
`2/1995
`3/1995
`3/1995
`4/1995
`4/1995
`4/1995
`5/1995
`5/1995
`5/1995
`9/1995
`10/1995
`11/1995
`11/1995
`12/1995
`1/1996
`2/1996
`4/1996
`4/1996
`6/1996
`7/1996
`7/1996
`7/1996
`9/1996
`9/1996
`9/1996
`10/1996
`11/1996
`11/1996
`12/1996
`12/1996
`1/1997
`2/1997
`
`O’Brien et al.
`Hori et al.
`Huang
`Fascenda
`Mitchell et al.
`Taalfe et al.
`Gibson et al.
`Langdon, Jr. et al.
`Dinwiddie, Jr. et al.
`SZymborski
`Chu
`Rabin et al.
`LantZ
`Taalfe et al.
`Keith et al.
`Hasegawa et al.
`Chevion et al.
`Hiyama et al.
`Normile et al.
`WestaWay et al.
`Ett
`Dangi et al.
`Miller et al.
`Hannon, Jr.
`Seroussi et al.
`Jackson
`O’Brien et al.
`Osterlund et al.
`Toms et al.
`Balkanski et al.
`Barrett
`Carr
`Feigenbaum et al.
`Akins et al.
`Provino et al.
`Pattisam et al.
`Storer
`Hiyama et al.
`Allen et al.
`KulakoWski et al.
`Garahi
`Wasilewski et al.
`Belsan et al.
`Graybill et al.
`Anderson et al.
`Chang et al.
`Whiting
`Perkins
`DiCecco
`Normile et al.
`Chu
`Allen et al.
`Campbell et al.
`Remillard
`Jeong et al.
`Rao
`Mohler
`Hiatt et al.
`James
`Kim et al.
`Bakke et al.
`Craft
`Brady
`Norris
`Carreiro et al.
`Brady et al.
`Rust et al.
`Allen et al.
`Watanabe et al.
`Bhandari et al.
`Chui et al.
`
`5,606,706
`5,612,788
`5,613,069
`5,615,017
`5,621,820
`5,623,623
`5,623,701
`5,627,534
`5,627,995
`5,629,732
`5,630,092
`5,635,632
`5,635,932
`5,642,506
`5,649,032
`5,652,795
`5,652,857
`5,652,917
`5,654,703
`5,655,138
`5,666,560
`5,668,737
`5,671,389
`5,675,333
`5,694,619
`5,696,927
`5,703,793
`5,715,477
`5,717,393
`5,717,394
`5,719,862
`5,721,958
`5,724,475
`5,729,228
`5,748,904
`5,757,852
`5,771,340
`5,778,411
`5,781,767
`5,784,572
`5,787,487
`5,796,864
`5,799,110
`5,805,932
`5,808,660
`5,809,176
`5,809,337
`5,812,789
`5,818,368
`5,818,369
`5,818,530
`5,819,215
`5,825,424
`5,832,037
`5,832,126
`5,836,003
`5,838,996
`5,839,100
`5,841,979
`5,847,762
`5,861,824
`5,861,920
`5,867,167
`5,870,036
`5,870,087
`5,872,530
`5,883,975
`5,886,655
`5,889,961
`5,915,079
`5,917,438
`5,920,326
`5,936,616
`
`2/1997
`3/1997
`3/1997
`3/1997
`4/1997
`4/1997
`4/1997
`5/1997
`5/1997
`5/1997
`5/1997
`6/1997
`6/1997
`6/1997
`7/1997
`7/1997
`7/1997
`7/1997
`8/1997
`8/1997
`9/1997
`9/1997
`9/1997
`10/1997
`12/1997
`12/1997
`12/1997
`2/1998
`2/1998
`2/1998
`2/1998
`2/1998
`3/1998
`3/1998
`5/1998
`5/1998
`6/1998
`7/1998
`7/1998
`7/1998
`7/1998
`8/1998
`8/1998
`9/1998
`9/1998
`9/1998
`9/1998
`9/1998
`10/1998
`10/1998
`10/1998
`10/1998
`10/1998
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`11/1998
`12/1998
`1/1999
`1/1999
`2/1999
`2/1999
`2/1999
`2/1999
`3/1999
`3/1999
`3/1999
`6/1999
`6/1999
`7/1999
`8/1999
`
`Takamoto et al.
`Stone
`Walker
`Choi et al.
`Rynderman et al.
`Kim et al.
`Bakke et al.
`Craft
`Miller et al.
`MoskoWitZ et al.
`Carreiro et al.
`Fay et al.
`Shinagawa et al.
`Lee
`Burt et al.
`Dillon et al.
`Shimoi et al.
`Maupin et al.
`Clark, 11
`Kikinis
`Moertl et al.
`Iler
`Saliba
`Boursier et al.
`Konno
`MacDonald et al.
`Wise et al.
`Kikinis
`Nakano et al.
`Schwartz et al.
`Lee et al.
`Kikinis
`Kirsten
`FranasZek et al.
`Huang et al.
`Kericevic et al.
`NakaZato et al.
`DeMoss et al.
`Inoue et al.
`Rostoker et al.
`Hashimoto et al.
`Callahan
`Israelsen et al.
`KaWashima et al.
`Sekine et al.
`Yajima
`Hannah et al.
`DiaZ
`Langley
`
`Withers .................... .. 341/107
`Can?eld et al.
`Dobson et al.
`Can?eld et al.
`Park
`Tanaka
`Sadeh
`deCarmo
`Wegener
`Schulhof et al.
`Can?eld et al.
`Ryu et al.
`Mead et al.
`Deering
`FranasZek et al.
`Chau
`Domyo et al.
`Narita et al.
`Rust
`Dobbek
`Vondran, Jr. et al.
`Ando
`Rentschler et al.
`Torborg, Jr. et al.
`
`Teradata, Exh. 1001, p. 2 of 58
`
`

`

`US 7,161,506 B2
`Page 3
`
`9/1999 Panaoussis ................. .. 341/51
`5,949,355 A *
`9/1999 Heath
`5,955,976 A
`9/1999 Adams
`5,960,465 A
`5,964,842 A 10/1999 Packard
`5,968,149 A 10/1999 Jaquette et al.
`5,973,630 A 10/1999 Heath
`5,974,471 A 10/1999 Belt
`5,982,723 A 11/1999 Kamatani
`5,991,515 A 11/1999 Fall et al.
`5,996,033 A 11/1999 Chiu-Hao
`6,000,009 A 12/1999 Brady
`6,002,411 A 12/1999 Dye
`6,003,115 A 12/1999 Spear et al.
`6,011,901 A
`1/2000 Kirsten
`6,014,694 A
`1/2000 Aharoni et al.
`6,026,217 A
`2/2000 Adiletta
`6,028,725 A
`2/2000 Blumenau
`6,031,939 A
`2/2000 Gilbert et al.
`6,032,148 A
`2/2000 Wilkes
`6,061,398 A
`5/2000 Satoh et al.
`6,073,232 A
`6/2000 Kroeker et al.
`.
`6,075,470 A
`6/2000 Little et al.
`.
`6,094,634 A
`7/2000 Yahagi et al.
`.
`6,097,520 A
`8/2000 Kadnier
`6,104,389 A
`8/2000 Ando
`6,105,130 A
`8/2000 Wu et al.
`6,128,412 A 10/2000 Satoh
`6,141,053 A 10/2000 Saukkonen
`6,145,069 A 11/2000 Dye
`.
`.
`6,169,241 B1
`1/2001 Shimizu
`.
`.
`6,172,936 B1
`1/2001 Kitazaki
`6,173,381 B1
`1/2001 Dye
`6,182,125 B1
`1/2001 Borella et al.
`.
`6,192,082 B1
`2/2001 Moriarty et al.
`6,195,024 B1
`2/2001 Fallon
`6,226,667 B1
`5/2001 Matthews et al.
`6,226,740 B1
`5/2001 Iga
`
`8/2001 Mann
`6,272,627 B1
`8/2001 Aguilar et al.
`6,272,628 B1
`8/2001 Christensen
`6,282,641 B1
`10/2001 Fallon
`6,309,424 B1
`11/2001 Del Castillo et al.
`6,317,714 B1
`12/2001 Schaefer
`6,330,622 B1
`2/2002 Booth
`6,345,307 B1
`7/2002 Rhee
`6,421,387 B1
`8/2002 Kari
`6,434,168 B1
`8/2002 Esfahani et a1.
`6,434,695 B1
`8/2002 Blumenau
`6,442,659 B1
`9/2002 Toorians
`6,449,682 B1
`9/2002 Morein
`6,452,602 B1
`10/2002 Teoman et al.
`6,463,509 B1
`11/ 2002 Lipasti
`6,487,640 B1
`12/2002 Heath
`6,489,902 B1
`1/2003 Kobayashi
`6,513,113 B1
`3/2003 EaSWilf et 61
`6,529,633 B1
`3/2003 Stewart
`6,539,456 B1
`4/2003 Satoh
`6,542,644 B1
`7/2003 Kltade et a1~
`6,590,609 B1
`7/2003 Fallon
`6,601,104 B1
`6,604,158 B1* 8/2003 Fallon ....................... .. 710/65
`6,606,040 B1* 8/2003 Abdat ....................... .. 341/87
`
`8/2003 Zeineh
`6,606,413 B1
`8/2003 Wolfgang
`6,609,223 B1
`9/2003 Rail
`6,618,728 B1
`6,624,761 B1* 9/2003 Fallon ....................... .. 341/51
`6,661,839 B1
`12/2003 Ishida et al.
`6,704,840 B1
`3/2004 Nalawadi et al.
`6,711,709 B1* 3/2004 York ........................ .. 714/748
`6,745,282 B1
`6/2004 Okada
`6,748,457 B1
`6/2004 Fallon
`2001/0032128 A1 10/2001 Kepecs
`2002/0037035 A1
`3/2002 Singh
`2002/0104891 A1
`8/2002 Otto
`2002/0126755 A1
`9/2002 Li et al.
`2003/0034905 A1* 2/2003 Anton et al. ................ .. 341/51
`2003/0084238 A1
`5/2003 Okada et al.
`2003/0142874 A1
`7/2003 Schwartz
`
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`EP
`
`GB
`JP
`JP
`W0
`W0
`W0
`W0
`
`FOREIGN PATENT DOCUMENTS
`0164677
`12/1985
`0185098
`6/1986
`0283798
`9/1988
`0405572 A2
`1/1991
`0405572 A3
`3/1991
`0493130
`7/1992
`0587437
`3/1994
`0595406
`5/1994
`0718751 A2
`6/1996
`0718751 A3
`2/1997
`9188009
`7/1997
`
`2162025
`6051989
`11149376
`W0 9414273
`W0 9429652
`W0 9502873
`W0 9748212
`
`1/1986
`2/1994
`6/1999
`6/1994
`12/1994
`1/1995
`l2/l997
`
`Pen-Shu Yeh, The CCSDS Lossless Data Compression Recommen
`dation for Space Applications, Chapter 16, Lossless Compression
`Handbook, Elsevier Science (USA), 2003, pp. 311-326.
`Robert F. Rice, Some Practical Universal Noiseless Coding Tech
`niques , Jet Propulsion Laboratory, Pasadena, California, JPL Pub
`lication 79-22, Mar. 15, 1979.
`K. Murashita et al., High-Speed Statistical Compression using
`Self-organized Rules and Predetermined Code Tables, IEEE, 1996
`Data Compression, conference, no month.
`IBM, Fast Dos Soft Boot, Feb. 1, 1994, vol. 37, Issue 28, pp.
`185-186.
`J. Anderson et al. Codeo squeezes color teleconferencing through
`telephone lines, Electronics 1984, pp. 13-15, no month.
`Robert Rice, “Lossless Coding Standards For Space Data Systems”,
`IEEE 1058-6393/97, pp. 577-585, no month.
`Coene, W et al. “A Fast Route For Application of Rate-distortion
`Optimal Quantization in an MPEG Video Encoder” Proceedings of
`the International Conference on Image Processing, US., New York,
`IEEE, Sep. 16, 1996, pp. 825-828.
`“Operating System Platform Abstraction Method”, IBM Technical
`Disclosure Bulletin, Feb. 1995, vol. 38, Issue No. 2, pp. 343-344.
`
`* cited by examiner
`
`Teradata, Exh. 1001, p. 3 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 1 0134
`
`US 7,161,506 B2
`
`INPUT DATA STREAM
`
`I
`
`2
`IDENTIFY INPUT DATA TYPE AND
`GENERATE DATA TYPE IDENTIFICATION /
`SIGNAL
`
`DATA TYPE l
`
`ID SIGNAL
`
`l
`
`COMPRESS DATA IN ACCORDANCE WITH _/3
`IDENTIFIED DATA TYPE
`
`I
`
`COMPRESSED DATA STREAM
`
`I
`
`5
`RETRIEVE DATA TYPE
`INFORMATION OF COMPRESSED /
`DATA STREAM
`
`I
`
`6/‘
`
`DECOMPRESS DATA IN ACCORDANCE _/6
`WITH IDENTIFIED DATA TYPE
`
`I
`
`FIG. 1
`PRIOR ART
`
`Teradata, Exh. 1001, p. 4 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 2 of 34
`
`US 7,161,506 B2
`
`E.«GQMQOOZN
`
`\\S_sqmmhm
`
`mofifiomme
`
`Emumam
`
`_\mmfizaoo
`
`Emfiam
`
`Nmmbzsoo
`
`Emmooozm
`
`mmmmooozm
`
`Eqmmxm«R1Q
`
`
`
`zo_mmmE2oozo_mmmmn_s_oo50.2.$.<o
`
`zo_E_mowmommmfizaoommutnmmm:.z:oo
`
`
`
`mat.\zo_»M__,_,E_mm»moEmursmmmmwooozw<55xoo._m
`zomE<as_oo._
`
`
`N.O_u_
`
`Emumnm
`
`cmmpzaoo
`
`cmmmooozw
`
`Teradata, Exh. 1001, p. 5 of 58
`
`Teradata, Exh. 1001, p. 5 of 58
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 3 0f 34
`
`US 7,161,506 B2
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`COUNT SIZE OF
`DATA BLOCK
`
`BUFFER DATA BLOCK "[304
`
`COMPRESS DATA
`BLOCK WITH
`ENABLED ENCODERS
`
`BUFFER ENCODED
`DATA BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`V
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`V
`CALCULATE
`COMPRESSION
`RATIOS
`
`COMPARE
`COMPRESSION
`RATIOS WITH
`THRESHOLD LIMIT
`
`I
`A
`FIG. 3a
`
`Teradata, Exh. 1001, p. 6 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 4 0f 34
`
`US 7,161,506 B2
`
`316
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`i
`YES
`V
`318
`APPEND NULL
`322
`sELECT ENCODED
`DATA BLOCK WITH / DESCRIPTOR TO /
`GREATEST
`UNENCODED INPUT
`COMPRESSION RATIO
`DATA BLOCK
`
`V
`APPEND
`CORRESPONDING J324
`DESCRIPTOR
`
`‘
`OUTPUT ENCQDED
`DATA BLOCK WITH V4525
`DESQRIPTQR
`
`TY
`OUTPUT UNENCODED
`DATA BLOCK WITH J 320
`NULL DESCRIPTOR
`
`MORE
`DATA BLOCKS IN INPUT <————-———-———
`STREAM?
`
`YES
`
`I
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`I
`B
`
`FIG. 3b
`
`Teradata, Exh. 1001, p. 7 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 5 of 34
`
`US 7,161,506 B2
`
`EEomqoozm
`
`mo.EEommQNmmfizaoo§:<mEmEmursmmmmmooozm
`
`Emumnm
`
`_.mmpzaoo
`
`_.mmmaoozm
`
`:<mEmE.<Q
`
`
`zo_mmmEs_oozO_mm.nEn=>_oo5&2.
`zocémommommm._.ZDO0mmuiam
`
`
`
`
`
`mn_>._.\zo_.:%~»_.\x,\_mm.nmoEmniammmmmaoozm<._.<n.
`
`zom_m<n_s_oo
`
`ow
`
`
`
`zo:.<z_s_mmEommo.6<u_
`
`
`
`n_OMMDOEmmooozm
`
`
`
`tam:>5_m<m_mmo
`
`Emnmsm
`
`cmmtzaoo
`
`cmmmooozm
`
`ov8
`
`8.
`
`<._.<D
`
`v_oo._m
`
`mm:.z:oo
`
`Teradata, Exh. 1001, p. 8 of 58
`
`Teradata, Exh. 1001, p. 8 of 58
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 6 6f 34
`
`US 7,161,506 B2
`
`RECEIvE INITIAL _/500
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`v
`COUNT SIZE OF _/5O2
`DATA BLOCK
`
`5 4
`BUFFER DATA BLOCK -/ 0
`
`TV
`COMPRESS DATA I506
`BLOCK WITH
`ENABLED ENCODERS
`
`v
`508
`APPEND CORRESPONDING
`DESIRABILITY FACTORS TO I
`ENCODED DATA BLOCKS
`
`V
`510
`BUFFER ENCODED DATA
`BLOCK OUTPUT J
`FROM EACH ENCODER
`
`V
`COUNT SIZE OF
`ENCODED DATA _/512
`BLOCKS
`
`V
`CALCULATE
`COMPRESSION _/514
`RATIOS
`
`516
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD -/
`LIMIT
`
`1
`A
`FIG. 5a
`
`Teradata, Exh. 1001, p. 9 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 7 0f 34
`
`US 7,161,506 B2
`
`518
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`YES
`
`i
`
`i
`520
`APPEND NULL
`CALCULATE FIGURE OF
`MERIT FOR EACH ENCODED j524 DESCRIPTOR TO /
`DATA BLOCK WHICH EXCEED
`UNENCODED INPUT
`THRESHOLD
`DATA BLOCK
`
`526
`SELECT ENCODED DATA
`BLOCK WITH GREATEST 1
`FIGURE OF MERIT
`
`V
`APPEND
`CORRESPONDING ¢528
`DESCRIPTOR
`
`V
`OUTPUT UNENCODED 522
`DATA BLOCK WITH 1
`NULL DESCRIPTOR
`
`\'
`OUTPUT ENCODED
`DATA BLOCK WITH ¢530
`DESCRIPTOR
`
`532
`
`MORE
`DATA BLOCKS IN
`INPUT STREAM’?
`
`YES
`Y
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA I534
`BLOCK FROM INPUT
`STREAM
`
`B FIG. 5b
`
`Teradata, Exh. 1001, p. 10 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 8 of 34
`
`US 7,161,506 B2
`
`
`
`<.~.<QQWQOUZM
`
`\\S:<mEm
`
`moEEomwd
`
`zo_mmmEn.s_oo
`
`mn_>._.
`
`zo_E_momwo
`\zo_H<z__2mm:.mo
`
`zow_m<m2oo
`
`zo_mwmEs_oo
`
`o:<m
`
`Bmuinm
`
`_.mm:.z3oo
`
`Emfinm
`
`NKMFZDOO
`
`Emnrsm
`
`mKMFZDOO
`
`Emmusm
`
`:mmkzaoo
`
`Emmooozm
`
`mmmmooozm
`
`mmmmooozm
`
`c
`
`cmmmooozm
`
`©.w_n_
`
`._.Dn_Z_
`
`<._.<D
`
`mmnmsm
`
`<53
`
`x0O._m
`
`mmezaoo
`
`§<<..a..E..~m.«R«G
`
`8
`
`-mw.m:
`
`
`
`WEE.QMENOWQM.
`
`Teradata, Exh. 1001, p. 11 of 58
`
`Teradata, Exh. 1001, p. 11 of 58
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 9 0f 34
`
`US 7,161,506 B2
`
`INPUT INITIAL
`70O\ DATA BLOCK FROM
`INPUT DATA STREAM
`
`70
`
`v
`
`B ’
`
`COUNT SIZE OF
`DATA BLOCK
`
`710
`
`‘I
`
`704\ BUFFER DATA BLOCK
`
`ENCODING
`COMPLETE?
`
`‘I
`
`706x INITIALIZE TIMER
`
`\
`
`BEGIN
`708\ COMPRESSING
`DATA BLOCK WITH
`ENCODERS
`
`YES
`
`i (714
`
`BUFFER
`ENCODED DATA
`BLOCK OUTPUT
`FROM EACH
`ENCODER
`
`v [716
`STOP
`ENCODING
`PROCESS
`
`f718
`,
`BUFFER ENCODED
`DATA BLOCK FOR EACH
`ENCODER THAT
`COMPLETED ENCODING
`PROCESS
`WITHIN TIME LIMIT
`
`COUNT SIZE OF
`ENCODED DATA
`BLOCKS
`
`1720
`
`CALCULATE
`COMPRESSION
`RATIOS
`
`V
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD 1724
`LIMIT
`
`I
`A
`
`FIG. 7a
`
`Teradata, Exh. 1001, p. 12 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 10 0f 34
`
`US 7,161,506 B2
`
`726
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`NO
`
`1
`YES
`'4'
`728
`APPEND NULL
`732
`SELECT ENCODED
`DATA BLOCK WITH / DEscRIPTOR TO /
`GREATEST
`UNENCODED INPUT
`COMPRESSION RATIO
`DATA BLOCK
`
`V
`APPEND
`CORRESPONDING ‘r734
`DESCRIPTOR
`
`‘
`OUTPUT ENOODED
`DATA BLOCK WITH E736
`DESCRIPTOR
`
`\
`730
`OUTPUT UNENCODED
`DATA BLOCK WITH ./
`NULL DESCRIPTOR
`
`MORE
`DATA BLOCKS IN INPUT <———————
`STREAM?
`
`YES
`
`I
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`I
`B
`
`FIG. 7b
`
`Teradata, Exh. 1001, p. 13 of 58
`
`

`

`U.S. Patent
`
`hS
`
`M
`
`S
`
`61.}
`
`2BM
`
`78
`
`5.1,wGE
`
`E3omdoozm
`
`nmofiiowmmNmmhzaooh\\S§<mEmEmursmmmmmooozm
`
`Romwmooma0mat<532ommzooo:<mEmtam
`._.Dn_Z_xoo._m
`
`9.,z_man.zo_mmmm%,_oo<20Suz_
`
`\zo:<z_2mEmommmpzaoo8mmooozwmmrmamzomfiizoo.mmhznooMzo_E_mommo
`
`owS
`
`ncmmkzsoomEmtamcmmmooozm
`
`
`Uzo_._<z_s_m.n:mommoB<u_
`tam:>:.__m<m_mmoem
`
`
`
`
`
`tomagmammooozm
`
`3imm:
`
`49.8mmsfiMSEomtammm
`
`Teradata, Exh. 1001, p. 14 of 58
`
`E.n._nE3m
`
`Emmooozm
`
`
`
`
`
`_.mmpzaoo§<mEm<1:\Q
`
`Teradata, Exh. 1001, p. 14 of 58
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 12 of 34
`
`US 7,161,506 B2
`
`8
`
`moiiommoE2<mEmE<Qomooozm
`
`zo_mmmEs_oommooozm
`29n=N_mmommo_.o<u_
`
`hmnfi>...:_m<m_mm_n_8
`
`zo_mmmE2oo
`
`emoa
`
`
`
`5om....s.<mEmE3
`
`u_Omacaw.
`
`hams.
`
`zo:.<z_s_mm:.mo
`
`C.E..-
`
`zomE<%,_oo.
`
`zo:<z_sEmEocm9m...<20xoo._m
`
`\.mm..r5mmmpzsoo
`
`om
`
`
`
`
`
`o_»<m._-3&2.<._.<D
`
`
`
`oovoomms:qmtamqm
`
`$2:
`
`émms
`
`Teradata, Exh. 1001, p. 15 of 58
`
`Teradata, Exh. 1001, p. 15 of 58
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 13 0f 34
`
`US 7,161,506 B2
`
`100
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`102\.
`
`B ’
`
`"
`COUNT SIZE OF
`DATA BLOCK
`
`I,
`
`104T”
`
`BUFFER DATA
`BLOCK
`
`v
`
`1D5\ INITIALIZE TIMER
`
`‘I
`APPLY INPUT DATA
`BLOCK TO FIRST
`108
`\ ENCODING STAGE
`IN CASCADED
`ENCODER PATHS
`
`\
`
`A’ TIME EXP'RED?
`
`APPLY OUTPUT
`OF COMPLETED
`ENCODING
`STAGE TO NExT
`ENCODING
`STAGE IN
`CASCADE PATH
`
`BUFFER
`ENCODED DATA
`BLOCK OUTPUT
`FROM
`COMPLETED
`ENCODING
`STAGE
`
`1 18
`r
`STOP ENCODING ‘
`PROCESS
`A
`
`(120
`l
`SELECT BUFFERED OUTPUT OF LAST
`ENCODING STAGE IN ENCODER
`CASCADE THAT COMPLETED ENCODING
`PROCESS WITHIN TIME LIMIT
`
`I
`COUNT SIzE OF
`ENCODED DATA r[122
`BLOCKS
`I
`CALCULATE
`COMPRESSION _/124
`RATIOS
`I
`COMPARE COMPRESSION
`RATIOS WITH THRESHOLD 1126
`LIMIT
`
`FIG. 103
`
`I
`A
`
`Teradata, Exh. 1001, p. 16 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 14 0f 34
`
`US 7,161,506 B2
`
`128
`
`IS
`COMPRESSION
`RATIO OF AT LEAST ONE
`ENCODED DATA BLOCK
`GREATER THAN
`THRESHOLD?
`
`YES
`
`III
`CALCULATE FIGURE OF
`134\ MERIT FOR EACH ENCODED
`DATA BLOCK WHICH ExcEED
`THRESHOLD
`
`SELECT ENCODED DATA
`136
`\ BLOCK WITH GREATEST
`FIGURE OF MERIT
`
`NO
`
`i
`
`APPEND NULL
`DESCRIPTOR TO
`UNENCODED INPUT
`DATA BLOCK
`
`130
`
`‘L
`APPEND
`138w CORRESPONDING
`DEscRIPToR
`
`‘V
`OUTPUT UNENCODED 132
`DATA BLOCK WITH 1
`NULL DESCRIPTOR
`
`OUTPUT ENCODED
`14%» DATA BLOCK WITH
`DEscRIPTOR
`
`DATA BLOCKS IN
`INPUT STREAM?
`
`146
`
`TERMINATE DATA
`COMPRESSION
`PROCESS
`
`YES
`V
`I144
`RECEIVE NEXT DATA
`BLOCK FROM INPUT
`STREAM
`
`I
`B FIG. 10b
`
`Teradata, Exh. 1001, p. 17 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 15 0f 34
`
`US 7,161,506 B2
`
`E. <Q hDnCDO
`
`\ 8 S \ \ 8:
`
`No:
`
`
`
`
`<20 5050 A 8 580mm 1 moEEowmo <20 SQ; SEEM E3
`
`5&3 \ . zopoébm A mwumnm V606 m
`
`, 8 mwaoown
`
`5 580mm
`
`moEEuwmq
`
`5 $0086
`
`\ 3
`2,
`
`v r GE
`
`Teradata, Exh. 1001, p. 18 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 16 0f 34
`
`US 7,161,506 B2
`
`RECEIVE INITIAL
`DATA BLOCK FROM
`INPUT DATA STREAM
`
`I
`
`BUFFER DATA BLOCK
`v
`
`l
`
`EXTRACT DATA
`COMPRESSION TYPE
`f 1204
`DESCRIPTOR
`
`IS DATA
`COMPRESSION
`
`1 206
`
`YES
`
`NO
`
`1210
`SELECT DECODER{S) J
`CORRESPONDING TO
`DESCRIPTOR
`l
`DECODE DATA BLOCK USING _f1212
`SELECTED DECODER(S)
`
`Ir
`
`OUTPUT DECODED
`DATA BLOCK
`
`OUTPUT
`UNDECODED
`DATA BLOCK
`
`(1220
`RECEIVE NEXT
`DATA BLOCK IN
`INPUT STREAM
`
`YES
`
`MORE DATA
`BLOCKS IN INPUT
`STREAM?
`
`TERMINATE
`DECODING PROCESS
`
`1218
`
`FIG. 12
`
`Teradata, Exh. 1001, p. 19 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 17 0f 34
`
`US 7,161,506 B2
`
`
`
`
`
`wkmuoocm Emvcmawo E980
`
`
`
`< All mabououcm 1
`
`55805
`
`
`
`mohmuoucm (0N2.
`
`mw> E950
`
`Emucwqmo
`
`
`
`Emncmqwus E950 02 Eng 1
`
`awuoucm cgEmoomm
`
`
`
`
`
`5 Saw
`
`
`m All]: 3 380cm BEES
`a 82
`
`E5255 1 w
`
`
`
`. cozEmooom
`
`. I 8 EEQEQQZ
`. 6 5w:
`
`<2 mmzwi
`
`92. w
`
`ON 2 w w
`
`ES 59.; xogm Ema E85
`
`
`
`
`hmtsm LQEJOO Lilli
`
`
`Ema
`
`Teradata, Exh. 1001, p. 20 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 18 of 34
`
`US 7,161,506 B2
`
`umuoocm
`
`
`
`Loacommoco_m$aEoocofiwmaeoo
`
`5?Sanucmaa<m:_E.9mQ
`
`
`
`ma?ozmm
`
`
`
`_oE.:ommn_€m.__:cwm.5
`
`m2manor.
`
`EDm..mE:oo\._mt:m
`
`moEmwcsootmtzm
`
`—.D..u...mwC300tmt3m
`
`mom..mE:oo:mt:m
`
`282
`
`rmm.oE:oo:mt:m
`
`Nmeficsootmtsm
`
`mmeflcsootmtsm
`
`cmm.5E:OOtmt3m
`
`Teradata, Exh. 1001, p. 21 of 58
`
`Teradata, Exh. 1001, p. 21 of 58
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 19 of 34
`
`US 7,161,506 B2
`
`
`
`
`Receive Initial
`Data Block From
`
`~ 1400
`
`
`
`Input Data
`Stream
`
`Count Size of
`Data Block
`
`’” 1402
`
`Buffer Data Block «/1404
`
`
`
`
`
`Apply Content
`Dependent Data
`Recognition
`
`~1406
`
`
`
`Recognize Data
`Stream Content
`
`No—> B
`
`?
`
`FIGURE 14A
`
`Teradata, Exh. 1001, p. 22 of 58
`
`Teradata, Exh. 1001, p. 22 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 20 of 34
`
`US 7,161,506 B2
`
`
` Compress Data
`
`
`
`Block with
`
`Enabled Content
`
`~141O
`
`
`
`
`Independent
`Encoders
`
`
`
`
`Buffer Encoded
`Data Block Output
`
`~1412
`From Each
`
`
`
`Encoder
`
`
`
`
`Count Size of
`~1414
`Encoded Data
`
`
`
`Blocks
`
`
`
` Calculate
`~1416
`Compression
`Ratio
`
` Compare
`
`
` D
`
`Threshold Limit
`
`Compression
`Ratios with
`
`
`
`FIGURE 14B
`
`Teradata, Exh. 1001, p. 23 of 58
`
`Teradata, Exh. 1001, p. 23 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 21 of 34
`
`US 7,161,506 B2
`
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`
`
`
`
`
`Independent Threshold
`1420 ~
`
`
`
`
`
`Append Null
`Select Encoded
`Data Block with
`Descriptor to
`Greatest
`Unencoded Input
`Data Block
` 1422 ~
`Compression Ratio
`
`
`
`
`
`
`Append
`Corresponding
`Encoding
`Descriptor
`
`1424 ~
`
`
`
`
`
`
`
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`
`
`Terminate
`
`
`
`
`
`More Data
`
`Receive Next
`Data Block From
`
`Input Stream
`
`Blocks in Input
`Data Compression
`Stream
`Process
`
`?
`
`
`Yes
`
`1430
`
`FIGURE 14C
`
`Teradata, Exh. 1001, p. 24 of 58
`
`Teradata, Exh. 1001, p. 24 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 22 of 34
`
`US 7,161,506 B2
`
`Select Recognized
`1434~ Data TypelFi|e or Block
`in List or Algorithm
`
`1436 ~
`
`Select Content
`
`Dependent
`Algorithm(s)
`
`
`
`Dependent Encoder(s)
`
`Compress Data Block
`1438 ~ with Enabled Content
`
`1440 ~
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`N°+ F
`
`
`Compression
`Ratio of at Least One
`
`Encoded Data Block
`
`
`
`
`
`
`1442 N Count Size of Data
`Blocks
`
`1444 ~
`
`
`
`Calculate
`'
`R t‘
`ompression aio
`
`C
`
`Greater Than
`
`Content Dependent
`Threshold
`?
`
`
`
`~1448
`
`Yes
`
`+ E
`
`FIGURE 14D
`
`Teradata, Exh. 1001, p. 25 of 58
`
`Teradata, Exh. 1001, p. 25 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 23 of 34
`
`US 7,161,506 B2
`
`m
`
`
`
`
`
`QmuoocmEmucmqmoHCQCOU
`
`<noLmuoucm
`
`_\DLmnoocm
`
`NoEuoocmIown;
`
`
`
`E9200Emu
`
`EDBuoocmEma.9500
`
`
`
`
`Emucmqmov_oo_m98E85
`
`coacmoumm
`
`m__”=smo
`
`coacmoomm
`
`5Eu:
`
`EEs__om_<
`
`<3maze:
`
`Teradata, Exh. 1001, p. 26 of 58
`
`Teradata, Exh. 1001, p. 26 of 58
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 24 of 34
`
`US 7,161,506 B2
`
`umuoocm
`
`£_>>98
`
`._9q_._ommn_
`
`ozmmco_mmm.aEoo
`
`v_o;mmE._.m>on<E980moBflcsootmtsmIon?
`
`
`
`
`
`5m..9c_._oo:mt:m_
`
`
`
`_o.h_bmoou_o%e£.
`
`
`
`co_mmm._n_EooEmucmqmo
`25co_8oaEoomom§c:ootmt:m
`
`Hwm._.
`
`EDw._9c:oOtm.£._m
`
`
`
`
`
`u_ocmm.=.:.>>o_mmozmmco_mm9.E00
`
`mc_E§mn_
`
`coamwaeoo
`
`u_o:wmE._.\ozmm
`
`rmm._9C300\._mt.3m
`
`rmEuoocm
`
`mmemfisootwtsmmmauoocm
`
`mmEflczootmtsmmmauoocm
`
`
`
`mm;m_m:o_.._
`
`
`
`
`
`emuoucm.cmvcmamuc_EQCOO
`
`Teradata, Exh. 1001, p. 27 of 58
`
`Teradata, Exh. 1001, p. 27 of 58
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 25 of 34
`
`US 7,161,506 B2
`
`
`
`
`
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`~1600
`
`Count Size of
`Data Block
`
`~ 1602
`
`Buffer Data Block ~1604
`
`
`
`
`
`Apply Content
`Dependent Data
`Recognition
`
`~1606
`
`
`
`Recognize Data
`Stream Content
`?
`
`No—> B
`
`YES
`vi
`
`C
`
`FIGURE 16A
`
`Teradata, Exh. 1001, p. 28 of 58
`
`Teradata, Exh. 1001, p. 28 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 26 of 34
`
`US 7,161,506 B2
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`Count Size of
`
`Encoded Data Blocks
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`D
`
`F|GURE 16B
`
`Teradata, Exh. 1001, p. 29 of 58
`
`Teradata, Exh. 1001, p. 29 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 27 of 34
`
`US 7,161,506 B2
`
`
`
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`Append Null
`Descriptor to
`
`Unencoded Input
`Data Block
`
`
`
`Select Encoded
`Data Block with
`Greatest
`
`Compression Ratio
`
`
`
`
`
`
`Append
`Corresponding
`
`Encoding
`Descriptor
`
`
`1624 ~
`
`
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`
`
`Output Encoded
`Data Block with
`
`Descriptor
`
`
`
`
`
`Receive Next
`More Data
`Data Block From —
`Blocks in Input
`Stream
`?
`
`
`
`
`
`Data Compression
`Process
`
`Terminate
`
`1630
`
`
`
`Yes
`
`Input Stream
`
`FIGURE 16C
`
`Teradata, Exh. 1001, p. 30 of 58
`
`Teradata, Exh. 1001, p. 30 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 28 of 34
`
`US 7,161,506 B2
`
`Select Recognized
`1634~ Data Type/File or Block
`in List or Algorithm
`
`1636 ~
`
`Select Content
`
`Dependent
`A|gorithm(s)
`
`
`
`Dependent Encoder(s)
`
`Compress Data Block
`1638 ~ with Enabled Content
`
`Buffer Encoded Data
`
`No» B ~1648
`
`Content Dependent
`Threshold
`
`Yes
`
`V E
`
`Calculate
`1644 ~ Compression Ratio
`
`FIGURE 16D
`
`Teradata, Exh. 1001, p. 31 of 58
`
` Compression
`Ratio of at Least
`
`One Encoded Data
`Block Greater Than
`
`
`
`
`
`
`1640 ~
`
`1642 N
`
`Block From Each
`Encoder
`
`Count Size of Data
`Blocks
`
`Teradata, Exh. 1001, p. 31 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 29 of 34
`
`US 7,161,506 B2
`
`EEvoocm
`
`
`
`8:.m__u_Emo
`
`ucmcozcmoomm
`
`
`
`E£__o9<co_aE_am_
`
`
`
`$33n5-xoo._.5
`
`<5.mane:
`
`
`
`emuoocmEmucmam6:_E280coacmoomm
`
`
`
`
`
`
`
`
`
`emuoocmEmucmamo«CQCOO
`
`MDEuoocm
`
`_.
`
`D.wuoo:m
`
`moEuoocm2omm_.
`
`EQCOO
`
`EDEuoocmm..mQ
`
`#cmummmm._muc_.9500
`
`Zcmucmqmov_oo_mEmaEmmsm
`
`Teradata, Exh. 1001, p. 32 of 58
`
`Teradata, Exh. 1001, p. 32 of 58
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 30 of 34
`
`US 7,161,506 B2
`
`.o§._ommn_co_mmmaEoomc_E._m..mn_
`
`
`£3,93.
`._oE__owmQAvmmxmwm.5
`mn_>._.:o_mwmEEoo
`
`
`
`
`om?9%w
`
`
`
`mt‘MMDOE
`
`_.mw_mE:oo:o__uSm_
`
`mmBficsootmtzm
`
`mmm._9c:o0\._mE:m
`
`cmEmuczootmtsm
`
`
`
`umuoocmEDm._mE:oo\._mt_..m
`
`noEflczootmtzm
`
`_.Dw._wE:OOtmt.:m
`
`mom._9::ootmt:m2om?
`
`Teradata, Exh. 1001, p. 33 of 58
`
`Teradata, Exh. 1001, p. 33 of 58
`
`
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 31 of 34
`
`US 7,161,506 B2
`
`Receive Initial
`
`Data Block From
`
`Input Data
`Stream
`
`~1800
`
`
`
`
`
`Count Size of
`Data Block
`
`A/1802
`
`Buffer Data Block ~1804
`
`
`
`Apply Content
`Dependent /
`Independent Data
`Recognition
`
`
`
`
`
`
`~1806
`
`
`
`Recognize Data
`Stream Content
`
`No-> B
`
`?
`
`Yes
`
`i C
`
`FIGURE 18A
`
`Teradata, Exh. 1001, p. 34 of 58
`
`Teradata, Exh. 1001, p. 34 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 32 of 34
`
`US 7,161,506 B2
`
`Estimate Optimum
`Encoder(s) From
`Estimation Algorithms
`
`Compress Data
`Block with Enabled
`
`Content Independent
`Encoders
`
`Buffer Encoded Data
`
`Block Output From
`Each Encoder
`
`Count Size of
`
`Encoded Data Blocks
`
`Calculate
`
`Compression
`Ratio
`
`Compare
`Compression Ratios
`with Threshold Limit
`
`D
`
`FIGURE 18B
`
`Teradata, Exh. 1001, p. 35 of 58
`
`Teradata, Exh. 1001, p. 35 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 33 of 34
`
`US 7,161,506 B2
`
`
`Compression Ratio
`
`of at Least One Encoded Data
`Block Greater Than Content
`
`
`
`
`
`
`
`Independent Threshold
`1820 ~
`
`
`Select Encoded
`Append NU"
`Data Block with
`Descriptor to
`Greatest
`Unencoded Input
` 1322 ~
`Data Block
`
`Compression Ratio
`
`F
`
`
`
`
`
`
`
`E
`
`
`
`Append
`Corresponding
`
`Encoding
`Descriptor
`
`
`
`
`
`1824 ~
`
`
`
`Output Unencoded
`Data Block with
`
`Null Descriptor
`
`
`
`Descriptor
`
`Output Encoded
`Data Block with
`
`
`
`
`
`Receive Next
`
`More Data
`Data Block From
`Data Compression
`Blocks in Input
`Process
`Stream
`
`
`?
`
`
`
`
`Yes
`
`Input Stream
`
`Terminate
`
`1 830
`
`FIGURE 18C
`
`Teradata, Exh. 1001, p. 36 of 58
`
`Teradata, Exh. 1001, p. 36 of 58
`
`

`

`U.S. Patent
`
`Jan. 9, 2007
`
`Sheet 34 of 34
`
`US 7,161,506 B2
`
`
`
`
`Select Recognized
`
`Data Type/File or Block
`in List or Algorithm
`
`
`1838~
`
`1840 ~ Content Dependent
`
`Select or Estimate
`
`Algorithm(s)
`
`
`
`Dependent Encoder(s)
`
`Compress Data Block
`1842 ~ with Enabled Content
`
`Buffer Encoded Data
`Block From Each
`Encoder
`
`
`
`Count Size of Data
`Blocks
`
`1844 ~
`
`1646 N
`
`1 848
`
`No} F ~ 1850
`
` Compression
`
`Ratio of at Least
`
`
`One Encoded Data
`Block Greater Than
`
`
`
`Content Dependent
`Threshold
`
`
`
`Yes
`
`V E
`
`Calculate
`.
`.
`Compression Ratio
`
`FIGURE 18D
`
`Teradata, Exh. 1001, p. 37 of 58
`
`Teradata, Exh. 1001, p. 37 of 58
`
`

`

`US 7,161,506 B2
`
`1
`SYSTEMS AND METHODS FOR DATA
`COMPRESSION SUCH AS CONTENT
`DEPENDENT DATA COMPRESSION
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is a Continuation of U.S. application Ser.
`No. 10/016,355 filed on Oct. 29, 2001, is a U.S. Pat. No.
`6,624,761, which is a Continuation-In-Part of U.S. patent
`application Ser. No. 09/705,446, filed on Nov. 3, 2000, now
`U.S. Pat. No. 6,309,424, issued on Oct. 30, 2001, which is
`a Continuation of U.S. patent application Ser. No. 09/210,
`491, filed on Dec. 11, 1998, which is now U.S. Pat. No.
`6,195,024, issued on Feb. 27, 2001.
`
`BACKGROUND
`
`1. Technical Field
`
`The present invention relates generally to a data compres-
`sion and decompression and, more particularly, to systems
`and methods for data compression using content indepen-
`dent and content dependent data compression and decom-
`pression.
`2. Description of Related Art
`Information may be represented in a variety of manners.
`Discrete information such as text and numbers are easily
`represented in digital data. This type of data representation
`is known as symbolic digital data. Symbolic digital data is
`thus an absolute representation of data such as a letter,
`figure, character, mark, machine code, or drawing.
`Continuous information such as speech, music, audio,
`images and video, frequently exists in the natural world as
`analog information. As is well known to those skilled in the
`art, recent advances in very large scale integration (VLSI)
`digital computer technology have enabled both discrete and
`analog information to be represented with digital data.
`Continuous information represented as digital data is often
`referred to as diffuse data. Diffuse digital data is thus a
`representation of data that is of low information density and
`is typically not easily recognizable to humans in its native
`form.
`
`There are many advantages associated with digital data
`representation. For instance, digital data is more readily
`processed, stored, and transmitted due to its inherently high
`noise immunity. In addition, the inclusion of redundancy in
`digital data representation enables error detection and/or
`correction. Error detection and/or correction capabilities are
`dependent upon the amount and type of