|
The Collection of Computer Science Bibliographies |
|
| Up: Bibliographies on Theory/Foundations of Computer Science | Collection Home |
[ About | Browse | Statistics ]
| Number of references: | 1585 | Last update: | January 26, 2004 |
|---|---|---|---|
| Number of online publications: | 80 | Supported: | yes |
| Most recent reference: | September 2003 | Info: | Version 1.29 |
| Information on the Bibliography |
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).
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.
| Browsing the bibliography |
| Bibliographic Statistics |
|
Please direct comments regarding the bibliography collection
to <liinwwwa@ira.uka.de>.
This page is part of the Computer
Science Bibliography Collection. |