ross@spam.ua.oz.au (Ross Williams) (05/20/91)
Data Compression Conference 1991 (DCC'91): The Unauthorized Report
==================================================================
Author : Ross Williams (ross@spam.ua.oz.au)
Date : 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 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 PROGRAM
------------------
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 program.
Note: My commentary continues after the program...
--------------------------------------------------------------------------------
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].
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 delagates 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.
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:
* 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.
* Markov techniques (such as PPM, PPMC, DMC, DHPC, SAKDC, DAFC -- see
my book for details) are all open. No problem. Go for it.
* Arithmetic coding is open except for some binary arithmetic codes and
some versions that avoid multiplication.
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".
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:
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. 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.
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.
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:
1 Ignore one projector: the conventional approach.
2 Switch between them (thus enabling enthusiastic members of the audience
twice as long to jot things down).
3 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) can be obtained by FTP access from:
Machine : sirius.itd.adelaide.edu.au (129.127.40.3)
Directory : pub/misc
Files : lzrw1.c lzrw1.68000.
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
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
------------
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.
PROCEEDINGS
-----------
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
ross@spam.ua.oz.aubrad@looking.on.ca (Brad Templeton) (05/21/91)
A brief hint for those planning to order the conference proceedings. They are $100 for non-members, $50 for IEEE computer society members. Membership, on the other hand, is only $27 for the rest of the year, so the choice is pretty obvious.... -- Brad Templeton, ClariNet Communications Corp. -- Waterloo, Ontario 519/884-7473
thomsen@spf.trw.com (Mark R. Thomsen) (05/22/91)
Ross Williams writes
Data Compression Conference 1991 (DCC'91): The Unauthorized Report
... skip a bunch of good stuff ...
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.
... skip a bunch more good stuff ...
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.
... skip a little more good stuff ...
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.
... skip a whole bunch more good stuff ...
Enjoy,
Ross Williams
ross@spam.ua.oz.au
Three years ago I learned the term 'petabyte' in conjunction with EOS.
This NASA program will be collecting 1 terabyte per day, every day, for
over a decade. This massive collection is to support the actual measure-
ment and study of environmental phenomena, e.g., is it getting warmer
and what are all of the dynamics of clouds, mosture, wind, etc.? This
undertaking will stretch a number of technical fields including data
compression. Lossless compression for scientific data is extremely
important - those least significant bits might contain the key informa-
tion, which may not be known until years after collection when the
state-of-the-art and attention span catch up. Lossy compression for
browsing (window shopping) the massive archives across these very same
networks will have a role too.
Image compression and n-dimensional data array compression will evolve
rapidly as earth science becomes more of a national priority. The amount
of data and the number of people needing/wanting access will drive this
technology. Researchers and the conversations I watch here will be quite
important, IMHO.
Thanks for the report. I think you are right - signals (images, data
arrays) will evolve into an important part of compression R&D.
Mark R. Thomsen
TRWsean@ms.uky.edu (Sean Casey) (05/26/91)
brad@looking.on.ca (Brad Templeton) writes: |A brief hint for those planning to order the conference proceedings. |They are $100 for non-members, $50 for IEEE computer society members. |Membership, on the other hand, is only $27 for the rest of the year, |so the choice is pretty obvious.... $100??????????? Geez, what are they printed on, gold leaf? -- ** Sean Casey <sean@s.ms.uky.edu>
brad@looking.on.ca (Brad Templeton) (05/26/91)
They could have reduced the price of the book by compressing the text with a good C-W compressor and spewing out the bits, of course! -- Brad Templeton, ClariNet Communications Corp. -- Waterloo, Ontario 519/884-7473