1110
`
`w. H. HSU AND A. 5. zwxmco
`
`EXPERIMENTAL RESULTS
`
`Design and construction of the test files
`
`To test the overall performance, the system was run on a set of 20 test files. These files
`range in length from approximately 39K to 366K, with representative files from each of the
`ten block types included in the test corpus.
`The test files are designed to model certain types of heterogeneous files, including utilities
`for image viewing, business, or audio processing, and hypothetical multimedia databases and
`programs. To construct these files, a collection of 30 files from the Unix, Apple Macintosh,
`and MS-DOS (IBM PC) operating systems was created. These files are listed in Table II.
`To create the test corpus, they were concatenated in groups of 2 or 3. The resultant series
`of test files is listed in Table III. All of the source files were used. The goal was to generate
`as broad a range of permutations as possible (while restricting the generated files to those
`which are likely to exist in a typical user environment). This was performed manually with
`consideration toward combinatorial constraints and the criteria of realistic data modeling.
`Since all of the files in the source collection originate from common commercial sources
`or from public archives (with the exception of the source and object files, which are from
`the code for the heterogeneous compressor itself), the latter constraint was considerably
`simplified.
`The assembled files were then ported to the test sites (a Sun workstation for Unix
`compress and our heterogeneous compressor; a Macintosh for Srufilt and Compact Pro;
`and an IBM 80486 machine for PKZIP). Binary file transfer mode was used to ensure that
`the file lengths agreed exactly among all platforms.
`
`Performance
`
`In this section, we review and analyze the perfonnance of the heterogeneous compressor
`with respect to compression savings, as compared with four of the commercial systems
`previously discussed; and execution time- Finally, we briefly note the implications of running
`the experiments and compiling perforrna.nce data on several different architectures.
`
`Compression savings
`
`The total length of the uncompressed benchmark suite is just under three megabytes. Table
`IV shows the compressed length achieved by Unix compress, PKZIP, Stufllr, Compact
`Pro and the heterogeneous compression system. The heterogeneous compressor achieved
`the greatest compression, with a total compressed length of 1828K. This represents an
`additional savings of 162K (more than eight per cent) over the best commercial system
`(Compact Pro vl'.32), and 339K (nearly 16 per cent) over the average. Compressed lengths
`for the commercial methods ranged from 1990K to 23?5K.
`Table V compares the percentage savings obtained by our system to the savings obtained
`by the commercial programs and the heterogeneous system. The last two columns show the
`difference in per cent saved between the synthesis system and the best and average of the
`four commercial packages. The best commercial compressor is marked for each of the files.
`Note that the heterogeneous compressor does better than all commercial programs in 19 of
`20 cases and better than three of the four commercial systems in this one case (file 15).
`The difference in compression for this file is only 0.02 per cent, whereas for all the other
`files, the heterogeneous compressor has at least a 1.3 per cent improvement over the best
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE C0., HPES, LLC -
` Ex. 1026, p. 63 of 152
`Ex. 1026, p. 63 of 152
`
`

