dbm/file hashing techniques

[Jerry Leichter]

A while back, I answered a question in net.unix-wizards about the algorithms
used in dbm.  I offered to put together a set of references if people were
interested.  One or two people responded; then there was a large pause, which
was apparently caused by decvax problems, as I've received several requests in
the last two days.  So, below you will find the bibliography.

I have also gotten requests for copies of the original note, which seems to
have gotten eaten on the way to some sites by the greater munger of the net.
Unfortunately, I didn't keep a copy and it has already disappeared from our
spool files.  If anyone out there still has a copy, some of your colleagues
would appreciate it if you put on a non-blank first line - if it has a blank
first line - and re-posted it.

							-- Jerry
						decvax!yale-comix!leichter
						leichter at yale

--------------------------------------------------------------------------
		Bibliography on file hashing techniques

The fundamental paper is:

"Extendible Hashing - A Fast Access Method for Dynamic Files", Fagin, Niever-
gelt, Pippenger, Strong.  TODS V4#3 (Sept. 1979) pgs 315-344.

That paper has a bibliography that's a good starting point for finding all older
work.  A couple of relevent papers (some may be listed in that bibliography; I
haven't checked):

"Universal Classes of Hash Functions" (extended abstract), Carter and Wegman,
Proc. 9th SIGACT (1977).  [This one is hard to find.  I don't know if a full
version was ever published.]

"Organization of Efficient Access by Hashing", A.D. Astakhov.  Programming
and Computer Software (A translation of @i(Prorammirovanie)) V6#3, May-June
1980, pgs 141-144.  [An overview of related work; little detail.]

"Dynamic Hashing", Larson.  BIT 18(1978) 184-201

"Virtual Hashing:  A Dynamically Changing Hashing", Litwin.  Proc. Very Large
DB Conf. 1978 pgs 517-523.

"Tightly Controlled Linear Hashing Without Separate Overflow Storage",
Mullin, BIT 21 (1981) pgs 390-400.

"New File Organizations Based on Dynamic Hashing", Scholl, TODS V6#1 (March
1981) pgs 194-211.

"Order Preserving Extendible Hashing and Bucket Tries", Tamminen, BIT 21
(1981) 419-435.

"Analysis of a Universal Class of Hash Functions", Markowsky, Carter, Wegman.
In "Lecture Notes on Computer Science 64 (1978)" (Springer-Verlag).  [Gives
a simple, implementable class of such functions.]

A very recent paper with applications to construction of hash functions:

"How to Construct Random Functions", Goldreich, Goldwasser, Micali.  MIT/LCS
TM 244.  [I have a pre-print, with the TM # written on it; it may not be
accurate.]

-------------
These listings are from my files.  I have seen other articles in recent jour-
nals to which I subscribe (CACM? TOPLAS?), so I didn't make copies, and now
I can't find them easily.  If you are seriously interested in this area, a
literature search for papers written in the last 3 years would be worth your
while; if you do this, I would be interested in the results!  (I believe there
have been articles in BIT other than the ones I listed above, BTW.)