Nelson H. F. Beebe <beebe @ math . utah . edu (Internet)> (email mangled to prevent spamming)
Center for Scientific Computing Department of Mathematics University of Utah Salt Lake City, UT 84112 USA
Abstract:
This bibliography records publications on the subject of hashing, i.e., algorithms for lookup of keys in large lists in (on average) constant time. For static collections of text, such as data on CD ROMs, minimal perfect hash functions are of considerable interest, and the reader's attention is drawn to the important breakthroughs represented by the work of E. Fox and collaborators (1988–1992), which now permit derivation of hash functions for collections of millions of keys, instead of at most a few hundred with the methods of earlier work. Witten, Moffat, and Bell (Witten:1994:MGC) describe very recent work on minimal ordered perfect hash functions, that is, ones in which entries are stored in some predefined order, such as alphabetical; this makes enumeration of a sorted key list trivial. The methods of their book are implemented in software (retrievable on the Internet) for solving the full text search problem: given a word, or word, find all documents in a large collection that contain that word. Their software also supports Boolean search (find A and B or C and not D), and query ranked search (given a list of several words, find documents containing them, and rank them by the number of matches).
Keywords:
hashing
Author Comments:
These references have been extracted from a very large computer science bibliography collection on ftp.ira.uka.de in /pub/bibliography to which many people of have contributed. The snapshot of this collection was taken on 5-May-1994, and it consists of 441 BibTeX files, 2,672,675 lines, 205,289 entries, and 6,375 <at>String abbreviations, occupying 94.8MB of disk space. Regrettably, the quality of many of those bibliography files is low, with incomplete bibliographic data (missing author initials, page numbers, titles, proceedings cross-references, ....) and spelling and typing errors. Also, because the collection came from many sources, there is much duplication, and I had to spend much longer than I expected identifying duplicates, and merging them manually into single entries with maximal bibliographic information. I have corrected all spelling errors that I could identify with the help of two separate spelling programs, though this is difficult with multi-lingual text. The list of spelling exceptions (i.e. words believed to be correctly spelled, but absent from the spelling program dictionaries) is kept in the companion file, hash.sok. I have supplied publisher, ISBN, LCCN, page number data to the extent possible with the resources of the U.S. Library of Congress catalog, and other university catalogs accessible on the Internet, particularly the University of California MELVYL catalog, and the Stanford University RLIN catalog (thanks to the willow software from the University of Washington). Their availability is gratefully acknowledged. For books published since 1972, when the International Standard Book Numbering system was introduced, ISBNs are particularly important, because they are unique numbers that identify the country group, publisher, and book; bookstores routinely request ISBNs from their customers. More than 235 of these references are papers in conference proceedings, and regrettably, for about 30 of them, I have been unable to locate an exact reference to the conference volume in the various on-line library catalogs that I consulted. This is disappointing, because it suggests that the papers will be largely inaccessible. Missing data are indicated throughout by question marks. Approximately a third of the bibliographic entries contain them, sigh... I will be very grateful to users of this bibliography who can supply me with corrected conference proceedings data for future editions of this bibliography, as well as for new entries. Despite the very large collection from which this data was extracted, more than half of the papers in my personal files of papers on hashing were absent from that collection. Also, most of the references from Knuth's exhaustive study (Knuth:1973:ACP), and from the books by Vitter and Chen (Vitter:1987:DAC), Pieprzyk and Sadeghiyan (Pieprzyk:1993:DHA), and Devroye (Devroye:1986:LNB) were absent, and have been included below. Because of my dissatisfaction with the completeness of many of these entries, I have assigned a major version number of 0 to this bibliography, rather than the more usual 1. A substantial amount of updating work remains to be done to remedy this situation, and bring this bibliography up to the standards which should be expected of professionals in the field. This bibliography is nevertheless being made available in its present state in the belief that it will be useful to many people.