`
`AUTOMATIC SYNTHESIS OF COMPRESSION TECHNIQUES FOR HETEROGENEOUS FILES 1111
`
`Table I]. Files used to compose the test suite and their fitspective origins
`
`File
`
`designation
`audio 1
`
`lowrdl
`|owrd2
`lowrd3
`lowrd4
`
`textl
`Iext3
`text4
`lexl.5
`text6
`text?
`
`execul
`execu2
`execu3
`execu4
`execufi
`execufi
`
`graphl
`graph2
`graph3
`graph4
`graph5
`graphfi
`graph’?
`
`object
`objecz
`objec3
`
`sourcel
`source2
`
`File
`name
`
`cosby.snd
`
`ticker.txt
`exsound
`huff
`
`appnote.uue
`
`phracictxt
`lechbo-ok.txt
`
`quanta1.txt
`attillafluff
`shadowfiuff
`
`quanta2.txt
`
`ad
`sh
`blob
`zero
`
`networiclexe
`hostname
`
`cornpmisc.drw
`compperi .drw
`computer.drw
`[owres.mpt
`3dbar.drw
`
`imageppm
`STP4
`
`test1.o
`test2.o
`test3.o
`
`table.c
`freeze.c
`
`File
`
`type
`SoundMaster Macintosh audio file
`
`ASCII characters from stock ticker
`
`compressed World Builder sound library
`compressed Unix executable
`uuencoded text
`
`English text
`Unix news article
`
`English text
`English text
`English text
`English text
`
`Unix executable
`Unix executable
`
`Silicon Graphics executable
`Silicon Graphics executable
`IBM PC executable
`Unix executable
`
`Lotus Freelance line drawing
`Lotus Freelance line drawing
`Lotus Freelance line drawing
`MacPaint file
`Lotus Freelance 3-D bar chart
`
`PPM (high-resolution image) file
`Macl’ainl file
`
`Unix object file
`Unix object file
`Unix object file
`
`C source code
`C source code
`
`commercial compressor. The average of each column appears in the bottom row; note that
`the ‘percent difference’ averages are not weighted by file length, as each file is considered
`a separate experiment.
`Because the quality of compression by the synthesis system depends on that of the algo-
`rithms and heuristics used, improvement of the implementations that we use should yield
`higher performance. This is evidenced by comparing the results of compressing a file dom-
`inated by string repetitions by Unix compress and Compact Pro. Both are implementations
`of the Lempel—Ziv algorithm. Unix compress has no heuristics. whereas Compact‘ Pro is
`a better implementation of LZ7'}'.5' " Compact Pro consistently outperforms compress. It
`should be noted that the perfonnance of the Fneeze variant of Lempel—Ziv‘ used in our sys-
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE co., HPES, LLC -
` Ex. 1026, p. 64 of 152
`Ex. 1025, p. 54 of 152
`
`

`
`W. H. HSU AND A. E. ZWARICO
`
`Table III. Combinations of the test files and the resultant simulated data types
`
`File
`number
`
`File
`
`composition
`textl -— Iowrdl
`
`00"-~J!J\l.It-J?-l..I-FIN-.)'—'
`
`graph? -— objecl
`lowrdl — text3 — graph4
`graph? — execu3
`audiol — graph]
`text2 —— lowrdl — graph}.
`|owrd3 —— cxecul
`
`griph2 — lowrd2 -— execu2
`
`sourcel —— lowrd3 — graphfi
`
`audiol — text4
`lowrdl — execu4
`
`graph? — textS
`lowrd2 — text6
`
`text3 — audiol — graphfi
`lowrdl — text-4 — source2
`
`text? — |owrd2 — graph3
`
`graph4 —- audiol — exccu5
`execu4 -—— graph? — text4
`objec3 — lowrd3 — exccufi
`objec2 —— audio! — exccu’2
`
`Classification of
`data modeled
`
`news or stock report
`object file for a graphics viewer
`multimedia application {texb'graphics)
`graphics viewer
`multimedia data file (soundfgraphics)
`multimedia data file (textfgraphics)
`commercial utility
`multimedia application
`(graphicslsoundlexecutable)
`multimedia data or source file
`
`(sourceicompressed binary.-’image}
`multimedia data file (soundltext)
`statistical application with data
`multimedia data file (textfgraphics)
`multimedia data file {soundJ'text)
`multimedia data file (textisoundigraphics)
`source file for multimedia program
`(textlsource code)
`multimedia data file
`
`{textlcompressed audiofgraphics)
`multimedia application (soundlgraphics)
`multimedia application (graphicsftext)
`commercial utility
`audio application
`
`tern does consistently better than compress and is comparable to Compact Pro on standard
`industrial benchmarks.” Improving algorithms and adding or substituting new heuristics
`would also yield more savings.
`
`Execution times and speed optimizations
`
`In this section we compare, in approximate units, the running time of the heterogeneous
`compressor against those of the four commercial systems the savings rates of which for our
`test files are documented above. The units are approximate for two reasons. First, because
`the four test systems are commercial the source code for three of them is not publicly
`available*, which renders an exact measure of user time infeasible. This concern is in part
`assuaged by the non-multitasked, single—user nature of the microcomputer operating systems
`on which three (compress for Linux notwithstanding) of the commercial systems reside.
`Second. however, the drastic architectural and organizational differences among the various
`native machines renders unifomt comparisons unreliable. This applies even to normalized
`execution times because the host machines differ not merely in clock cycle speed, but
`in instruction set architecture and dynamic instruction frequencies for similar compression
`algorithms. The exact running times reported in this section is only that of the heterogeneous
`
`' As noted, however, the Lempcl-—Ziv implementation employed by Smfflt Ciarric is nearly identical to that of Unix compress.
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE C0., HPES, LLC -
` Ex. 1026, p. 65 of 152
`Ex. 1026, p. 65 of 152
`
`

`
`AUTOMATIC SYNTHESIS OF COMPRESSION TECHNIQUES FOR HETEROGENEOUS FILES 1 113
`
`compressor. These comprise the non-commercial‘ compression systems for which source
`code is available for profiling. For the commercial systems we report the observed wall
`clock time to provide a standard of comparison, but note that the host machines vary in
`computational power.
`
`Table IV. Results of the four popular commercial programs and the heterogeneous compression system,
`applied to the 21} test files
`
`File
`number
`
`g,.;..__-._.._.._._.._._._._.q:;¢;a-..;a\:...~..isi.;;\_>...G\O0D--JG\Lh-hLnJt«J—C
`
`Original
`length
`39,348
`44,202
`46,629
`59,254
`169,108
`100,476
`13 I .663
`220,644
`301,805
`255,306
`59,305
`51,715
`63,189
`196,789
`148,903
`164,535
`203,912
`200,640
`366,557
`278,152
`
`Unix
`compress
`20,578
`44,202
`46,629
`52.076
`168,903
`69,77 I
`131,663
`190,971
`145,993
`204,457
`30,173
`51,715
`63,189
`176,276
`73,555
`141,067
`203,912
`128,675
`265,114
`223,277
`
`PKZIP
`v1.10
`17,119
`39,813
`46,629
`40.571
`151,478
`53,043
`103,544
`137,886
`112,503
`191,378
`22,782
`43,032
`58,247
`196,789
`63,743
`132,992
`184,657
`107,728
`198,727
`193.9 80
`
`Srufil'r
`Classic
`20,575
`40,412
`43,26 1
`45.202
`149,701
`65,417
`106,643
`173,677
`137,685
`206,193
`29,701
`46,462
`59,569
`172,486
`75,595
`135,245
`189,398
`125,461
`265,027
`224,943
`
`Compact Heterogeneous
`Pro v1.32
`compressor
`16,831
`16,315
`41,112
`37,383
`40,367
`36,477
`41,607
`38,007
`148,917
`134,524
`52,349
`50,906
`109,979
`96,429
`137,401
`127,384
`115,096
`103,730
`183,313
`168,675
`22,858
`21,774
`44,107
`40,229
`59,934
`54,481
`151,057
`137,052
`64,618
`63,773
`110,093
`104,175
`202,821
`170,564
`104,711
`101,674
`193,756
`187,659
`191,763
`181,030
`
`Tbtal
`
`3,102,137
`
`2,432,201
`
`2,096,646
`
`2,312,653
`
`2,037,690
`
`1,872,251
`
`The running times for the commercial systems on the entire test suite documented above
`appear in Table VI. All of the execution times are measured in wall clock units except for
`the heterogeneous compressor’s, which is a total of user times as reported by prof, the C
`profiler under Unix. The wall clock time was empirically observed not to differ noticeably
`from this total on an unloaded Unix machine. The commercial systems were similarly tested
`on unloaded (or single-task) systems.
`For Unix compress, the mean running time was 26 s, where the average was taken
`over runs on different Sun workstations of comparable power (documented below). A Unix
`implementation of PKZIP was also tested on one of these Sun workstations, and achieved
`an execution time of 56 s « only slightly better than the personal computer version. The
`running time of 856 s placed the heterogeneous compressor in the middle to high end of
`the commercial compressors in terms of running time.
`
`"' For this purpose we continue to consider Unix compress conunercial, due to its wide range of versions.
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE C0., HPES, LLC -
` Ex. 1026, p. 66 of 152
`Ex. 1026, p. 66 of 152
`
`

`
`W. H. HSU AND A. E.. ZWARICO
`
`Table V. Percent savings for the test compression systems‘
`
`Unix
`compress
`{% saved)
`47-70
`0-00
`0-00
`12-11
`0-12
`30-56
`0-00
`13-45
`51-63
`19-92
`49-11
`0-00
`0-00
`10-42
`50-60
`14-26
`0-00
`35-87
`27-67
`19-73
`
`PKZIP
`v1.10
`(% saved)
`56-49
`9-93*
`0-00
`31-53»:
`10-43
`47-21
`21-36::
`37-51
`62-72*
`25-04
`61-59::
`16-79::
`7-82:
`0-00
`57-19*
`19-17
`9-44¢
`46-31
`45-79»:
`30-26
`
`Srufllt
`Classic
`(% saved)
`47-71
`8-57
`7-22
`23-71
`11-48
`34-89
`19-00
`21-29
`54-38
`19-24
`49-92
`10-16
`5-73
`12-35
`49-23
`17-80
`7-12
`37-47
`27-70
`19-13
`
`Compact
`Pro v1.32
`(% saved)
`57-23»:
`6-99
`13-43*
`29-78
`1 1-94:
`47-90*
`16-47
`37-73::
`61-86
`28-20::
`61-46
`14-71
`5-15
`23-24::
`56-61
`33-09*
`0-54
`47-81*
`45-78
`31-06»:
`
`Heterogeneous
`compressor
`(% saved)
`58-54
`15-42
`21-77
`35-86
`20-45
`49-34
`26-76
`42-27
`65-63
`33-93
`63-28
`22-21
`13-78
`30-36
`57-17
`36-69
`16-35
`49-33
`48-80
`34-92
`
`Best
`win
`(% dill.)
`1-31
`5-49
`8-34
`4-33
`8-51
`1-44
`5-40
`4-54
`2-91
`5-73
`1-70
`5-42
`5-96
`7-12
`-0-02
`3-60
`6-91
`1-51
`3-02
`3-86
`
`Average
`win
`(% diff.)
`6-25
`9-04
`16-61
`11-57
`11-96
`9-20
`12-55
`14-77
`7-98
`10-83
`7-77
`11-80
`9-11
`18-85
`3-76
`15-60
`12-03
`7-46
`12-07
`9-87
`
`.-.-.-._._.._.._.._.—.—u'_)oo-...ta~L.p1.|:..L..t[\_).—.
`
`xtilm--.1O\U'I-1'-‘-'.s.‘It»J--C3
`
`20
`
`Average
`
`19-16
`
`29-83
`
`24-21
`
`31 -551:
`
`37-14
`
`4-35
`
`10-96
`
`"‘ The starred entry in each row is the best commercial system.
`
`CONCLUSIONS
`
`Analysis of results
`
`This project was successful on several levels. First, the feasibility of synthesizing com-
`pression plans from encapsulated primitives for heterogeneous files was illustrated. The use
`of property analysis and redundancy metrics was experimentally successful, the latter veri-
`fying the applicability of statistical data analysis to automatic programming in this domain.
`The positive test results obtained with the primitive database currently available would
`probably be even better with improved implementations of the algorithms and heuristics.
`The statistical foundations of the heterogeneous system proved strong enough to be of def-
`inite relevance to the operating systems community, and might be useful in an information
`theoretic context. The benefits of data compression are ubiquitous in that savings through
`compression are independent of hardware and storage capabilities; selective techniques in-
`crease these savings by a significant factor for heterogeneous files.
`
`Future work
`
`The sampling method may be improved in future implementations by randomization.
`The increase in analysis accuracy that this would bring would demand more primitives and
`heuristics — such need would arise in any case with the continuing development of new
`files types, such as high-resolution animation and three-dimensional images.
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE co., HPES, LLC -
` Ex. 1026, p. 67 of 152
`Ex. 1025, p. 57 of 152
`
`

`
`AUTOMATIC SYNTHESIS OF COMPRESSION TECHNIQUES FOR HETEROGENEOUS FILES l l 15
`
`Table VI. Execution times of the heterogeneous and commercial compressors
`
`Compression system
`
`Unix compress
`PKZIP v1.1!)
`Stufflt Classic
`
`Execution time
`(3)
`re 26
`67
`1152
`
`Execution time
`(min)
`0:26
`1:07
`l9: l2
`
`Compact Pro v1.32
`Heterogeneous compressor
`
`1594
`856
`
`26:34
`14:56
`
`In the current system, lossy compression methods can be applied only if an entire file
`is found to be of a lossily compressible data type. Typically, these include high-resolution
`images (for JPEG) and speech, genera] high-definition audio, and high-resolution animation
`files. A special case could be implemented specifying that when an entire file matching a
`single lossily compressible data type (i.e. a homogeneous loss-perrnissible file) is found,
`the lossy algorithm may be applied.
`The difficulty is that without explicit information on where loss-permissible portions of
`a heterogeneous (e.g. multimedia) file begin and end,
`the compressor cannot absolutely
`guarantee that no data will be distorted which the user is not willing to have distorted.
`Thus no lossy methods can be safely applied to any segment in the block-based system.
`Thus a heterogeneous system would require either full interactive guidance from a user
`who could inspect the file or knew its contents, or would require improved magic numbers
`which encoded the lengths of loss-permissible segments. The heterogeneous system could
`then scan for these codes during the property analysis phase and preempt or modify metric-
`based selection if a lossy algorithm is warranted. The latter approach seems far superior
`to interactive compression, which places an intolerable burden of responsibility on users
`(consider a multimedia file with hundreds of interspersed digitized photographs).
`Another improvement worth considering is the use of a ratings system for specialized
`(especially lossy) compression algorithms such as IPEG and MPEG. For example, by des-
`ignating RLE compression '0 per cent alphabetic distribution, 100 per cent run length, 0
`per cent string repetition’ and by defining its single-type counterparts similarly, a standard
`can be established. Unix compress. for instance, might rate ‘4O per cent AD, 0 per cent
`RL, 60 per cent SR’ and a hypothetical algorithm X might rate ‘2S per cent AD, 50 per cent
`RL, 25 per cent SR’ . The rating standard would correspond to the metric rating system for
`files which our system uses, and would help in analysis of the perfonnance of composite
`compression techniques (which handle multiple redundancy types)- Non-synthesized com-
`posite techniques exist, both adaptive and non-adaptive, though results are not as promising
`as those of automatically generated techniques.
`Finally, it is clear from the frequency of duplicate entries in the algorithm lookup table
`that the database of primitives used in this heterogeneous system may not be as well-stocked
`as it optimally could be. Storcr' lists a plethora of optional heuristics which are applicable
`to Lempel—Ziv compression, specifically in augmenting and deleting from the dictionary.
`
`ACKNOWLEDGEMENTS
`
`This paper was produced as part of a research project at Johns Hopkins University. We
`are grateful to the faculty and staff of the JHU Computer Science Department, and to the
`Brown University CS Department. for their assistance throughout this work.
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE C0., HPES, LLC -
` Ex. 1026, p. 68 of 152
`Ex. 1026, p. 68 of 152
`
`

`
`] 116
`
`W. H. HSU AND A. E. ZWARICO
`
`We would like to thank Leonid Broukhis, Graham Toal, and Kenneth Zeger for discus-
`sions on some of the research reported here. We also thank Jonathan Eifrig, Bil] Goodman,
`and Tom Lane for guidance on several technical issues. Finally, we thank the anonymous re-
`viewers for their comments and suggestions, especially for introduction to relevant literature
`in arithmetic coding.
`
`REFERENCES
`
`James A. Storer, Data Compression.‘ Methods and Tiwory, Computer Science Press, Rockville, MD, 1988.
`Phillip W. Katz, PKZIP. Commercial compression system, version l.l, 1990.
`Sun Microsystems, compress. Commercial compression system, operating system version 5.3, September
`1992.
`Raymond Lau, Stufflt Classic and Stufflt Deluxe. Commercial compression system, 1990.
`Bill Goodman, Compact Pro. Commercial compression system, v1.32, I99].
`Terry A. Welch, ‘A technique for high performance data compression’, IEEE Computer, 17(6), 8-19 (I984).
`Gilbert Held and Thomas R. Marshall, Data Compression: Techniques and Applications: Hardware and
`Software Considerations, 3rd edn, John Wiley and Sons, 1991.
`Leonid Broukhis, Freeze implementation of L2]-luf algorithm. comp.sources.misc archives. Internet, 1991.
`.lean—Loup Gailly, compcompression benchmark (Calgary lest corpus). In compcomprcssion FAQ list, .|.
`Gailly, (ed.), 1992.
`Jeffrey S. Viller, ‘Dynamic Huffman Coding‘, ACM Transactions on Mathematical Software, {June 1989).
`J. Ziv and A. Lempel,
`‘A universal algorithm for sequential data compression’, IEEE Transactions on
`Information Theory, 23,(3), 337-343 (1977).
`.l. Ziv and A. Lempel, ‘Compression of individual sequences via variable—rate coding‘, IEEE Transactions
`on lnforrnation Theory, 24(5), 530-546 (1978).
`Jon Louis Bentley, Daniel D. Sleator. Robert E. Tarjan and Victor K. Wei,
`compression scheme’, Commrtnications of the ACM, 320-330 (April I986).
`Yooichi Tagawa, Haruhiko Okumura and Haruyasu Yoshizaki, L.ZHuf: encoding.-‘decoding module for
`Lllarc. Compression system, version 0.03 (Beta). 1989.
`Haruyasu Yoshizaki, LHA: A high-performance lile—comprcssion program. Compression system, version
`2.] l, l99l.
`Edward R. ffiala and Daniel H. Greene, ‘Data compression with finite windows’, Communications of the
`ACM, 490~505 (1989).
`Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures in Pascal. Computer Science Press,
`Rockville, Maryland, second edition, 1987.
`Graham Toal. Personal communication. Unpublished, 1992.
`Gerard Salton, Automatic Text Processing.‘ The Transformation, Analysis, and Retrieval.’ of Information by
`Computer, Addison-Wesley, Reading, MA, 1989.
`Ian F. Darwin,
`file (program). Berkeley Unix operating system, 1987.
`David A. Huffman, ‘A method for the construction of minimum-redundancy codes’, Proceedings of the
`IRE, number 40, 1952, pp. 10934101.
`Claude E. Shannon and Warren Weaver, Tire Mathematical Theory of Communications, University of
`Illinois Press, Urbana and Chicago, 1963.
`Robert Sedgewick, Algorithms. 2nd edn. Addison—Weslcy, Reading, MA, 1988.
`Timothy C. Bell, John G. Cleary and [an H. Witten, Text (.'ompre.rsr'on, Prentice Hall, Englewood Cliffs,
`New Jersey, 1990.
`Sheldon Ross, .4 First Course in Probabr't'r'ty. Macmillan Publishing Company. New York, third edition,
`1988.
`
`‘A locally adaptive data
`
`Ian H. Witten, Redford Neal and John G. Cleary, ‘Arithmetic coding for data compression’, Communica-
`tions of the ACM, 30(6), 520-540 (I 98?}.
`thinlr.com FTP archives, Internet, I994.
`Independent JPEG Group. ‘JPEG image compression system‘,
`.lean~Loup Gailly.
`compcompressionlcomp.compression.research FAQ list.
`I. Gailly (ed.), URL
`http: //mm. cis . ohio-state . edu/hypertext/faq/usenet/compression-faq/top .l:r.tm1, 1994.
`James A. Storer, Image and Text Compression, Kluwer Academic Publishers, Norwell, MA, 1992.
`Graham Toal. C implementation of dynamic Huffman compressor by J. S. Vitter.
`comp.source.misc
`archives, Internet, 1990.
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE C0., HPES, LLC -
` Ex. 1026, p. 69 of 152
`Ex. 1026, p. 69 of 152
`
`

`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL lNC., EMC CORP., HPE CO., HPES, LLC -
` Ex. 1026, p. 70 of 152
`Ex. 1026, p. 70 of 152
`
`

