NewsSpeak

[Mark S. Miller <mark>]

Date: Tue, 29 Aug 89 19:34:44 PDT
   From: michael (Michael McClary)

   ...

   By the way,

   >   "Any filing system slows down some as you add more information.

   isn't strictly quite true.  There's "perfect hash".  It doesn't slow down
   at all.  Trouble is, you have to chose the hash function with total knowlege
   of what you're storing.  This means enormous amounts of computation when
   you add one unexpected thing to the data base, and must chose a new hash
   function and reorganize the entire data base to match.

I believe the extensible hashing algorithms in the literature (the
ones Mr. Hill is researching) are constant time to access & constant
time to store a new record (or overwrite an existing one).  And this
constant time averages much closer to one disk seek than two.

Obviously, this doesn't mean we aren't doing magic.  We are doing
operations which extensible hash tables (or any other publicly known
data structure) can't do efficiently, and we do so with the
performance characteristics you outline.  The remaining rhetorical
problem is how to distinguish these kinds of problems without loosing
most people, or making it seem like a set of distinctions which
artificially load the dice in our favor.

Btw, I also liked the NewsSpeak alot.  I'd do Esther Dyson very
differently if I had it to do over again.