Home
Home
Introduction
Policy
FAQ
DHPC
SAKDC
MMDC
LZRW1
LZRW1-A
LZRW2
LZRW3
LZRW3-A
LZRW4
LZRW5
Support Code
Thesis
Interface
DCC91
Patents
Printing
Links
Link Here

RossNet

Snowbird vista


DCC'91 Report

This page contains a personal account of the world's first conference entirely devoted to Data Compression: DCC'91. The conference was held at Snowbird, Utah, USA, 7-11 April 1991. This document was posted to comp.compression on 20 May 1991 and was put up for FTP in my compression archive. This page consists of that original report with some spelling errors corrected and with additional comments which were added on 5 May 1996 in the form [05-May-1996: ...]. The original pure-text document is available by FTP as follows:

Please bear in mind that this document was written at least five years ago. Nowadays, I might write this differently. Also, please do not assume that just because I have added corrections, that the rest of the paper represents a statement of fact, or even my current opinions. I added comments in a hurry and might have missed something.


Data Compression Conference 1991 (DCC'91): The Unauthorized Report

By Ross Williams, 20 May 1991.


Abstract

This document gives a personal account of the world's first conference entirely devoted to Data Compression: DCC91. The conference was held at Snowbird, Utah, USA, 7-11 April 1991.


Contents

  • Location
  • Conference Program
  • People
  • Food
  • Patents
  • Standards
  • Skiing
  • Weather
  • My Paper
  • Thursday
  • Organization
  • Proceedings
  • Cost
  • Summary


Location

The first thing that one notices as one flys into Salt Lake City, Utah is that it is flat. Very flat; except that is, for the enormous mountains surrounding it, upon which snow falls thick enough and often enough to provide almost year round skiing conditions. In the heart of a valley in the mountains surrounding Salt Lake City lies Snowbird which is an enormous ski resort. Right in the middle of the enormous ski resort is an enormous hotel called the Cliff Lodge. The conference was held there.

The Cliff Lodge The focus of the Cliff Lodge is an enormous ten story atrium which I suspect was originally designed to hold Saturn V Rockets. The atrium has an enormous glass window which faces onto the mountain where most of the skiing happens. There is usually something interesting going on. The effect is stunning.

On the other side of the lodge is the beginners slope and the ski rental shop. Rising up the mountain is a large cable car and a chairlift. The cable car would go up and ten minutes later the bottom of the mountain would be flooded with skiers. This would go on all day. In the morning there were loud explosions as the snow teams blasted away excess snow. All in all an excellent place to go skiing.


Conference Programme

The conference program was roughly as follows:

   Sunday     7 Registration and reception.
   Monday     8 Papers and banquet.
   Tuesday    9 Papers and poster session.
   Wednesday 10 Papers and rush off to the airport.
   Thursday  11 NASA/Navy Workshops.

About 150 (from memory) papers were received for the conference. 44 papers were accepted for presentation and there were 42 papers in the poster session. The conference seemed to be about 1/3 image compression, 1/3 text compression and about 1/3 coding and theory.

Here is a copy of the programme. My commentary continues after the programme...

--------------------------------------------------------------------------------

DCC'91 Data Compression Conference
----------------------------------
(Sponsored by the IEEE Computer Society TCCC in Cooperation with NASA/CESDIS)
Snowbird, Utah
April 7-11, 1991

Co-General Chairs:
J.Storer, Brandeis U.
J.Reif, Duke U.

Registration Chair: M.Cohn, Brandeis U.

Publicity Chair: R.Miller, NASA/CESDIS

Program Committee:
A.Blumer, Tufts U.
R.Capocelli, U.Rome
J.Cleary, UI.Calgary
P.Elias, MIT
I.Daubechies, Bell Labs
R.Gray, Stanford U.
D.Hirschberg, UC Irvine
A.Lempel, Technion
V.Miller, IBM
J.Reif, Duke U.
D.Sheinwald, IBM
J.Storer, Brandeis U.
J.Tilton, NASA
J.Vitter, Brown U.
A.Wyner, Bell Labs
J.Ziv, Technion

REGISTRATION/RECEPTION
Sunday, April 7, 1991
7:00pm-10:00pm
In the Golden Cliff Room

DCC'91 - Monday, April 8, 1991
------------------------------
8:00am: Welcome

Session 1: 8:05-10:10

8:05 Analysis of Arithmetic Coding for Data Compression
P.Howard and J.S.Vitter (Brown U.)

8:30 Probabilistic and Q-Coder Algorithms for Binary Source Adaptation
G.Langdon (UC Santa Cruz)

8:55 Models for Compression in Full-Text Retrieval Systems
I.H.Witten (U.Calgary), T.C.Bell and C.G.Nevill (U.Canterbury)

9:20 Piecewise Arithmetic Coding
J.Teuhola and T.Raita (U.Turku)

9:45 High Efficiency, Multiplication Free Approximation of Arithmetic Coding
D.Chevion, E.D.Karnin, and E.Walach (IBM Haifa Research Group)


Break: 10:10-10:35

Session 2: 10:35-12:40

10:35 An Image Database for Low Bandwidth Communication Links
M.Malak and J.Baker (Computer Science Co.)

11:00 The Complexity of Optimal Tree Pruning for Source Coding
E.Lin, J.A.Storer, and M.Cohn (Brandeis U.)

11:25 Image Coding by Adaptive Tree-Structured Segmentation
X.Wu and C.Yao (U. Western Ontario)

11:50 Prediction Trees and Lossless Image Compression
N.D.Memon, S.S.Magliveras, and K.Sayood (U. Nebraska at Lincoln)

12:15 Image Compression Methods with Distortion Controlled Capabilities
T.Markas and J.Reif (Duke U.)


Lunch 12:40-4:00


Session 3: 4:00-6:55

4:00 Entropy-Constrained Trellis Coded Quantization
T.R.Fisher (Washington State U.) and M.Wang (U. Wisconsin)

4:25 Combining Vector Quantization and Histogram Equalization
P.C.Cosman, Eve A.Riskin, and Robert M.Gray (Stanford U.)

4:50 Concentric-Shell Partition Vector Quantization with Application to
Image Coding
H.Nguyen and J.W.Mark (U. Waterloo)

5:15 Design and Performance Residual Quantizers
R.L.Frost, C.F.Barnes, and F.Xu (Brigham Young U.)

5:40 An Iteratively Interpolative Vector Quantization Algorithm for
Image Data Compression
K.Xue and J.M.Crissey (Wright State U.)

6:05 A New Transform Domain Vector Quantization Technique for Image Data
Compression in an Asynchronous Transfer Mode Network
P.P.Polit and N.M.Nasrabadi (Worcerster Polytechnic Institute)

6:30 Restricted Boundary Vector Quantization
R.Lindsay (Unisys Co.)

Reception: 7:00pm-8:00pm (Golden Cliff)
Banquet: 8:00pm-10:00pm (Ballroom)


DCC'91 - Tuesday, April 9, 1991
-------------------------------

Session 4: 8:00-9:40

8:00 W-Orbit Finite Automata for Data Compression
Y.Liu asnd H.Ma (Savannah State College)

8:25 Data Compression Using Wavelets: Error, Smoothness, and Quantization
R.A.Devore and B.J.Lucier (Purdue U.)

8:50 A 64 Kb/s Video Codec using a 2-D Wavelet Transform
A.S.Lewis and G.Knowles (Imperial College)

9:15 A Practical Approach to Fractal Based Image Compression
A.P.Pentland and B.Horowitz (MIT)

Break: 9:40-10:05

Session 5: 10:05-12:35

10:05 Fixed Data Base Version of the Lempel-Ziv Data Compression Algorithm
A.D.Wyner (At&T Bell Laboratories) and J.Ziv (Technion)

10:30 Asymptotic Convergence of Dual-Tree Entropy Codes
G.H.Freeman (U. Waterloo)

10:55 On Compression with Two-Way Head Machines
D.Sheinwald (IBM Israel Scientific Centre), A.Lempel and J.Ziv (Technion)

11:20 Asymptotics of Predictive Stochastic Complexity
L.Gerencser (U. Quebec)

11:45 On the Optimal Asymptotic Performance of Universal Ordering and
Discrimination of Individual Sequences
M.Weinberger, J.Ziv, and A.Lempel (Technion)

12:10 A Typical Behaviour of Some Data Compression Schemes
W.Szpankowski (Purdue U.)

Lunch 12:35-4:00

Poster Session and Reception
4:00pm-7:00pm
In the Golden Cliff Room


DCC'91 - Wendnesday, April 10, 1991
-----------------------------------

Session 6: 8:00-10:05

8:00 New Methods for Lossless Image Compression Using Arithmetic Coding
P.Howard and J.S.Vitter (Brown U.)

8:25 Inducting Codes from Examples
W.H.Leung and S.Skiena (SUNY at Stony Brook)

8:50 The Cascading of LZW Compression Algorithm with Arithmetic Coding
Y.Perl, Venkat Maram, and Nageshwar Kadakuntla (New Jersey Inst.
Technology)

9:15 Complexity Aspects of Map Compression
H.Brodlaender, T.F.Gonzales, and T.Kloks (UC Santa Barbara)

9:40 An Optimal Algorithm for the Construction of Optimal Prefix Codes
A.De Santis (U. Salerno) and G.Persiano (Harvard U.)

Break: 10:05-10:30

Session 7: 10:30-12:35

10:30 Compression of Natural Images Using Thread-like Visual Primitives
J.Robinson (U. Waterloo)

10:55 Streamlining Context Models for Data Compression
D.A.Lelewer and D.S.Hirschberg (UC Irvine)

11:20 Semantic Data Compression
G.Promhouse (U. Western Ontario)

11:45 Improving LZW
R.N.Horspool (U. Victoria)

12:10 A Neural Network Based VLSI Vector Quantizer for Real-Time Image
Compression
W.Fang, B.Sheu, and O.T.C.Chen (U. Southern California)

Lunch: 12:35-4:00

Session 8: 4:00-6:55

4:00 Multibit Decoding/Encoding of Binary Codes Using Memory Based
Architectures
A.Mukherjee, H.Bheda, M.A.Bassiouni, and T.Acharia (U. Central Florida)

4:25 Practical Evaluation of Data Compression Algorithm
D.W.Jones (U. Iowa)
[Ed: Note: This talk swapped time slots with Moffat two papers down.]

4:50 An Extremely Fast Ziv-Lempel Data Compression Algorithm
R.N.Williams (U. Australia)
[Ed: Note: I am not from the University of Australia; there is in fact no
such University. I am actually from Renaissance Software,
South Australia].[05-May-1996: Renaissance Software changed its
name to Rocksoft on 21 December 1992.]


5:15 Two-Level Context Based Compression of Binary Images
A.Moffat (U. Melbourne)

5:40 A Better Tree-Structured Vector Quantizer
X.Wu and K.Zhang (U. Western Ontario)

6:05 Flexible Compression for Bitmap Sets
A.Bookstein (U. Chicago) and S.T.Klein (Bar Ilan U.)

6:30 Compression Experiments with AVHRR Data
J.C.Tilton, D.Han, M.Manohar (NASA)

POSTER SESSION
--------------
(Tuesday Afternoon, April 9, 1991)

Adaptive Source Modelling Using A Conditioning Tree
C.C Lu and N.Choong

An Algorithm for Tree Structure Compression
K.Van.Houton and P.W.Oman

Compression of Stereoscopic Image Data
E.Salari an W.A.Whyte, Jr.

Concurrent Techniques for Developing Motion Video Compression Algorithms
J.A.Elliott, P.M.Grant, and G.G.Sexton

Data Compression in View of Data Sealing
E.Koch and M.Sommer

Data Compression with Factor Automata
M.Zipstein

A Design to Increase Media-Independent Data Integrity and Availability
Through the Use of Robotic Media Management Systems
R.Blitstein

Effects of Coefficient Coding on JPEG Basline Image Compression
M.Chang and G.G.Langdon

Exact Data Compression using Hierarchical Directories
D.K.Chang

Experiments on the Compression of Dictinoary Entries
M.R.Lagana, G.Turrini, and G.Zanchi

Experiments on Improving the Compression of Special Data Types
M.Bassiouni, A.Mukherjee, and N.Tzannes

Generalized Scanning and Multioresolution Compression
I.Gertner and Y.Y.Zeevi

Implementing JPEG Algorithm on INMOS Transputer Equipped Machines
A.Omodeo, M.Pugassi, and N.Scarabottolo

IMproved Hierarchical Interpolation (HINT) Method for the Reversible
Compression of Grayscale Images
K.Chen and T.Ramabadran

Index Compression Method with Compressed Mode Boolean Operators
R.P.Millett and E.L.Ivie

Keyword Dictionary Compression Using Efficient Trie Impelemntation
T.Masui

Lossless Coding Techniques for Color Graphical Images
G.S.Yovanof and J.R.Sullivan

Motion-Compensated Video Image Compression Using Luminance and Chrominance
Components for Motion Estimation
C.W.Wong

On the Selection of Color Basis for Image Compression
W.K.Chau, S.K.Wong, X.D.Yang, S.J.Wan

An Optimization Approach for Removing Blocking Effects in Transform Coding
S.Minami and A.Zakhor

Performance Analysis of a Vector Quantization Algorithm for Image Data
A.Desoky and Y.You

Pictorial Data Compression Using Array Grammars
E.T.Lee

Rate Distortion Performance of VQ and PVQ Compression Algorithms
K.M.Liang, S.E.Budge, and R.W.Harris

Reduction in Power System Load Data Training Sets Size using Fractal
Approximation Theory
D.Indjic

Satellite Data Archives Algorithm
K.Nickels and C.Thacker

Signal Processing and Compression for Image Capturing Systems Using a
Single-Chip Sensor
Y.T.Tsai

Some Results on Adaptive Statistics Estimation for the Reversible Compression
of Sequences
T.V.Ramabadran

Systolic Architectures for LZ based decompression
N.Ranganathan and S.Henriques

Techniques for Index Compression
E.L.Ivie

Text Compression Using Several Huffman Trees
D.Basu

3-D Image Compression for X-ray CT Images Using Displacement Estimation
H.Less, Y.Kim, A.H.Rowberg, and E.A.Riskin

Transform Coding of Monochrome and Color Images Using Trellis Coded
Quantization
K.L.Tong and M.W.Marcellin

Trends in Audio and Speech Compression for Storage and Real-Time Communication
P.Mermelstein

2-D Discrete Cosine Transform Array Processor Using Non-Planar Connections
C.Ko and W.Chung

A Uniform Model for Parallel Fast Fourier Transform (FFT) and Fast Discrete
Cosine Transform (FDCT)
W.K.Chou and D.Y.Yun

Universal Data Compression Algorithms Using Full Tree Models
S.Y.Chang and J.J.Metzner

Using Fractal Geometry for Image Compression
K.Culik and S.Dube

V.42bis and Other Ziv-Lempel Variants
C.Thomborson

A Very High Speed Lossless Compression/Decompression Chip Set
J.Venbrux and N.Liu

A Very HIgh Speed Noiseless Data Compression Chip for Space Imaging Applications
R.Anderson, J.Bowers, W.C.Fang, D.Johnson, J.Lee, and R.Nixon

VLSI Implementation of a Vector Quantization Processor
P.Israelson

Waveform Data Compression with Exact Recovery
S.D.Stearns


Space and Earth Science Data Compression Workshop
-------------------------------------------------
Snowbird Utah, April 11, 1991

Held in conjunction with the Data Compression Conference (DCC'91)
Snowbird Utah, April 8-10, 1991.

This workshop seeks to explore the opportunities for data compression
to enhance the collection and analysis of space and earth science
data. In seeking to identify the most appropriate data compression
approaches, the workshop will focus on the scientists' data
requirements, as well as on the constraints imposed by the data
collection, transmission, distribution and archival systems.

8:00am Welcome and opening remarks, from Workshop organizers:
Dr James C. Tilton of NASA GSFC and Dr. Daneil E.Erickson of NASA JPL.

8:10am NASA Headquarters welcome.

Morning session I - Science Data Systems: 8:15-9:45am

Description of information systems for space and earth data,
addressing present and proposed configurations, focussing on the
constraints imposed by colecting, transmitting, distributing and
archiving data.

8:15am: Dr Jeffrey Dozier, Universities Sapce Research Association at
NASA GSFC and Earth Observing System (EOS) Project Scientist.

9:00am Mr Wallace Tai, Mission Information Systems Engineering
Section, NASAA JPL and End-to-End Information System Engineer,
CRAF-Cassini Project.

Morning Session II - Science Data Requirements: 9:45am -12 NOON

Four papers depicting analysis scenarios for extracting information of
scientific interest from data collected by earth-orbiting and
deep-space platforms. Included will be estimates of the volumes of
data involved, frequency of data analysis, required data fidelity, and
analysis algorithms.

9:45am Dr. Vincent Salomonson, Director of the Earth Sciences
Directorate, NASA GSFC and Team Leader for the Moderate-Resolution
Imaging Spectrometer.

10:15am Dr C.Y.Chang, Radar Science and Engineering Section, NASA,
JPL, and manager of the SIR-C Ground Data Processing System.

10:45am Break

11:00am Dr Ray Walker, Institute of Geophysics and Planetary Physics at UCLA.

11:30am Mr William Hartz, Analex Corporation, Cleveland, OH and
principle engineer for the design of the diagnostics systems for the
Combustion Experiments Module at the NASA Lewis Research Centre.


Afternoon session I - Data Compression Approaches 1:30-2:15pm

A taxonomy of data compression techniques, including strengths and
weaknesses.
1:30pm Dr Robert Gray, Professor, Electrical Engineering
Department, Stanford University.


Afternoon Session II: Group Discussions: 2:15-4:30pm

2:15pm Organize groups and appoint group leaders.
2:30pm Group Discussions (20 min break at about 3:15pm)

Afternoon Session III: Summary Group Reports: 4:30pm-5:00pm


U.S. NAVY ENVIRONMENTAL SYSTEMS PROGRAM OFFICE DATA COMPRESSION WORKSHOP
------------------------------------------------------------------------
APRIl 11, 1991
SNOWBIRD, UTAH

In conjunction with the Data Compression Conference, the US Navy
Environmental Systems Program Office invites you to attend a one day
workshop to discuss issues of interest related to data communications
and compression. The issues to be presented will involve such things
as present requirements, equipment, capabilities, and issues relevant
to future concerns.

The program to be presented will consist of both invited speakers from
Navy and industrial organizations. In addition, there will be several
papers presented which dal with various aspects of compression
vis-a-vis Navy requirements. The prtogram for the workshop is as
follows:

TIME TOPIC RESPONSIBLE AGENT

0800-0830 Introduction and Problem Navy Environmental Systems
Statement Program Office

0830-0930 Navy Data Product Development Fleet Numerical Oceanography
and Distribution Centre

0930-1000 Navy C3I Architecture, Industry
Current and Future

1000-1015 Break

1015-1045 Navy Communications Industry
Equipment and Interfaces

1045-1115 Navy Tactical User Naval Eastern Oceanography
Centre

1115-1145 Navy Satellite User Naval Oceanographic and
Atmospheric Research Lab

1145-1215 Navy Data Generation Fleet Numerical Oceanography
Centre

1215-1300 Lunch Invitied Speaker


1300-1530 Technical Paper Presentation Selected Authors


--------------------------------------------------------------------------------

Note: There was also a list of delegates but I am certainly not going to type all THAT in as well!


People

The conference started with the registration and reception. This was a highly charged occasion as many (if not most) people there were meeting everyone else for the first time.

As far as I could tell, there was a solid core of academia (the hard core?) who were surrounded by dozens of curious industry representives most of whom seem to have come to sniff out new people and algorithms to compress their ever-increasing volumes of data. There were also a lot of space and science types there trying to work out what to do with all the signals coming back from out there. Altogether about 256 compressor heads.

Most of the conferences I have attended at the past have been geographically defined and I have found them to be largely a waste of time. Someone gets up an explains his latest lemma in the non-linear theory of complex meta-widgits. Then someone stands up and gives a vague overview of an ongoing 20-person research project. Nobody understands what anyone else is saying so they all get drunk and go home.

In contrast, DCC91 was a remarkably tight conference. Hundreds of people who had never met each other seemed to mix well. The people present were from many backgrounds, but all shared the deep psychological need to make data smaller.

If anything, the major division was between the SIGNALS (who want to compress images, sounds and other signals) and the TEXTS (who want to compress text data) (see section 1.14 of my book for a tight definition of the distinction). These two groups, while sharing the same basic semantic vocablary, sometimes seemed to be on different planets. As far as I could tell there were about 2 SIGNAL delegates for every TEXT delegate. There seemed to be a trend towards image compression. Many TEXTs (including myself) seemed to be a little envious and curious about the techniques so fluently bandied about by the SIGNALS and I think we will see some defections next year. This is a healthy trend, as images are likely to end up taking far more space than text in the long run. Snowbird

I met lots of interesting people. As well as meeting academic greats such as Abraham Lempel and Ian Witten, there was a soup of industry people from many different areas all with different stories to tell. I met an oceanographer who was looking to compress data about the ocean. He could measure the height of the ocean to within a few centimetres. One guy was from a company that manufactures video games. Another was from a company making fax machines. There were several people on satellite data projects. One large software company was there partly to sniff out ways to crunch up programs so as to save on the distribution media. Another was there to find new algorithms for data compression products. One guy was on a project that was going to collect SIX PETAbytes of data -- I had to go and look it up. The scale goes like this:

    10^3  Kilo
    10^6  Mega
    10^9  Giga
    10^12 Tera
    10^15 Peta
    10^18 Exa

You would have about six petabytes of data if you gave half the population of Australia a different compact disk each. However, this would make it very hard for disk jockeys to choose songs so do not attempt this in your own country.


Food

Food at the Cliff Lodge seemed to be the usual combination of fairly high priced restaurants and overcrowded discount snack bars with nothing much in between. There was a reasonably-priced restaurant nearby but one had to wade through the beginners slope to get there. Luckily, one could survive for much of the time on the rather generous snacks presented during the conference registration and poster sessions.

I observed an interesting effect during the (I think) poster session where the hotel served a variety of main-course snack foods and a chocolate cake cut up into slices. The chocolate cake moved slowly at first and then was observed to vanish at an exponentially increasing rate. This could be because:

  1. Most people finished their "main course" and hit the chocolate cake at about the same time.
  2. Perceived worth increases with scarcity.

However, what I think was happening was that everyone had their eye on the chocolate cake, but didn't want to eat any until they had finished their "main course". However, when the cake started disappearing, the prospect of missing out caused lots of people to abandon this ideal in favour of securing some of the scarce resource. So it was (2) with a sort of added criticality thrown in. Maybe we could use some catastrophe theory here. Anyway, it doesn't matter because they brought in another chocolate cake.

As a general rule, the food got better and better as the conference went on.


Patents

One of the dominant underground themes of the conference (at least for me) was PATENTS. As Richard Stallman has pointed out, the situation with software patents is getting on the stupid side. Amazing though it is, there are now software patents covering:

  • Scrolling with multiple subwindows.
  • Exclusive OR highlighted text.
  • Natural order spreadsheet recalculation.
  • Use of backing store to store overlapping parts of windows.

These are just the beginning. Soon, it seems, it will be impossible to write a large computer program without accidentally violating several dozen patents.

The field of data compression is now hot with patents. Starting with the problems with LZW (Unisys wants about $20000 from any manufacturer using it) and Unix compress, we have seen the LZ78 hierarchy almost closed to the public. It is extremely unclear what is covered and what is not.

A key issue here is that there seems to be no TECHNICAL procedure for establishing exactly what a software patent covers. It seems that any company that has a patent coming remotely close to an algorithm in use can successfully launch (if not win) a lawsuit against the user. This environment rules out the use of any algorithm close to a patented algorithm by any company or individual who could not survive a test law case. One result, as we have seen, is the locking up of the LZ78 hierarchy.

I went to the conference expecting to find the answers to the question of what is covered by patents and what is not. Instead I found hundreds of people even more confused than I was. In the twilight hours of the conference dinner I remember sitting at a table with some fairly heavy compressor heads none of whom seemed to have the faintest idea of what was covered by patents - "Only a lawyer can decide" they said.

From my communications before and during the conference my impressions of the patent situation are as follows [05-May-1996: Author accepts no responsibility for these opinions]:

  • The LZ78 class is under challenge. Don't touch it until it is resolved. There was a rumour going around that a certain compressor head heavy had agreed to testify that prior art of LZW existed before Welch. But don't hold your breath.

  • The LZ77 class is basically open. However, there are patents popping up everywhere so get in early or you might find your algorithm gone. [05-May-1996: The LZ77 class is now peppered with patents.]

  • Markov techniques (such as PPM, PPMC, DMC, DHPC, SAKDC, DAFC -- see my book for details) are all open. No problem. Go for it. [05-May-1996: I think this area is still fairly clear of patents, but if I were writing this document again now, I wouldn't phrase it so confidently.]

  • Arithmetic coding is open except for some binary arithmetic codes and some versions that avoid multiplication. [05-May-1996: My understanding is that there are now lots of arthmetic coding patents.]

You can find out more about software patents and their problems from:

   The League for Programming Freedom
   1 Kendall Square #143
   PO Box 9171
   Cambridge MA 02139
   Net: league@prep.ai.mit.edu
   Phone: +1 (617) 243-4091
   Document: "Against Software Patents".
   Document: "Against User Interface Copyright".

[27-Jul-1998: The League For Programming Freedom no longer exists.]

To "raise the consciousness" of participants, James Woods and I handed out league for programming freedom propaganda and buttons (reading "Get Your Lawyers off My Computer"). We received various responses ranging from that of someone who seemed to have just come from the live audience of the Arsenio Hall show ("Hey yeah, give me that badge - yeah, wooo woo wooo, ooh ooh ooh") to the gruff refusal of a guy from a certain big company who had probably come to the conference to flog patent licenses. Gruff refusals were also obtained from people whom we had already bothered three times before - its hard to recognise the people you've already approached out of so many people!!

Most people at the conference seemed to agree that there was a serious problem with the patent situation, but did not quite align with the League for Programming Freedom whose current short term goal is the elimination of all software patents. Nevertheless, it was gratifying to see much of the room wearing the badges by the end of the poster session.


Standards

The conference was abuzz with standards, particularly in the SIGNAL field. Standards for TEXT compression seem to be sparse and confused (Unix compress and MNP5 are the only ones I know of) probably because of the problem with patents. However, the SIGNAL field seems to have lots of standards. In particular, everyone seemed to be talking about a new JPEG standard for image compression and there seemed to be a lot of job opportunities for anyone wanting to get involved with JPEG.


Skiing

I'm sure by now, you're sick of the conference, and so often were the delegates - which was why holding the conference at a ski resort was such a good idea. The conference organizers, being (apparently) avid skiers organized the program so that there was a four hour lunch each day from 12pm to 4pm.

On the Monday afternoon, I fronted up along with a few other compressor heads for the beginners skiing class. Skiing starts on a very small (but fairly steep) learners slope and then progresses to the beginners slope which has a small chairlift. When I saw this chair lift I couldn't believe my eyes as there was no forward guard rail of any kind. One gets hoisted up into the air a good thirty feet (est) with nothing to stop one from falling forward. I am amazed that they can operate the lift day in day out without people falling off all the time and killing themselves.

All went well for the first three hours - I didn't fall (off the skis or the chairlift) once - until just near the end of the session at 4:50pm I let out the throttle a little at the top of the beginners slope and fell over. Not to be discouraged, I got up and kept going but got out of control. The only method of stopping I knew was the snow plough method and it was just not working. As I gained speed, my attention was drawn from attempts to stop to navigation. As I rocketed down towards the end of the beginners slope three options presented themselves:

The Choice
Left: The ski lift. A guard rail, ice and potholes.
Middle: A narrowing flattening run of snow leading to a plaza.
Right: The very beginner's ski slope leading further down (steep).
I chose the middle and it seemed a good choice until the flattenning snow flattened out into a BRICK PLAZA. That's right - the snow turned into bricks. There seemed to be nothing I could do - it all happened so fast. The skis hit the bricks and stopped. Zooming in on the plaza The plaza The safety clamps released and I tumbled forward at high speed onto the brick surface. The skis and poles went clattering everywhere and the crowd of about one hundred having lunch on the plaza let out an amazed WOOOOOA. The moment I stopped I knew I was OK so I gave a grin and the big thumbs up to the crowd who started clapping.

In these situations there is always the little kid. Tradition has it that whenever one comes a cropper skiing, a little kid comes whizzing down the slopes, does a perfect snow spraying stop, and then says: "Gee Mister, Are You OK". I assured him that I was. Later I discovered a couple of blood knees, some bruises, and pants torn at the knees.

This experience put me off skiing for the remainder of my visit (but only just). The thought of giving my presentation in a plaster cast did not appeal to me - and I certainly would have been doing that, I was assured by many people, if the safety clamps on my skis had not activated. Also, I find that I feel basically unsafe with the bottom half of my lower leg locked stiff to a right angled piece of metal and fibreglass; it just feels perfectly set up for a broken leg. Nevertheless, skiing is so much fun that I will probably be at it again sometime, maybe even at DCC'92 if I can get there. [05-May-1996: I got there in 1992 and I did ski!]

ADVICE: Snowbird is a great place to learn how to ski. However, apart from the lessons, one is largely on one's own. If you intend to attend DCC92 and try skiing I suggest that you:

  • Bring some thick explorer socks.
  • Bring a set of gloves (a MUST).
  • Bring some water-resistant clothes.
  • Bring a balaclava
  • Don't forget to plaster on the sun-tan lotion (in particular under the chin where everyone forgets).
  • Make sure your health insurance is up to date.
  • Recommended: "The Inner Game of Skiing", W.Timothy Gallwey and Bob Kriegel, ISBN:0-330-29955-7.

The rest is easily hired. A few people including myself were caught short on some of these details as many people did not even know that they were going to a ski resort. I suggest that you take all the above stuff even if you do not intend to ski as you will probably end up doing so anyway - Snowbird's like that.


Weather

The climate at Snowbird is such that skiing is possible almost all year. During the conference the conditions were excellent.

Balcony snowman Snow was a new thing for me. Most delegates from North America seemed to be highly familiar (if not bored) with it and enjoyed only skiing over the top of it. Having lived most of my life in the Australian heat, I relished the snow itself and found it fun to touch, eat, throw, kick and look at it - the first time in the snow for me in twenty years.

On the (I think) Wednesday it snowed all day and there were four foot snowdrifts everywhere. The snow fell so thick on my balcony that I was able to make a small snowman, with coins for coat buttons and eyes, the drinking glass cover for a hat and icicles for arms. I was amazed at the speed at which icicles grew on everything.


My Paper

I presented my paper "An Extremely Fast Ziv-Lempel Data Compression Algorithm" halfway through the very last session of the very last day (4:50pm Wednesday). Numbers had thinned by this stage as many people had left to catch an evening flight (see ORGANIZATION later) but there were still a reasonable number left. Each presentation (including this one) was 25 minutes including questions.

I was unusually nervous for my presentation (first ever international conference paper presentation) and stuffed it up to a large extent by falling off the podium backwards while attempting to point to an overhead transparency, by muddling the slides, and by running at first undertime and then overtime. Despite this comedy relief, I think I got my message across.

One interesting aspect of the podium was that it had TWO overhead transparency projectors. This presented at least three options to speakers:

  • Ignore one projector: the conventional approach.
  • Switch between them (thus enabling enthusiastic members of the audience twice as long to jot things down).
  • Use one for reference material, the other for main presentation.

I chose the third option, using one projector to display "subliminal advertising" which I changed every few minutes during my talk:

   Subliminal advertisement #1: BUY MY BOOK.
   Subliminal advertisement #2: DONT PATENT SOFTWARE.
   Subliminal advertisement #3: READ COMP.COMPRESSION.

and the other for the normal stuff. Despite the abundance of projectors, there was no table space on which to put things. Just a small metal tray on the side of each projector. This was very frustrating and made manipulating the slides for presentation difficult. I hope that this can be fixed for next year.

People seemed pleased with the practicality of my paper ("we love your paper - it's actually got CODE in it"!!!). Many delegates from industry seemed put off by all the mathematics and theoreticalness of other work. However, my glory was short lived as, after my presentation, Timo Raita strolled up and informed me of an even faster algorithm of 1987. This had me worried for a few days until I tried it out in Boston and found that it yielded 7% absolute worse compression. The competing algorithm still goes faster (compressing - slower decompressing) and the question mark of my alternative title "The World's Fastest Adaptive Text Compression Algorithm?" turned out to be spot on. A lesson in humility. For those who are interested, my algorithm (which still holds a minimum point on the compression/speed performance curve [05-May-1996: I don't know if this is still true]) can be obtained by FTP access from [05-May-1996: The FTP address has changed since this document was written. These are the new FTP addresses.]:

As a side note my book "Adaptive Data Compression" (ISBN: 0-7923-9085-7) is available for US$75 from

   Kluwer Books
   101 Philip Drive
   Assinippi Park
   Norwell MA 02061
   USA
   Ph: +1 (617) 871-6300
   Fx: +1 (617) 871-6528
   Nt: kluwer@world.std.com

[27-Jul-1998: See the Thesis Book page for up-to-date details and online ordering.]


Thursday

By Thursday, most delegates had gone home although a few popped up here and there. I didn't attend the NASA/NAVY workshops but I peeked in and there seemed to be about fifty people.


Organization

A snow laden tree In general, the conference was excellently organized. Good organization is often not noticed because it manifests itself in the ABSENCE of stuffups and as far as I could tell, there were very few (if any) stuffups in DCC91. In particular, the conference proceedings were published in book form which was very neat and better than the usual 400 page loosely bound mountain one is usually lumbered with.

There was a bit of a fuss about the scheduling of the last session, as at least one delgate had booked an early evening flight and had to leave before their presentation slot. Throughout the conference there was fairly intense lobbying to move the final session forward into the four hour lunch break. It seems that the majority of delegates wanted the final session moved back. However, the conference organizers wouldn't hear of it. This caused some minor bad feeling. The conference organizers also came under fire for (apparently) booking the place for next year without telling anyone. Certainly Snowbird ski resort was a superb location for the conference and the organizers should be congratulated. However, there are many other superb locations in the world (and many other sports (I like skydiving so let's have it at Perris Valley!!!!)) and it seems only fair to move the conference around a bit. Maybe this can happen after the conference has attained a two-year identity.[05-May-1996: The conference is now well and truly established at Snowbird.]


Proceeedings

As I understand it, the conference proceedings have been published by the IEEE and you can obtain a copy ("DCC91 proceedings") from:

   IEEE Computer Society
   PO Box 3014
   10662 Los Vaqueros Circle
   Los Alamitos CA 90720-1264
   USA
   Ph: +1 (714) 821-8380

The proceedings are in the form of a small, strongly bound book and is essential reading for compressor heads. It may also be possible to obtain a list of the papers presented and then individual reprints.


Cost

This is roughly how my costs came out which should give a good idea for those thinking of attending next year.

     Registration : About US$300
     Accommodation: About US$ 90/night.
     Ski rental   : About US$ 20/day.
     Ski School   : About US$ 25/afternoon.
     Breakfast    : About US$ 10 (in restaurant).
     Dinner       : About US$ 25 (in restaurant).


Summary

A VERY successful conference. Congratulations to the organizers not only for organizing it so well but for thinking of having such a conference in the first place. If you have an interest in data compression or skiing and can possibly attend DCC'92 then try to do so.

This has been a very informal conference report. I had fun writing it. Please read it in the spirit in which it was written. Apologies in advance for omitting any obviously essential information or for offended anyone.

Enjoy,

Ross Williams
20 May 1991.

webmaster@ross.net
Copyright © Ross N. Williams 1996-1997. All rights reserved.