`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
` Ex. 1026, p. 71 of 152
`
`

`
`
`
`a FTWA *-
`
`
`
`PRACTICE & EXPERIENCE
`
`viii lJM[
`
`;_'=_._ Mn '1
`
`JULY 1995
`
`EDITORS
`
`DOUGLAS COMER
`
`‘
`
`ANDY WELLINGS
`
`Chichester Neg-w York Brisbane Toronto Singapore
`A Wiley-lnterscience Publication
`
`SPEXBL 25.1» 705 fi30II995\
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`'59” 0°38 05“ DELL lNC., EMC CORP., HPE co. HPES LLC -
` Ex. 1026, p. 72 of 152
`Ex. 1026, p. 72 of 152
`
`3
`
`.
`
`
`E
`
`

`
`
`
`
`
`PRACTICE 8; EXPERIENCE
`
`VOLUME 25 No. B
`
`AUGUST 1995
`
`EDITORS
`
`,
`
`DOUGLAS COMER
`
`ANDY WELLINGS
`
`WILEY
`
`
`
`_
`n"JJNa\hI‘.'\ K.v.'1ro' WU‘
`ch'lchc$tm. , New Vcuk . Bnsbaflfl ‘ TDIOHIO
`A WiIey—Interscience Publication
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`sPExaL 25:a:331-13EL1E9lNC., EMC CORP., HPE co., HPES, LLC -
`ISSN 00330544
`Ex_ 1025’ p_ 73 of 152
` Ex. 1026, p. 73 of 152
`
`
`
`SPDIC
`
`"19
`
`

`
`
`
`TWARE
`
`PRACTICE 8: EXPERIENCE
`
`SEPTEMBER 1995
`
`VOLUME 25. N0 9
`
`EDITORS
`
`DOU GLAS COMER
`
`ANDY WELLINGS
`
`
`
`@wILE}_r
`
`.F"r;H':l"l'f‘ " "" *
`
`'
`
`I'
`8 isbane - Toronto Sin9i|P°'°
`_
`Chichester - New York '
`t_ n
`A WiIey—|nterscience Publuca I0
`r
`- 051 : I995!
`?sP§§§Ea§°53éfa'BELL lNC., EMC CORP., HPE co., HPES, LLC -
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
` Ex. 1026, p. 74 of 152
`Ex. 1026, p. 74 of 152
`
`
`
`

