leichter@yale-com.UUCP (Jerry Leichter) (01/31/84)
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@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.)