Re: Data Compression

["D.F.S." <dfs@xmission.com>]

Several disclaimers up front:
I didn't write fplan, and would not want to in any way
detract from the great work done there.

Secondly, I have no real reason to push compression if it is not
an advantage, that is yet to be seen.

Thirdly, I would not expect someone to retrofit existing programs.

My vision was more along the lines of the fact we could easily
fit this ENTIRE huge database of info that was shipped on a CD into
maybe 10-15 megabytes.
With that handy, The number and variety of programs, that could 
provide a wealth of info we have not even envisioned yet, is huge.


A couple of points as well.

The decompression code I mentioned is VERY fast.
15-16 Meg/Second on a 155 Mhz Pentium.

On some machines with a fast CPU it will be faster to decompress
the data on the fly than to read it straight from the disk.
The simple reason is with a good compression ratio, the time it
would take to read 4,5,8.. 12? times as much data from the disk 
would take a lot longer than the realtime decompression.

Modern consumer disks don't average sustained thruput much over 
8 Meg/Second last I saw..
If you Read for 1 second, get 8 meg of data and uncompress it
at a 5-1 ratio, that is:
40 meg of data in (1+2.5)=3.5 seconds
Read 40 Meg of data at 8 Meg/Sec, 5 Seconds.

This is moot for random access, so a shift in the approach
would be required.

>    A general comment about database compression. Note that in the
> case of the fplan databases, the records are padded to fixed lengths so
> that a binary search can be used for the lookup by identifier. (See
> Knueth or other texts for a description of the algorithm). The binary
> search is *very* fast compared to a simple search by sequential read.
> This is one feature that made fplan quite unique when it first came out
> in 1989. It actually ran *fast* on the PC's of that era...

Do you mean a Binary Tree type Search?

I'm not being sarcastic or snotty either, IF you are not talking 
about Binary or Btree searches, look into it. there are Huge
advantages.

I HOPE so, I presume so from your description.

You are talking about a single Column or variable here.
At least that is all you mentioned.
I would presume you would also need to search on Lat/Lon 
values as well?
That is not possible with the approach you mentioned, IE.
The records are stored sorted be the identifier.

The usual approach is to build an index and point it back at the
file containing the data.

This has several advantages:
You are not wasting all that space keeping fixed length records.

The indexes themselves can be kept in memory or easily be
cached by any decent modern OS.

You can search on many different parameters.

In the case in question, that data can be compressed.


Aren't there about 8K airports?
4 char Identifier and a 16 bit "Pointer" ~50K bytes to index
the entire airport database.

> 
>   The problem with runtime de-compression is that fseek() is not
> fast (or even possible?) and it is crucial in the implementation of
> any fast search algorithm. My point is that you probably don't want to
> bother with compression on a desktop setup where disk space really
> isn't an issue.  The speed penalty you would pay by giving up fast
> searching algorithms isn't worth the space savings in a world where
> 5-10 GB drives are common place. Of course, it DOES make sense if we
> are talking about a handheld or other environment where space is a
> premium. Just my $0.02 ....

I see your point, depending on the platform.

MY original point, and maybe a bad presumption, but one I'll stand by
is that many of these systems could easily be running on hacked
3/486 Laptops running linux permanently mounted, as much as is legal,
in the planes probably even with the screens removed, repackaged and
mounted on the yoke or panel, with velco of course.

Something I do in an instant with a $50-$75 laptop with a 400 Meg disk.

Something I'd not do with my $2,500 new laptop with a 10 Gig disk which
I use and depend on daily to make a living.

That was the perspective I was coming from, the ability to dedicate
trailing edge technology to a specific use in the plane. 

Even trailing edge technology is incredibly advanced compared to
anything currently installed in GA planes aside from the
latest generation of GPS Navigation systems.

Using a laptop in a plane is a pain in the butt from my experience.

A screen mounted someplace so you can see it but not have to hold it
and one of those trackballs built for laptops stuck to the yoke
along with software designed to be run 100% with the mouse would be
a world apart.

Marc


-
Archives of linux-aviation: http://mail.nl.linux.org/lists/linux-aviation/
To unsubscribe: send the command "unsubscribe linux-aviation" in the body
of a mail message to <Majordomo@mail.nl.linux.org>.