`
`SOFTWARE
`PRACTICE & EXPERIENCE
`OCTOBER 1995
`
`_ No '10
`
`EDITORS
`
`DOUGLAS COMER
`
`ANDY WELLINGS
`
`l..l_h,,_‘..‘... M”.
`Chichester New York. Br|sbafle_
`A Wiley—Interscience Publication
`
`Tmonw smgzpore
`
`
`
`WILEY
`
`.
`
`§§Er»7'3532a3;'§J4‘°63‘éf.Bf
`EMC CORP., HPE co., HPES, LLC -
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
` Ex. 1026, p. 75 of 152
`. Ex. 1026, p. 75 of 152
`
`

`
`SOFTI/WIRE
`
`PRACTICE 8t EXPERIENCE
`
`_
`Editors
`Professor D. E. Comer, Computer Science Department, Purdue University. West
`Lafayette, IN 47907, U.S.A.
`Charlotte I. Tubis, U.S. Editorial Assistant, Computer Science Dc-partrriont. Purdue: Umvrzrsltv, West Lafayette.
`IN 47907. U.S.A.
`Dr A. J. Wellings, Department of Computer Science, University of York.
`Heslington, York YO1 5DD
`
`i
`
`‘
`
`I
`
`;
`'
`
`,
`;
`
`I
`
`-
`
`i
`
`‘
`i
`
`_,
`
`I
`
`r
`
`-
`
`-
`
`I
`
`dc
`
`3 '
`I
`amp“ er meme
`
`_
`
`S
`l<.’*llJTH
`Prr.i!ess.or D E
`Departrtieril iif C(Jl'Tl[JlJli!.’f’ LII.-iii.-.-,
`Stanford, C.-ilitririii.-i 94.10:, IJ S: A
`_
`I
`D’ B W LAMP,fUr"
`,
`. iv. v »
`~
`.-.
`&Fr'.’l?'n|})1I(?(j(,‘I.(' N
`I‘
`MA o2t3'a. u s A
`
`C’
`.
`
`s‘
`t.'iii ()l'(
`
`1 U
`
`I
`iiivizrsi v.
`
`Advisory Editorial Board
`Prolessor D. W. BARRON
`[)9 an
`I
`fpi
`-
`Univergits/nofosoufifitarmrdgdnén
`Southampton S09 SN}-l. U.K.
`Professor? J BROWN
`-
`-
`Computing Laboratorv. The Universittfi
`Canterburt/,KentCT2 ‘INF, U.K.
`Professor J. A. CAMPBELL
`,
`Deliaitment of Computer Science, University College London,
`Gower Street. London WC‘lE SBT, U.K.
`Professor F. J. CDHBATO
`Electrical E
`'
`'
`Massachus:?t:1fr$sti]:3t2:?gTrec?t$tndlogy
`'
`545 Technolo ysqua.-e_
`Cambridge, llfassachusetls D2139 U.S.A.
`.
`'
`D“ Ch"5‘°|3h*3T W- FRASER
`AT&T Bell Laboratories. 600 Mountain Ave 2C-464.
`Ml-'“'3V Hill. NJ D7974»0636, U.S.A.
`Professor PER BRINCH HANSEN
`.
`.
`§_(¥'°6°lcg§_'C§l‘l'3g:I:J&:[e?tl1‘t;%J‘;|¥:):t[;1aIIOn Science.
`Syracuse. New York 13210, U.S'.A.
`P f
`D’: :t5°l'D- 9- HANSON
`.
`-P
`"'°"t°fC°"‘PUIerScierice.
`Princeton University. Princeton,
`Ne
`J
`W may °85‘“'U'S‘A°
`:r°fess°rJ'KA1_-ZENELSON
`Taculty of Electrical Engineerin ,
`HE;ti:f|';nl|o5ir1;l;rae| Institute of Tecgnology,
`Dr- B. W. KERNIGHAN
`AT&T Bell Lab
`-
`-
`Murray Hill, N:VrlIaEl'Jerr‘:e.5\;f?J(')T“é3lxl1»:.)fl|:léélI5ir‘_| Avenue’
`Aims and Scope
`fl-aflWa'."‘L"P’3°liCe and Experience is an internationallv '9'-Spected a"d rigorous” refereed Vehiqe ft.” the diS5‘?mi"_'ati°" and
`fmsrcussion of practical experience with new and established softwarefor both systems and applications. Contributions regu.
`Y. laldescribe detailed accounts of completed software-system DFOJECIS which can serve as how-to-do-it models for future
`333'" "'3 same field; (13) present short reports on programming technicitles that can be used in a wide variety of areas: (cl
`thaU$entn_ewtechniques and tools that aid in solving software construction problems; and (dl explain methods/techniques
`on raPi‘(’j‘?y"“;":*:'E:|':)l:’:rJecial demands (marge 50313 software proiects. The l0U“’l€" 3'50 features timely Short Communications
`,
`new
`‘
`. The editors activelg gncomggg-papers which fesun from practical experience with tools and methods developed and used
`in both academic and industrial environments The aim is to encourage practitioners to share their experiences with design,
`implementation and evaluation of techniques and tools for software and software systems.
`Papers cover software design and implementation, case studies describing the evolution of system and the thinking behind
`them, and critical appraisals of software systems. The iournal has always welcomed tutorial articles describing welI—tried tech-
`n|CtU€5 n01l3fe.\-'l’ously documented in computing literature. The emphasis is on practical experience; articles with theoretical
`Ormafhematlcal contentare included only in cases where an understanding of the theory will lead to better practical systems.
`Articles range in length from a Short Communication (half to two pages) to the length required to give full treatment to a
`Substantial pieceof software (40 or more pages).
`Advertising: For details contact-—
`M“'-hael -1-
`I-9~V9"T1Ore. Advertisement Sales, John Wiley 84 Sons Ltd, Baffins Lane, Chichester, Sussex PO19 1UD, England (Telephone 01243
`179351. Fax 01243 775373. Telex sszgm
`Sofrware—Practi'ce aflfl'Expen'enc8”SSN (}a33_u545,'USPS 890-920} is published monthly, by John Wiley 8i Sons Limited, Baffins Lane. Chichester,
`5U559X» Eflglaflli Second class postage paid at Jamaica. N.Y. 11431. Air freight and mailing '" the USA. by Publications Expediting Services Inc,
`3'30 M93l3h3"l Avenue. Elrnont, N.Y. 11003, © 1995 by John Wiley 8i Sons Ltd. Printed and bound in Great Britain by Page Bros. Norwich. Printed
`on acid-free paper.
`
`D , C A. LANG
`'
`S
`_ L“
`‘
`;,r8',§§S“gaSCIE;eL_t
`Cambridge ce3'o.ex.i. u K
`p’°f‘’5S°' 8' RANDELL
`Computing Laboratory,
`University of Newcastle upon Tyne,
`Claremont Tower, Clarernurii Road.
`Newcastleupon-Tyne NE1 IFRU, U.K.
`
`professor J, S, ROHL
`Department of C?lUcrpllIl'.‘f SEIQITCOI,
`Th U ‘ ersity 0
`esteiii
`ustra ia,
`Nefjlarridis, Western Australia 5009.
`85
`o. T. no
`Softech Inc.. 460 Tollen Pond Road.
`Waltham, Massachusetts 02154, LJ5,A,
`
`B, H. SHEARING
`The Software Factory,
`28 Padbrook, Limpstield, Oxted.
`surrey HH8 ODW, U.K.
`Professor N. WIRTH
`1
`t't
`t fur Computersysterne, ETH—Zentrum,
`Zurich. Switzerla rid.
`
`To subscribe: Orders should be addressed to Subscriptions Department, John Wiley 8: Sons Limited. Baffins Lana. Ct-iichestei, Sussex, PO19 1UD,
`England. 1995 subscription price (13 issuesl: U.S. $325.00.
`U.5.A. POSTMASTER: Send address changes to Soriware—Practice and Experience. cio Publications Expediting Services Inc., 200 Meacham
`Avenue Elmont. N.Y. 1
`DELL lNC., EME3°3c:”(5'hP., HPE co., HPES, LLC - Ex. 1026, p. 76 of 152_ .
`
`DELL INC., EMC CORP., HPE CO., HPES, LLC - Ex. 1026, p. 76 of 152
`
`

`
`SOFTWARE—PRACTlCE AND EXPERIENCE
`(Softw. pract. exp.)
`
`VOLUME 25, ISSUE No. 10
`
`October 1995
`
`CONTENTS
`
`Migration in Object-oriented Database Systems—A Practical Approach:
`C. Huemer, G. Kappel and S. Vieweg ...........
`....................................... 1065
`
`Automatic Synthesis of Compression Techniques for Heterogeneous
`Files: W. H. Hsu and A. E. Zwarico ........................................................... .. 1097
`
`A Tool for Visualizing the Execution of Interactions on a Loosely-coupled
`Distributed System: P. Ashton and J. Penny ............................................. 1117
`
`Process Scheduling and UNIX Semaphores: N. Dunstan and l. Fris ........ .. 1141
`
`Software Maintenance: An Approach to Impact Analysis of Objects
`Change: 8. Ajila ................................................
`.....
`............................... .. ‘I155
`
`SPEXBL 25110} 1055-1182 H995}
`ISSN 0038-0844
`
`
`
`
`Indexed or abstracted by Cambridge Scientific Abstracts. CompuMath Citation Index iISll,
`Compuscience Database, Computer Contents, Computer Literature lndex, Computing
`
`
`Reviews, Current ContentsfEng, Tech 8: Applied Sciences, Data Processing Digest, Deadline
`Newsletter, Educational Technology Abstracts, Engineering Index, Engineering Societies
`
`
`[_ibrary_ |3z umematio,-.3: Bibliography of Periodical Literature}. Information Science Abstracts
`{Plenum},
`INSPEC, Knowledge Engineering Review. Nat Centre for Software Technology,
`
`Research Alert {Isl} and SCISEAHCH Database iISi}.
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL |NC., EMC CORP., HPE co., HPES, LLC -
` Ex. 1026, p. 77 of 152
`Ex. 1026, p. 77 of 152
`
`
`

`
`
`
`1096
`20.
`
`C. HUEMER, G. KAPPEL AND 3. vn-zwr-:<;
`
`21.
`
`22.
`
`23.
`
`24.
`
`in G-
`A. Scheer and A. Hats, ‘The Lci:stand—a new mo] for dL'cL'nlr:I| pnulucnun cnntI'U1'-
`Fandel and G. Zfipfel (eds), Modern Production Crmccgrm. Springer. Br.-rlm. UNI. PP‘ 37”'385'
`G. Kappel and S. Vieweg, ‘Database requirements for (SIM ;:pp1uc.-mum’. Journal "f "”*"'-‘3"“"d
`Manufacturing Syslems, 5, (45), 48-63 (1994).
`U. Schreier, ‘Database requirements of knowledge-bxascd producuun schcduluul ‘”“i wmmk 3
`CIM perspective’, in R. Agrawal (ed.), Proc.
`I9rI: Inrermmrnmi ('r::r_f¢-r.-rrrv rm \'«'f\'
`I-""".'~"' Dam
`Bases, Dublin, August 1993. pp. 710-711.
`_
`R. Cattell and J. Skeen, ‘Object operations benchmark’. /l('M 'l'rumm-mun an .')umhu.\':'
`-5_V5f¢'"IS-
`17, (1), 1-31 (1992).
`_
`M. Carey, D. Dewitt and J. Naughton. ‘The 007 hcnchmark‘. f’rm' A(‘.U .S‘I(iM()[) ( unf. ACM
`SIGMOD Record, 22, (2), 12-21 (1993).
`
` DELL INC., EMC CORP., HPE CO., HPES, LLC -
`DELL |NC., EMC CORP., HPE CO., HPES, LLC -
` Ex. 1026, p. 78 of 152
`Ex. 1026, p. 78 of 152
`
`
`
`

`
`
`
`S0!-"l'WARE-—PRACT[C[-I AND EXPERIENCE. vot. 2500). 1991-: ns (ocroasn ms)
`
`Automatic Synthesis of Compression Techniques for
`
`Heterogeneous Files
`
`WILLIAM H. HSU
`
`Department of Computer Science. University of iliinois at Urbana-Champaign. Urbaflfl. IL 61801. U.-5'.A-
`(emaii: bit.m@cs.uiuc.edu. voice: (217) 244-1620)
`
`AND
`
`AMY E. ZWARICO
`
`Deparment of Computer Science, The Johns Hopkins University. Baltimore. MD 21213. U-5-A
`femaii: amy@cs.jhu.edu. voice: (4!0J 5I6-5304)
`
`SUMMARY
`
`We present a compression technique for heterogeneous files, those files which contain multiple ll’P95_ 07
`data such as text, images. bina