%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "2.23", %%% date = "08 July 2008", %%% time = "08:47:57 MDT", %%% filename = "hash.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% checksum = "05732 39216 183034 1660651", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "bibliography, BibTeX, hashing", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This bibliography records publications on %%% the subject of hashing, i.e., algorithms for %%% lookup of keys in large lists in (on %%% average) constant time. %%% %%% At version 2.23, the year coverage looks %%% like this: %%% %%% 1939 ( 2) 1962 ( 1) 1985 ( 81) %%% 1940 ( 0) 1963 ( 8) 1986 ( 70) %%% 1941 ( 0) 1964 ( 1) 1987 ( 57) %%% 1942 ( 0) 1965 ( 1) 1988 ( 84) %%% 1943 ( 0) 1966 ( 0) 1989 ( 113) %%% 1944 ( 0) 1967 ( 0) 1990 ( 98) %%% 1945 ( 0) 1968 ( 5) 1991 ( 97) %%% 1946 ( 0) 1969 ( 6) 1992 ( 85) %%% 1947 ( 0) 1970 ( 9) 1993 ( 110) %%% 1948 ( 0) 1971 ( 7) 1994 ( 102) %%% 1949 ( 0) 1972 ( 12) 1995 ( 63) %%% 1950 ( 1) 1973 ( 17) 1996 ( 39) %%% 1951 ( 0) 1974 ( 21) 1997 ( 25) %%% 1952 ( 0) 1975 ( 23) 1998 ( 18) %%% 1953 ( 3) 1976 ( 18) 1999 ( 20) %%% 1954 ( 0) 1977 ( 26) 2000 ( 4) %%% 1955 ( 0) 1978 ( 23) 2001 ( 7) %%% 1956 ( 1) 1979 ( 30) 2002 ( 20) %%% 1957 ( 1) 1980 ( 37) 2003 ( 9) %%% 1958 ( 1) 1981 ( 35) 2004 ( 12) %%% 1959 ( 1) 1982 ( 57) 2005 ( 19) %%% 1960 ( 0) 1983 ( 76) 2006 ( 6) %%% 1961 ( 1) 1984 ( 68) 2007 ( 1) %%% 19xx ( 7) %%% %%% Article: 850 %%% Book: 99 %%% InCollection: 5 %%% InProceedings: 324 %%% Manual: 5 %%% MastersThesis: 11 %%% Misc: 4 %%% PhdThesis: 16 %%% Proceedings: 200 %%% TechReport: 121 %%% Unpublished: 4 %%% %%% Total entries: 1639 %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% This bibliography is sorted by year, and %%% within each year, by author and title key, %%% with ``bibsort -byyear''. Year order has %%% been chosen to make it easier to identify %%% the most recent work. Cross-referenced %%% proceedings entries appear at the end, %%% because of a restriction in the current %%% BibTeX. %%% %%% 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). %%% %%% 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 %%% String{} abbreviations, occupying 94.8MB %%% of disk space. %%% %%% At version 0.34, about 65 new entries were %%% added from a search of the OCLC Article1st %%% database, and another 60 existing entries %%% were updated with new information. At version %%% 0.37, another 46 entries were added from a %%% search of the OCLC Proceedings database. %%% %%% At version 0.56, a search of the Compendex %%% databases (1970--1996) added 185 new %%% entries, and provided additional data %%% for many other entries. %%% %%% 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 %%% with extension .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. %%% %%% Journal, organization, and publisher names, %%% and publisher addresses, have all been %%% replaced by consistent abbreviations of the %%% form j-xyz, org-xyz, pub-xyz, and %%% pub-xyz:adr. The variation in spelling and %%% abbreviation in the original data was %%% distressingly large. %%% %%% LCCN (Library of Congress Call Numbers) are %%% given wherever applicable, because they are %%% widely used by libraries in the United %%% States and possibly elsewhere. Please note %%% that these are letter-digit-year %%% combinations like QA76.9.D35 D48 1986, %%% rather than the field LCCN: 85-26850 r91 %%% which appears in Library of Congress %%% catalog entries, and is an internal number %%% of apparent little use elsewhere. %%% %%% 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. %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{ "\hyphenation{ Chris-to-dou-la-kis Fach-ge-sprach feh-ler-be-hand-lung feh-ler-er-ken-nung Han-over Jean-ette Mann-heim Piep-rzyk Reuh-ka-la Rus-in-kie-wicz Sa-degh-i-yan Worm-ald zu-griffs-ver-fahr-en }" } %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Institutional abbreviations: @String{inst-BROWN-CS = "Department of Computer Science, Brown University"} @String{inst-BROWN-CS:adr = "Providence, RI, USA"} @String{inst-CSC = "Center for Scientific Computing and Department of Mathematics, University of Utah"} @String{inst-CSC:adr = "Salt Lake City, UT 84112, USA"} @String{inst-HARVARD-CRCT = "Centre for Research in Computing Technology, Harvard University"} @String{inst-HARVARD-CRCT:adr = "Cambridge, MA"} @String{inst-IBM = "IBM Corporation"} @String{inst-IBM:adr = "San Jose, CA, USA"} @String{inst-MANCHESTER-CS = "Department of Computer Science, University of Manchester"} @String{inst-MANCHESTER-CS:adr = "Manchester, UK"} @String{inst-MIT-AI = "Massachusetts Institute of Technology, A. I. Lab."} @String{inst-MIT-CS = "Massachusetts Institute of Technology, Computer Science Lab."} @String{inst-MIT:adr = "Cambridge, Massachusetts"} @String{inst-PRINCETON-CS = "Department of Computer Science, Princeton University"} @String{inst-PRINCETON-CS:adr = "Princeton, NJ, USA"} @String{inst-PURDUE-CS = "Department of Computer Science, Purdue University"} @String{inst-PURDUE-CS:adr = "West Lafayette, IN, USA"} @String{inst-STANFORD = "Stanford University"} @String{inst-STANFORD:adr = "Stanford, CA, USA"} @String{inst-UC-BERKELEY-ICSI = "International Computer Science Institute"} @String{inst-UC-BERKELEY-ICSI:adr = "Berkeley, CA, USA"} @String{inst-VIRGINIA-POLY-CS = "Department of Computer Science, Virginia Polytechnic Institute and State University"} @String{inst-VIRGINIA-POLY-CS:adr = "Blacksburg, VA 24061-0106, USA"} @String{inst-WATERLOO-CS = "Department of Computer Science, University of Waterloo"} @String{inst-WATERLOO-CS:adr = "Waterloo, Ontario, Canada"} %%% ==================================================================== %%% Journal abbreviations: @String{j-ACTA-INFO = "Acta Informatica"} @String{j-ADA-LETT = "Ada Letters"} @String{j-ADV-SOFT-SCI-TECH = "Advances in software science and technology"} @String{j-AEU = "AEU: Archiv f{\"u}r Elektronik und Ubertragungstech"} @String{j-ALGORITHMICA = "Algorithmica"} @String{j-AMER-MATH-MONTHLY = "American Mathematical Monthly"} @String{j-ANG-INFO = "Angewandte Informatik"} @String{j-ANN-OPER-RESEARCH = "Annals of Operations Research"} @String{j-APPL-MATH-LETT = "Applied Mathematics Letters"} @String{j-AUSTRALIAN-COMP-J = "Australian Computer Journal"} @String{j-BIT = "BIT (Nordisk tidskrift for informationsbehandling)"} @String{j-BYTE = "Byte Magazine"} @String{j-C-PLUS-PLUS-REPORT = "C++ Report"} @String{j-CACM = "Communications of the Association for Computing Machinery"} @String{j-CCCUJ = "C/C++ Users Journal"} @String{j-COMBINATORICA = "Combinatorica"} @String{j-COMP-ART-INTELL = "Computers and Artificial Intelligence = Vychislitel'nye mashiny i iskusstvennyi intellekt"} @String{j-COMP-AUTO = "Computers and Automation"} @String{j-COMP-BULL = "The Computer Bulletin"} @String{j-COMP-COMM = "Computer Communications"} @String{j-COMP-COMM-REV = "Computer Communication Review"} @String{j-COMP-GRAPHICS = "Computer Graphics"} @String{j-COMP-J = "The Computer Journal"} @String{j-COMP-LANG-MAG = "Computer Language Magazine"} @String{j-COMP-MATH-APPL = "Computers and Mathematics and Applications"} @String{j-COMP-NET-AMSTERDAM = "Computer Networks (Amsterdam, Netherlands: 1999)"} @String{j-COMP-PHYS-COMM = "Computer Physics Communications"} @String{j-COMP-SURV = "ACM Computing Surveys"} @String{j-COMP-SYS = "Computing Systems"} @String{j-COMP-TECH-REV = "Computer Technology Review"} @String{j-COMP-VIS-IMAGE-UNDERSTANDING = "Computer vision and image understanding: CVIU"} @String{j-COMPUT-ELECTRON-AGRIC = "Computers and Electronics in Agriculture"} @String{j-COMPUT-METH-PROG-BIOMED = "Computer Methods and Programs in Biomedicine"} @String{j-COMPUT-SECUR = "Computers and Security"} @String{j-COMPUTER = "Computer"} @String{j-COMPUTERWORLD = "ComputerWorld"} @String{j-COMPUTING = "Computing"} @String{j-CONG-NUM = "Congressus Numerantium"} @String{j-CRYPTOBYTES = "CryptoBytes"} @String{j-CRYPTOLOGIA = "Cryptologia"} @String{j-CUJ = "C Users Journal"} @String{j-CVGIP-IU = "Computer Vision, Graphics, and Image Processing. Image Understanding"} @String{j-DATA-KNOWLEDGE-ENG = "Data and Knowledge Engineering"} @String{j-DBMS = "DBMS"} @String{j-DDJ = "Dr. Dobbs Journal"} @String{j-DESIGNS-CODES-CRYPTOGR = "Designs, Codes, and Cryptography"} @String{j-DISCRETE-APPL-MATH = "Discrete Applied Mathematics"} @String{j-DOKL-AKAD-NAUK = "Doklady Adak. Nauk SSSR"} @String{j-EL-COMM-LAB = "Rev. of the El. Commun. Lab."} @String{j-ELECT-COMM-JAPAN-3-FUND-ELECT-SCI = "Electronics and communications in Japan. Part 3, Fundamental electronic science"} @String{j-ELECT-LETTERS = "Electronics Letters"} @String{j-ELECTRONIC-DESIGN = "Electronic Design"} @String{j-EUR-J-COMB = "European Journal of Combinatorics"} @String{j-EUR-TRANS-TELECOMM = "Eur. Trans. Telecommun. Relat. Technol."} @String{j-FORM-METHODS-SYST-DES = "Formal Methods in System Design"} @String{j-FORTH-DIMENSIONS = "Forth Dimensions"} @String{j-FSTTCS = "Foundations of Software Technology and Theoretical Computer Science"} @String{j-IBM-JRD = "IBM Journal of Research and Development"} @String{j-IBM-SYS-J = "IBM Systems Journal"} @String{j-IBM-TDB = "IBM Technical Disclosure Bulletin"} @String{j-IEE-PROC-E = "IEE proceedings, E: Computers and digital techniques"} @String{j-IEEE-COMPUT-SCI-ENG = "IEEE Computational Science \& Engineering"} @String{j-IEEE-INT-SYMP-INF-THEORY = "IEEE International Symposium on Information Theory"} @String{j-IEEE-J-SEL-AREAS-COMMUN = "IEEE Journal on Selected Areas in Communications"} @String{j-IEEE-MICRO = "IEEE Micro"} @String{j-IEEE-PROC = "IEEE Proceedings"} @String{j-IEEE-SEC-PRIV = "IEEE Security \& Privacy"} @String{j-IEEE-SOFTWARE = "IEEE Software"} @String{j-IEEE-TIT = "IEEE Transactions on Information Theory"} @String{j-IEEE-TRANS-COMM = "IEEE Trans. Comm."} @String{j-IEEE-TRANS-COMPUT = "IEEE Transactions on Computers"} @String{j-IEEE-TRANS-INF-THEORY = "IEEE Transactions on Information Theory"} @String{j-IEEE-TRANS-KNOWL-DATA-ENG = "IEEE Transactions on Knowledge and Data Engineering"} @String{j-IEEE-TRANS-NETWORKING = "IEEE\slash ACM Transactions on Networking"} @String{j-IEEE-TRANS-PAR-DIST-SYS = "IEEE Transactions on Parallel and Distributed Systems"} @String{j-IEEE-TRANS-PATT-ANAL-MACH-INTEL = "IEEE Transactions on Pattern Analysis and Machine Intelligence"} @String{j-IEEE-TRANS-SOFTW-ENG = "IEEE Transactions on Software Engineering"} @String{j-IEEE-TRANS-SYST-MAN-CYBERN = "IEEE Trans. Systems, Man, and Cybernetics"} @String{j-IEICE-TCEIS = "IEICE Transactions on Communications\slash Electronics\slash Information and Systems"} @String{j-IEICE-TRANS-FUND-ELECT= "IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences"} @String{j-IND-MATH = "Industrial Mathematics"} @String{j-INF-CONTROL = "Information and Control"} @String{j-INF-TECH-RES-DEV-APPL = "Inf. Tech. Res. Dev. Appl."} @String{j-INFO-PROC-LETT = "Information Processing Letters"} @String{j-INFO-SCI = "Information sciences"} @String{j-INFO-SOFTWARE-TECH = "Information and Software Technology"} @String{j-INFO-SYS = "Information system"} @String{j-INT-J-COMPUT-INF-SCI = "International Journal of Computer and Information Sciences"} @String{j-INT-J-COMPUT-MATH = "International Journal of Computer Mathematics"} @String{j-INT-J-COMPUT-SYST-SCI-ENG = "International Journal of Computer Systems Science and Engineering"} @String{j-INT-J-ELECTRON = "International Journal of Electronics Theoretical \& Experimental"} @String{j-INT-J-FOUND-COMP-SCI = "International Journal of Foundations of Computer Science"} @String{j-INT-J-ROBOTICS-RES = "International Journal of Robotics Research"} @String{j-INTEGRATION-VLSI-J = "Integration, the VLSI journal"} @String{j-ISR = "Information Storage and Retrieval"} @String{j-J-ACM = "Journal of the Association for Computing Machinery"} @String{j-J-ALG = "Journal of Algorithms"} @String{j-J-AM-SOC-INF-SCI = "Journal of the American Society for Information Science"} @String{j-J-AUTO-REASON = "Journal of Automated Reasoning"} @String{j-J-CHEM-INFO-COMP-SCI = "Journal of Chemical Information and Computer Sciences"} @String{j-J-CHINESE-INST-ENG = "Journal of Chinese Institute of Engineers"} @String{j-J-COMB-DES = "Journal of Combinatorial Designs"} @String{j-J-COMB-THEORY-A = "Journal of Combinatorial Theory (Series A)"} @String{j-J-COMP-SYS-SCI = "Journal of Computer and System Sciences"} @String{j-J-COMPUTATIONAL-CHEM = "Journal of Computational Chemistry"} @String{j-J-CRYPTOLOGY = "Journal of Cryptology"} @String{j-J-DATABASE-ADM = "J. Database Adm."} @String{j-J-DOC = "Journal of Documentation"} @String{j-J-ELISHA-MITCHELL-SCI-SOC = "Journal of the Elisha Mitchell Scientific Society"} @String{j-J-INF-PROCESS = "Journal of the Information Processing Society of Japan"} @String{j-J-INFO-ENG = "Journal of Information and Engineering"} @String{j-J-PAR-DIST-COMP = "Journal of Parallel and Distributed Computing"} @String{j-J-PAS-ADA-MOD = "Journal of Pascal, Ada and Modula-2"} @String{j-J-SYST-SOFTW = "The Journal of Systems and Software"} @String{j-J-UCS = "J.UCS: Journal of Universal Computer Science"} @String{j-LAB-MICROCOMP = "Laboratory microcomputer"} @String{j-LECT-NOTES-COMP-SCI = "Lecture Notes in CS"} @String{j-LINUX-J = "Linux Journal"} @String{j-MAPLE-TECH-NEWS = "Maple Technical Newsletter"} @String{j-MATH-MAG = "Mathematics Magazine"} @String{j-MATH-RECR-ESSAYS = "Mathematical Recreations and Essays"} @String{j-MATH-SYS-THEORY = "Mathematical Systems Theory"} @String{j-MICROCOMPUT-APPL = "Microcomputer Applications"} @String{j-MICROPROC-MICROPROG = "Microprocessing and Microprogramming"} @String{j-NAMS = "Notices of the American Mathematical Society"} @String{j-NEURAL-NETWORKS = "Neural Networks"} @String{j-NEW-GEN-COMP = "New Generation Computing"} @String{j-OPER-RES-LETT = "Operations Research Letters"} @String{j-OPER-SYS-REV = "Operating Systems Review"} @String{j-ORSA-J-COMPUT = "ORSA Journal on Computing"} @String{j-PARALLEL-ALGORITHMS-APPL = "Parallel Algorithms and Applications"} @String{j-PARALLEL-COMPUTING = "Parallel Computing"} @String{j-PATTERN-RECOGN = "Pattern Recognition"} @String{j-PATTERN-RECOGN-LETT = "Pattern Recognition Letters"} @String{j-PC-MAGAZINE = "PC Magazine"} @String{j-PERF-EVAL = "Performance evaluation"} @String{j-PROC-ICASSP = "Proceedings of the International Conference on Acoustics, Speech, and Signal Processing"} @String{j-PROC-INT-CONF-PAR-PROC = "Proceedings of the International Conference on Parallel Processing"} @String{j-PROG-COMP-SOFT = "Programming and Computer Software; translation of Programmirovaniye, (Moscow, USSR) Plenum"} @String{j-PROGRAM-J = "Programmer's Journal"} @String{j-RIV-INFO-MILANO = "Rivista di Informatica (Milano)"} @String{j-SCIENCE = "Science"} @String{j-SIAM-J-ALG-DISC-METH = "SIAM Journal of Algebraic Discrete Methods"} @String{j-SIAM-J-COMPUT = "SIAM Journal on Computing"} @String{j-SIAM-J-DISCR-MATH = "SIAM Journal on Discrete Mathematics"} @String{j-SIGADA-LETTERS = "ACM SIGADA Ada Letters"} @String{j-SIGCSE = "SIGCSE Bulletin (ACM Special Interest Group on Computer Science Education)"} @String{j-SIGIR-FORUM = "SIGIR forum"} @String{j-SIGMOD = "SIGMOD Record (ACM Special Interest Group on Management of Data)"} @String{j-SIGPLAN = "SIGPLAN Notices"} @String{j-SIGSAM = "SIGSAM Bulletin (ACM Special Interest Group on Symbolic and Algebraic Manipulation)"} @String{j-SIGSMALL-PC-NOTES = "SIGSMALLslash PC Notes"} @String{j-SOVIET-PHYS-DOKL = "Soviet Physics---Doklady"} @String{j-SPE = "Software---Practice and Experience"} @String{j-SYS-COMP-JAPAN = "Systems and computers in Japan"} @String{j-TALG = "ACM Transactions on Algorithms"} @String{j-THEOR-COMP-SCI = "Theoret. Comput. Sci."} @String{j-TISSEC = "ACM Transactions on Information and System Security"} @String{j-TOCS = "ACM Transactions on Computer Systems"} @String{j-TODAES = "ACM Transactions on Design Automation of Electronic Systems."} @String{j-TODS = "ACM Transactions on Database Systems"} @String{j-TOIS = "ACM Transactions on Information Systems"} @String{j-TOMS = "ACM Transactions on Mathematical Software"} @String{j-TOOIS = "ACM Transactions on Office Information Systems"} @String{j-TOPLAS = "ACM Transactions on Programming Languages and Systems"} @String{j-TRANS-SAIEE = "Transactions --- The South African Institute of Electrical Engineers. Handelinge --- Die Suid-Afrikaanse Instituut van Elektriese Ingenieurs"} @String{j-VLDB-J = "VLDB Journal: Very Large Data Bases"} @String{j-WIRED = "Wired"} %%% ==================================================================== %%% Organization abbreviations: %%% ==================================================================== %%% Publishers and their addresses: @String{pub-ACM = "ACM Press"} @String{pub-ACM:adr = "New York, NY 10036, USA"} @String{pub-AFIPS = "AFIPS Press"} @String{pub-AFIPS:adr = "Montvale, NJ, USA"} @String{pub-AP = "Academic Press"} @String{pub-AP:adr = "New York, NY, USA"} @String{pub-AW = "Ad{\-d}i{\-s}on-Wes{\-l}ey"} @String{pub-AW:adr = "Reading, MA, USA"} @String{pub-BC = "Brooks\slash Cole"} @String{pub-BC:adr = "Pacific Grove, CA, USA"} @String{pub-BIRKHAUSER = "Birkh{\"{a}}user"} @String{pub-BIRKHAUSER:adr = "Cambridge, MA, USA; Berlin, Germany; Basel, Switzerland"} @String{pub-BIBLIO-INST = "Bibliographisches Institut"} @String{pub-BIBLIO-INST:adr = "Mannheim, Germany"} @String{pub-CRC = "CRC Press"} @String{pub-CRC:adr = "2000 N.W. Corporate Blvd., Boca Raton, FL 33431-9868, USA"} @String{pub-CSP = "Computer Science Press"} @String{pub-CSP:adr = "11 Taft Court, Rockville, MD 20850, USA"} @String{pub-CUP = "Cambridge University Press"} @String{pub-CUP:adr = "Cambridge, UK"} @String{pub-ELLIS-HORWOOD = "Ellis Horwood"} @String{pub-ELLIS-HORWOOD:adr = "New York, NY, USA"} @String{pub-GORDON-BREACH = "Gordon and Breach"} @String{pub-GORDON-BREACH:adr = "Langhorne, PA, USA"} @String{pub-HANSER = "Carl Hanser"} @String{pub-HANSER:adr = "M{\"u}nchen, Germany"} @String{pub-HARTUNG-GORRE = "Hartung-Gorre Verlag"} @String{pub-HARTUNG-GORRE:adr = "Konstanz, Switzerland"} @String{pub-HRW = "Holt, Rinehart, and Winston"} @String{pub-HRW:adr = "New York, NY, USA"} @String{pub-IEEE = "IEEE Computer Society Press"} @String{pub-IEEE:adr = "1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA"} @String{pub-JW = "John Wiley"} @String{pub-JW:adr = "New York, NY, USA"} @String{pub-MACMILLAN = "Macmillan Publishing Company"} @String{pub-MACMILLAN:adr = "New York, NY, USA"} @String{pub-MH = "Mc{\-}Graw-Hill"} @String{pub-MH:adr = "New York, NY, USA"} @String{pub-MIT = "MIT Press"} @String{pub-MIT:adr = "Cambridge, MA, USA"} @String{pub-MITCHELL = "Mitchell Publishing, Inc."} @String{pub-MITCHELL:adr = "Santa Cruz, CA, USA"} @String{pub-MORGAN-KAUFMANN = "Morgan Kaufmann Publishers"} @String{pub-MORGAN-KAUFMANN:adr = "San Francisco, CA"} @String{pub-NASA = "National Aeronautics and Space Administration"} @String{pub-NASA:adr = "Washington, DC, USA"} @String{pub-NH = "North-Hol{\-}land"} @String{pub-NH:adr = "Amsterdam, The Netherlands"} @String{pub-OHMSHA = "Ohmsha, Ltd."} @String{pub-OHMSHA:adr = "3-1 Kanda Nishiki-cho, Chiyoda-ku, Tokyo 101, Japan"} @String{pub-OLDENBOURG = "R. Oldenbourg Verlag"} @String{pub-OLDENBOURG:adr = "Munich, Germany and Vienna, Austria"} @String{pub-OUP = "Oxford University Press"} @String{pub-OUP:adr = "Walton Street, Oxford OX2 6DP, UK"} @String{pub-PENN-STATE-UNIV-PRESS = "Pennsylvania State University Press"} @String{pub-PENN-STATE-UNIV-PRESS:adr = "University Park, PA, USA"} @String{pub-PERGAMON = "Pergamon Press"} @String{pub-PERGAMON:adr = "Oxford, UK"} @String{pub-PH = "Pren{\-}tice-Hall"} @String{pub-PH:adr = "Englewood Cliffs, NJ 07632, USA"} @String{pub-PLENUM = "Plenum Press"} @String{pub-PLENUM:adr = "New York, NY, USA"} @String{pub-PRINCETON = "Princeton University Press"} @String{pub-PRINCETON:adr = "Princeton, NJ, USA"} @String{pub-RESTON = "Reston Publishing Co. Inc."} @String{pub-RESTON:adr = "Reston, VA, USA"} @String{pub-SF = "Scott, Foresman and Company"} @String{pub-SF:adr = "Glenview, IL, USA"} @String{pub-SIAM = "Society for Industrial and Applied Mathematics"} @String{pub-SIAM:adr = "Philadelphia, PA, USA"} @String{pub-SPARTAN = "Spartan Books"} @String{pub-SPARTAN:adr = "New York, NY, USA"} @String{pub-SRA = "Science Research Associates, Inc."} @String{pub-SRA:adr = "Chicago, IL, USA"} @String{pub-SV = "Spring{\-}er-Ver{\-}lag"} @String{pub-SV:adr = "Berlin, Germany~/ Heidelberg, Germany~/ London, UK~/ etc."} @String{pub-TEUBNER = "B. G. Teubner"} @String{pub-TEUBNER:adr = "Stuttgart, Germany"} @String{pub-USENIX = "USENIX"} @String{pub-USENIX:adr = "San Francisco, CA, USA"} @String{pub-USGPO = "United States Government Printing Office"} @String{pub-USGPO:adr = "Washington, DC, USA"} @String{pub-VAHLEN = "Franz Vahlen"} @String{pub-VAHLEN:adr = "M{\"u}nchen, Germany"} @String{pub-VIEWEG = "Friedrich Vieweg und Sohn"} @String{pub-VIEWEG:adr = "Braunschweig, Germany"} @String{pub-VNR = "Van Nostrand Reinhold"} @String{pub-VNR:adr = "New York, NY, USA"} @String{pub-WESTERN-PERIODICALS = "Western Periodicals Co.,"} @String{pub-WESTERN-PERIODICALS:adr = "North Hollywood, CA"} %%% ==================================================================== %%% Series abbreviations: @String{ser-LNAI = "Lecture Notes in Artificial Intelligence"} @String{ser-LNCS = "Lecture Notes in Computer Science"} %%% ==================================================================== %%% Bibliography entries. @Book{Ball:1939:MRE, author = "W. W. Rouse (Walter William Rouse) Ball and H. S. M. (Harold Scott MacDonald [``Donald'']) Coxeter", title = "Mathematical recreations and essays", publisher = pub-MACMILLAN, address = pub-MACMILLAN:adr, edition = "11th", pages = "45", year = "1939", LCCN = "QA95 .B3 1939", bibdate = "Tue Nov 05 08:52:38 2002", note = "According to Knuth \cite[p.~507]{Knuth:1973:ACP}, this is one of two papers that first discuss the birthday paradox: ``if 23 or more people are present in the same room, chances are good that two of them will have the same month and day of birth! In other words, if we select a random function which maps 23 keys into a table of size 365, the probability that no two keys map into the same location is only 0.4927 (less than one-half).'' The discovery is credited to unpublished work of H. Davenport (1927). See also \cite{vonMises:1939:AB}.", acknowledgement = ack-nhfb, annote = "A Web search turned up this truncated comment by David Singmaster (http://anduin.eldar.org/~problemi/singmast/queries.html): ``Birthday Paradox. Feller cites von Mises (1938--39), but von Mises gets the expected number of repetitions, not the usual result. Ball, MRE (11th ed., 1939) cites Davenport, but Coxeter says that Davenport did not publish anything on it and others, including Mrs Davenport, say that Davenport explicitly denied originality for it. However, George Tyson, who was a student [text truncated]''", keywords = "Ball, W. W. Rouse (Walter William Rouse), 1850--1925", } @Article{vonMises:1939:AB, author = "R. von Mises", title = "{{\"U}ber Aufteilungs- und Besetzungswahrscheinlichkeiten}. ({German}) [On Partitioning and Occupation Probabilities]", journal = "{\.I}stanbul {\"U}niversitesi Fen Fak{\"u}ltesi Mecmuasi", volume = "4", number = "??", pages = "145--163", year = "1939", bibdate = "Thu Jul 21 09:15:52 1994", note = "See also \cite{Ball:1939:MRE}.", acknowledgement = ack-nhfb, altjournal = "Revue de la Facult{\'e} des Sciences de l'Universite d'Istanbul", } @Book{Feller:1950:IPT, author = "W. Feller", title = "An Introduction to Probability Theory and its Applications", publisher = pub-JW, address = pub-JW:adr, pages = "???", year = "1950", LCCN = "QA273 .F37", bibdate = "Sat Jul 16 00:30:14 1994", note = "See the discussion of the birthday paradox in Section 2.3.", acknowledgement = ack-nhfb, } @Unpublished{Amdahl:1953:xxx, author = "Gene M. Amdahl and Elaine M. Boehme and N. Rochester and Arthur L. Samuel", title = "???", year = "1953", bibdate = "Fri Jul 15 23:08:54 1994", note = "The year is uncertain (???). Amdahl originated the idea of open addressing with linear probing, which was later independently rediscovered and published \cite{Ershov:1958:xxx}.", acknowledgement = ack-nhfb, } @Unpublished{Lin:1953:xxx, author = "A. D. Lin", title = "???", year = "1953", bibdate = "Fri Jul 15 23:04:25 1994", note = "The year is uncertain (???). Extends \cite{Luhn:1953:xxx} with an alternative overflow handling technique using ``degenerative addresses'' \cite[p.~541]{Knuth:1973:ACP}.", acknowledgement = ack-nhfb, } @Unpublished{Luhn:1953:xxx, author = "Hans Peter Luhn", title = "???", month = jan, year = "1953", bibdate = "Fri Apr 30 11:13:48 1999", note = "Internal IBM memo that first suggested the idea of hashing, and one of the first applications of linked linear lists. Luhn is also the inventor of KWIC indexing, in 1960 \cite[p.~437]{Knuth:1973:ACP}. See also \cite{Lin:1953:xxx}.", acknowledgement = ack-nhfb, note2 = "OCLC contains an entry for a 1953 IBM report entitled ``Self-demarcating code words; a set of three and four letter code words with serially-unique and disjunctive combination-forming characteristics''. Was this the one Knuth refers to?", } @Article{Dumey:1956:IRR, author = "Arnold I. Dumey", title = "Indexing for Rapid Random Access Memory Systems", journal = j-COMP-AUTO, volume = "5", number = "12", pages = "6--9", month = dec, year = "1956", CODEN = "CPAUAJ", ISSN = "0010-4795, 0887-4549", bibdate = "Sat Jul 16 10:47:26 1994", note = "First paper in open literature on hashing. First use of hashing by taking the modulus of division by a prime number. Mentions chaining for collision handling, but not open addressing. See \cite{Ershov:1958:xxx} for the latter.", acknowledgement = ack-nhfb, } @Article{Peterson:1957:ARA, author = "W. W. Peterson", title = "Addressing for random-access storage", journal = j-IBM-JRD, volume = "1", number = "2", pages = "130--146", month = apr, year = "1957", CODEN = "IBMJAE", ISSN = "0018-8646", bibdate = "Tue Sep 06 20:55:04 1994", note = "First major paper dealing with the problem of searching in large files. Defined open addressing in general, analyzed the performance of uniform hashing, and the behavior of linear open addressing with various bucket sizes.", acknowledgement = ack-nhfb, country = "USA", date = "00/00/00", descriptor = "Hash coding;", enum = "2417", language = "English", location = "PKI-OG: Li-Ord.Le", references = "0", revision = "21/04/91", town = "Yorktown Heights", } @Article{Ershov:1958:xxx, author = "A. P. Ershov", title = "???", journal = j-DOKL-AKAD-NAUK, volume = "118", number = "??", pages = "427--430", year = "1958", CODEN = "DANKAS", ISSN = "0002-3264", bibdate = "Fri Apr 30 11:08:43 1999", note = "Rediscovery and first publication of linear open addressing. See \cite{Amdahl:1953:xxx,Dumey:1956:IRR}.", acknowledgement = ack-nhfb, } @Article{Williams:1959:HII, author = "F. A. Williams", title = "Handling Identifiers as Internal Symbols in Language Processors", journal = j-CACM, volume = "2", number = "6", pages = "21--24", month = jun, year = "1959", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jul 16 11:42:12 1994", acknowledgement = ack-nhfb, } @Article{Johnson:1961:ICM, author = "L. R. Johnson", title = "An Indirect Chaining Method for Addressing on Secondary Keys", journal = j-CACM, volume = "4", number = "5", pages = "218--222", month = may, year = "1961", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Mon Sep 26 23:36:24 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib", acknowledgement = ack-nhfb, annote = "Direct file with rings to access records by other attributes, with analysis.", } @Article{Schay:1962:AFA, author = "G. {Schay, Jr.} and W. G. Spruth", title = "Analysis of a File Addressing Method", journal = j-CACM, volume = "5", number = "8", pages = "459--462", month = aug, year = "1962", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Fri Nov 25 18:19:40 MST 2005", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Misc/hash.bib; ftp://ftp.math.utah.edu/pub/tex/bib/cacm1960.bib; http://www.acm.org/pubs/contents/journals/cacm/", note = "Early analysis of linear probing.", abstract = "This paper presents a new file addressing method based on the calculation of an address from the identification of a record. For large recirculating type files, it seems to be more advantageous than customary ones. The probability distribution of the displacement of records from their calculated address, which is one less than the number of probes required to address a record, is computed on the basis of a Markov chain model. For the reader not interested in the mathematics, the introduction and the summary should be sufficient.", acknowledgement = ack-nhfb, keywords = "hash table load factor; linear probing", } @Article{Buchholz:1963:FOA, author = "Werner Buchholz", title = "File Organization and Addressing", journal = j-IBM-SYS-J, volume = "2", number = "1", pages = "86--111", month = jun, year = "1963", CODEN = "IBMSA7", ISSN = "0018-8670", bibdate = "Wed Jul 20 22:58:45 1994", note = "Comprehensive survey of hashing, with a good discussion of hash functions.", acknowledgement = ack-nhfb, } @Article{Greniewski:1963:ELK, author = "M. Greniewski and W. Turski", title = "The External Language {KLIPA} for the {URAL-2} Digital Computer", journal = j-CACM, volume = "6", number = "6", pages = "322--324", month = jun, year = "1963", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jul 16 10:47:04 1994", note = "Early work on derivation of hash functions.", acknowledgement = ack-nhfb, } @Article{Hanan:1963:ACT, author = "M. Hanan and F. P. Palermo", title = "An Application of Coding Theory to a File Address Problem", journal = j-IBM-JRD, volume = "7", number = "2", pages = "127--129", month = apr, year = "1963", CODEN = "IBMJAE", ISSN = "0018-8646", bibdate = "Tue Sep 06 20:56:25 1994", acknowledgement = ack-nhfb, annote = "Mathematical statement of direct access problem. Polynomial hashing.", } @InProceedings{Lin:1963:KAR, author = "A. D. Lin", title = "Key addressing of random access memories by radix transformation", crossref = "AFIPS:1963:PSJ", pages = "355--366", year = "1963", bibdate = "Mon Sep 26 23:41:05 1994", acknowledgement = ack-nhfb, } @Article{McIlroy:1963:VMF, author = "M. D. McIlroy", title = "A Variant Method of File Searching", journal = j-CACM, volume = "6", number = "3", pages = "101--101", year = "1963", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Mon Sep 26 23:53:54 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib", acknowledgement = ack-nhfb, } @Article{Schay:1963:MKA, author = "G. Schay and N. Raver", title = "A Method for Key-to-Address Transformation", journal = j-IBM-JRD, volume = "7", number = "2", pages = "121--126", month = apr, year = "1963", CODEN = "IBMJAE", ISSN = "0018-8646", bibdate = "Mon Sep 26 23:59:15 1994", acknowledgement = ack-nhfb, } @Article{Trainiter:1963:ARA, author = "M. Trainiter", title = "Addressing for Random-Access Storage with Multiple Bucket Capabilities", journal = j-J-ACM, volume = "??", number = "3", pages = "307--315", month = jul, year = "1963", CODEN = "JACOAH", ISSN = "0004-5411", bibdate = "Mon Oct 24 17:55:13 1994", acknowledgement = ack-nhfb, } @TechReport{Martin:1964:HCF, author = "William A. Martin", title = "Hash-Coding Functions of a Complex Variable", type = "Report", number = "A. I. MEMO 70 and MAC-M-165", institution = inst-MIT-AI, address = inst-MIT:adr, pages = "??", month = jun, year = "1964", bibdate = "Thu Jul 21 08:37:46 1994", acknowledgement = ack-nhfb, } @Article{Batson:1965:OST, author = "A. Batson", title = "The organization of symbol tables", journal = j-CACM, volume = "8", number = "2", pages = "111--112", month = feb, year = "1965", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Mon Sep 19 10:21:06 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Compiler/bevan.bib", abstract = "An efficient symbol table organization is an important feature in the design of any compiler. During the construction of the Virginia ALGOL 60 compiler for the Burroughs B205, the primary consideration in the symbol table design was that the recognition of identifiers and reserved words should be as rapid as possible. the general features of the technique are described.", acknowledgement = ack-nhfb, checked = "19940409", refs = "0", sjb = "Describes a technique where all identifiers are stored in a stack and lookup is a linear search. Not surprisingly criticizes this for being slow. Instead of this method, suggests using a hash table with a linear probe on collision.", } @Article{Ariwasa:1968:RHM, author = "Makota Ariwasa", title = "Residue Hash Method", journal = j-J-INF-PROCESS, volume = "12", number = "??", pages = "??", month = feb, year = "1968", CODEN = "JIPRDE", ISSN = "0387-6101", bibdate = "Thu Jul 21 09:16:05 1994", acknowledgement = ack-nhfb, } @Article{Hopgood:1968:STO, author = "F. R. A. Hopgood", title = "A Solution for the Table Overflow Problem for Hash Tables", journal = j-COMP-BULL, volume = "??", number = "??", pages = "??", month = mar, year = "1968", bibdate = "Thu Jul 21 09:16:16 1994", acknowledgement = ack-nhfb, } @Article{Hopgood:1968:xxx, author = "F. R. A. Hopgood", title = "???", journal = j-COMP-BULL, volume = "11", number = "??", pages = "297--300", year = "1968", bibdate = "Fri Jul 15 22:51:48 1994", note = "Presents algorithms for expanding and rehashing nearly full hash tables.", acknowledgement = ack-nhfb, } @Article{Maurer:1968:IHS, author = "Ward Douglas Maurer", title = "An Improved Hashcode for Scatter Storage", journal = j-CACM, volume = "11", number = "1", pages = "35--37", month = jan, year = "1968", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Tue Jul 19 23:00:01 1994", acknowledgement = ack-nhfb, } @Article{Morris:1968:SST, author = "Robert Morris", title = "Scatter Storage Techniques", journal = j-CACM, volume = "11", number = "1", pages = "38--44", month = jan, year = "1968", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jul 16 10:46:50 1994", note = "Influential survey of the subject of hashing, and first introduction of random probing with secondary clustering. Appears to be the first publication where the word `hashing' appeared, although it was in common use at the time. Knuth \cite[p.~542]{Knuth:1973:ACP} found only one earlier printed use of the word, in a 1961 unpublished memorandum by W. W. Peterson.", acknowledgement = ack-nhfb, } @PhdThesis{deBalbine:1969:CAR, author = "Guy {de Balbine}", title = "Computational Analysis of the Random Components Induced by a Binary Equivalence Relation", type = "Ph.D. thesis", school = "California Institute of Technology", address = "Pasadena, CA, USA", pages = "168", year = "1969", bibdate = "Fri Apr 30 11:21:28 1999", note = "First use of second hash function for computing next hash table location after a collision. See also \cite{Bell:1970:LQH}.", abstract = "The problem of partitioning into classes by means of a binary equivalence relation is investigated. Several algorithms for determining the number of components in the graph associated with a particular set of elements are constructed and compared. When the classification process operates on independently-drawn samples of $n$ distinct elements from a population, the expected number of components is shown to be obtainable recursively for a class of problems called separable; in all cases, estimates are available to reach any desired level of accuracy. Clustering models in Euclidean space are analyzed in detail and asymptotic formulas obtained to complement experiments. Conjectures concerning the general behavior of the expected number of components are presented also. Finally, several computational tools of general interest are improved significantly.", acknowledgement = ack-nhfb, annote = "Abstract in Dissertation Abstracts, v30 n2 p645b 1969.", } @Article{Feldman:1969:ABA, author = "Jerome A. Feldman and Paul D. Rovner", title = "An {Algol}-Based Associative Language", journal = j-CACM, volume = "12", number = "8", pages = "439--449", month = aug, year = "1969", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Fri Nov 25 18:20:27 MST 2005", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib and ftp://ftp.ira.uka.de/pub/bibliography/Ai/Ai.misc.bib; ftp://ftp.math.utah.edu/pub/tex/bib/cacm1960.bib; http://www.acm.org/pubs/contents/journals/cacm/", abstract = "A high level programming language for large, complex associative structures has been designed and implemented. The underlying data structure has been implemented using a hash-coding technique. The discussion includes a comparison with other work and examples of applications of the language.", acknowledgement = ack-nhfb, classcodes = "C6140D (High level languages)", corpsource = "Stanford Univ., CA, USA", keywords = "ALGOL; associative; Associative; data structure; Data Structure; data structures; LEAP; procedure oriented languages; programming language; Programming Language; SAIL", remark = "Description of LEAP language and data structure of binary relations.", } @InProceedings{Files:1969:IRS, author = "John R. Files and Harry D. Huskey", title = "An Information Retrieval System Based on Superimposed Coding", crossref = "AFIPS:1969:ACP", pages = "??", year = "1969", acknowledgement = ack-nhfb, annote = "Proposal for Word-in-text retrieval system with a hash code for access to pointer tables for each word class.", } @InProceedings{Olsen:1969:RRF, author = "Charles A. Olsen", title = "Random Access File Organization for Indirectly Accessed Records", crossref = "ACM:1969:PAN", pages = "539--549", year = "1969", bibdate = "Tue Jul 19 22:10:27 1994", note = "Discusses practical considerations in the design of external scatter tables.", acknowledgement = ack-nhfb, } @Article{Bell:1970:LQH, author = "James R. Bell and Charles H. Kaman", title = "The Linear Quotient Hash Code", journal = j-CACM, volume = "13", number = "11", pages = "675--677", month = nov, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Tue Jul 19 17:51:20 1994", note = "Independent discovery of technique of secondary hash functions first proposed by \cite{deBalbine:1969:CAR}.", acknowledgement = ack-nhfb, } @Article{Bell:1970:QQM, author = "J. R. Bell", title = "Quadratic Quotient Method --- {A} Hash Code Eliminating Secondary Clustering", journal = j-CACM, volume = "13", number = "2", pages = "107--9", month = feb, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Secondary clustering as a cause of hash code inefficiency is discussed, and a new hashing method based on its elimination is presented. Comparisons with previous methods are made both analytically and empirically.", acknowledgement = ack-nhfb, keywords = "computers; programming", } @Article{Bloom:1970:STH, author = "B. H. Bloom", title = "Space/Time Trade-Offs in Hash Coding with Allowable Errors", journal = j-CACM, volume = "13", number = "7", pages = "422--6", month = jul, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency. The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods. An example is discussed which illustrates possible areas of application for the new method.", acknowledgement = ack-nhfb, journalabr = "Commun ACM", keywords = "codes; computers; computers, errors; hash coding; inf", } @Article{Bloom:1970:STO, author = "Burton H. Bloom", title = "Space/Time Trade-offs in Hash Coding with Allowable Errors", journal = j-CACM, volume = "13", number = "7", pages = "422--426", month = jul, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sun Jul 17 19:39:54 1994", acknowledgement = ack-nhfb, annote = "Phantom use of a direct access list.", keywords = "bit vector filter CACM", } @Article{Coffman:1970:FSU, author = "E. G. {Coffman, Jr.} and J. Eve", key = "Coffman \& Eve", title = "File Structures Using Hashing Functions", journal = j-CACM, volume = "13", number = "7", pages = "427--432, 436", month = jul, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "A general method of file structuring is proposed which uses a hashing function to define tree structure. Two types of such trees are examined, and their relation to trees studied in the past is explained. Results for the probability distributions of path lengths are derived and illustrated.", acknowledgement = ack-nhfb, annote = "Tree structure with branching based on bit values of key code.", journalabr = "Commun ACM", keywords = "computers; data processing; data structures; file organization; hash coding; information storage and retrie; tree structures", } @Article{Day:1970:FTQ, author = "A. C. Day", title = "Full Table Quadratic Searching for Scatter Storage", journal = j-CACM, volume = "13", number = "8", pages = "481--482", month = aug, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Theory/Seiferas/Pre.1975.bib, Compendex database", abstract = "The quadratic residue search method for hash tables avoids much of the clustering experienced with a linear search method. The simple quadratic search only accesses half the table. It has been shown that when the length of the table is a prime of the form 4n plus 3, where n is an integer, the whole table may be accessed by two quadratic searches plus a separate access for the original entry point. A search method is presented which is computationally simple, has all the advantages of the quadratic search, and yet accesses all the table in one sweep.", acknowledgement = ack-nhfb, journalabr = "Commun ACM", keywords = "CACMA; computers; computers, data storage; hash coding; programming; table look-up", } @Article{Lamport:1970:CBQ, author = "Leslie Lamport", title = "Comment on {Bell}'s Quadratic Quotient Method for Hash Code Searching", journal = j-CACM, volume = "13", number = "9", pages = "573--574", month = sep, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Thu Jul 21 09:16:50 1994", acknowledgement = ack-nhfb, } @Article{Radke:1970:UQR, author = "C. E. Radke", title = "The Use of Quadratic Residue Research", journal = j-CACM, volume = "13", number = "2", pages = "103--150", month = feb, year = "1970", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Mon Sep 26 23:56:07 1994", acknowledgement = ack-nhfb, } @TechReport{Ullman:1970:DHF, author = "Jeffrey D. Ullman", title = "The Design of Hashing Functions", number = "85", institution = "Princeton University, Electrical Engineering Department, TR", pages = "??", month = sep, year = "1970", bibdate = "Thu Jul 21 08:40:04 1994", acknowledgement = ack-nhfb, } @Book{Harrison:1971:DSP, author = "Malcolm C. Harrison", title = "Data Structures and Programming", publisher = "Courant Institute of Mathematical Sciences, New York University", address = "New York, NY, USA", pages = "xii + 381", month = apr, year = "1971", LCCN = "QA76.5 .H37", bibdate = "Mon Oct 24 18:42:52 1994", note = "See also \cite{Harrison:1973:DSP}.", acknowledgement = ack-nhfb, annote = "Mainly in core algorithms; Chapter 9 suggests comb. hashing.", } @Article{Harrison:1971:IST, author = "M. C. Harrison", title = "Implementation of the Substring Test by Hashing", journal = j-CACM, volume = "14", number = "12", pages = "777--779", month = dec, year = "1971", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Mon Jul 18 20:21:49 1994", note = "See also \cite{Tharp:1982:PTS}.", acknowledgement = ack-nhfb, } @InProceedings{Knott:1971:EOA, author = "G. D. Knott", booktitle = "ACM SIGFIDET, Codd(ed), 1971", title = "Expandable Open Addressing Hash Table Storage and Retrieval", publisher = "????", address = "????", pages = "??", year = "1971", bibdate = "Thu Jul 21 08:40:21 1994", acknowledgement = ack-nhfb, } @Article{Lum:1971:KAT, author = "V. Y. Lum and P. S. T. Yuen and M. Dodd", title = "Key-to-Address Transform Techniques: {A} Fundamental Performance Study on Large Existing Formatted Files", journal = j-CACM, volume = "14", number = "4", pages = "228--239", month = apr, year = "1971", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jul 16 10:48:52 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Misc/hash.bib", note = "Survey of several hash functions, with performance results.", acknowledgement = ack-nhfb, } @Article{Martin:1971:DEA, author = "William A. Martin", title = "Determining the Equivalence of Algebraic Expressions by Hash Coding", journal = j-J-ACM, volume = "18", number = "4", pages = "549--558", month = oct, year = "1971", CODEN = "JACOAH", ISSN = "0004-5411", bibdate = "Wed Jul 20 23:02:13 1994", acknowledgement = ack-nhfb, } @Article{Price:1971:TLT, author = "C. E. Price", title = "Table Lookup Techniques", journal = j-COMP-SURV, volume = "3", number = "2", pages = "49--64", month = jun, year = "1971", CODEN = "CMSVAN", ISSN = "0360-0300", bibdate = "Mon Sep 26 20:49:51 1994", acknowledgement = ack-nhfb, keywords = "binary search; hashing; search techniques; table lookup techniques", } @Article{Williams:1971:SUM, author = "J. G. Williams", title = "Storage Utilization in a Memory Hierarchy When Storage Assignment is Performed by a Hashing Algorithm", journal = j-CACM, volume = "14", number = "3", pages = "172--5", month = mar, year = "1971", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "The utilization of storage is studied in a two-level memory hierarchy. The first storage level, which is the fast store, is divided into a number of storage areas. When an entry is to be filed in the hierarchy, a hashing algorithm will attempt to place the entry into one of these areas. If this particular area is full, then the entry will be placed into the slower second-level store, even though other areas in the first-level store may have space available. Given that N entries have been filed in the entire hierarchy, an expression is derived for the expected number of entries filed in the first-level store. This expression gives a measure of how effectively the first-level store is being used. By means of examples, storage utilization is then studied as a function of the hashing algorithm, the number of storage areas into which the first-level store is divided and the total size of the first-level store.", acknowledgement = ack-nhfb, journalabr = "Commun ACM", keywords = "CACMA; computers, digital; storage allocation; storage units", } @Article{Bell:1972:QQM, author = "James R. Bell", title = "The Quadratic Quotient Method: {A} Hash Code Eliminating Secondary Clustering", journal = j-CACM, volume = "13", number = "2", pages = "107--109", month = feb, year = "1972", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Tue Sep 06 19:49:51 1994", acknowledgement = ack-nhfb, } @Article{Hashida:1972:AM, author = "O. Hashida", title = "Analysis of multiqueue", journal = j-EL-COMM-LAB, volume = "20", number = "??", pages = "189--199", year = "1972", bibdate = "Thu Jul 21 09:17:05 1994", acknowledgement = ack-nhfb, country = "J", date = "18/02/88", descriptor = "Queueing system; polling; gated service; exhaustive service;", enum = "1292", language = "English", location = "PKI-OG: Li-Ord.Le", references = "9", revision = "21/04/91", } @Article{Hashida:1972:LAC, author = "O. Hashida and K. Ohara", title = "Line accommodation capacity of a communication control unit", journal = j-EL-COMM-LAB, volume = "20", number = "??", pages = "231--239", year = "1972", bibdate = "Thu Jul 21 09:17:10 1994", acknowledgement = ack-nhfb, country = "J", date = "18/02/88", descriptor = "Queueing system; polling;", enum = "1293", language = "English", location = "PKI-OG: Li-Ord.Le", references = "3", revision = "21/04/91", } @Article{Healey:1972:CEP, author = "M. J. R. Healey", title = "Checking the Execution of Programs by Hashing", journal = j-IBM-TDB, volume = "15", number = "7", pages = "??--??", month = dec, year = "1972", CODEN = "IBMTAA", ISSN = "0018-8689", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", acknowledgement = ack-nhfb, classification = "723", journalabr = "IBM Tech Disclosure Bull", keywords = "computer programming", } @Article{Hopgood:1972:QHM, author = "F. R. A. Hopgood and J. Davenport", title = "The Quadratic Hash Method When the Table Size is a Power of $2$", journal = j-COMP-J, volume = "15", number = "4", pages = "314--315", month = nov, year = "1972", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Fri Sep 29 08:52:07 MDT 2000", bibsource = "http://www3.oup.co.uk/computer_journal/hdb/Volume_15/Issue_04/; Database/Wiederhold.bib", note = "See correspondence \cite{Pawson:1973:CHT}.", URL = "http://www3.oup.co.uk/computer_journal/hdb/Volume_15/Issue_04/150314.sgm.abs.html; http://www3.oup.co.uk/computer_journal/hdb/Volume_15/Issue_04/tiff/314.tif; http://www3.oup.co.uk/computer_journal/hdb/Volume_15/Issue_04/tiff/315.tif", acknowledgement = ack-nhfb, annote = "Criteria for rehashing to a larger space.", classcodes = "C6130 (Data handling techniques)", corpsource = "Atlas Computer Lab., Chilton, Didcot, UK", keywords = "codes; data handling; hash table; power of 2; quadratic; table size", treatment = "P Practical", } @TechReport{Koehler:1972:SDB, author = "Ch. Koehler", title = "Ein System zur Darstellung und Bearbeitung Assoziativer Datenstrukturen", institution = "????", address = "Bonn, Germany", pages = "??", year = "1972", bibdate = "Thu Jul 21 08:41:07 1994", acknowledgement = ack-nhfb, descriptor = "Adressierung, Assoziativ, Baum, Datenstruktur, Hash-code, Leap, Netzwerk, Relationensystem, Speicherkonzept, Speicherstruktur, Strukturanalyse, Systemanalyse", } @Article{Luccio:1972:WIL, author = "Fabrizio Luccio", title = "Weighted Increment Linear Search for Scatter Tables", journal = j-CACM, volume = "15", number = "12", pages = "1045--1047", month = dec, year = "1972", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Thu Sep 22 11:29:43 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib", acknowledgement = ack-nhfb, } @TechReport{Mergenthaler:1972:HCT, author = "Erhard Mergenthaler", title = "Hash-code-techniken, Uebersicht", institution = "????", address = "Stuttgart, Germany", pages = "??", year = "1972", bibdate = "Thu Jul 21 08:41:19 1994", acknowledgement = ack-nhfb, annote = "Informatik Hausarbeit, Ausfuehrliche Uebersicht ueber Hash-techniken. Interner Bericht 01/73.", descriptor = "Hash-code, Hash-verfahren, Hashing", } @Article{Mullin:1972:IIS, author = "James K. Mullin", title = "An Improved Indexed-Sequential Access Method Using Hashed Overflow", journal = j-CACM, volume = "15", number = "5", pages = "301--307", month = may, year = "1972", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Thu Jul 21 08:41:25 1994", acknowledgement = ack-nhfb, } @Article{Ullman:1972:NEH, author = "Jeffrey D. Ullman", title = "A Note on the Efficiency of Hashing Functions", journal = j-J-ACM, volume = "19", number = "3", pages = "569--575", month = jul, year = "1972", CODEN = "JACOAH", ISSN = "0004-5411", bibdate = "Tue Sep 27 00:04:12 1994", note = "Early work on the problem of finding optimal hash functions for open addressing.", acknowledgement = ack-nhfb, } @Article{vanderPool:1972:OSA, author = "J. A. van der Pool", title = "Optimum Storage Allocation for Initial Loading of a File", journal = j-IBM-JRD, volume = "16", number = "6", pages = "579--586", month = nov, year = "1972", CODEN = "IBMJAE", ISSN = "0018-8646", bibdate = "Tue Sep 27 00:05:07 1994", acknowledgement = ack-nhfb, } @PhdThesis{Webb:1972:DAE, author = "D. A. Webb", title = "The Development and Application of an Evaluation Model for Hash Coding Systems", type = "Ph.D. Thesis", school = "Syracuse University", address = "Syracuse, NY, USA", month = aug, year = "1972", bibdate = "Tue Sep 27 00:09:20 1994", acknowledgement = ack-nhfb, } @Article{Arnold:1973:UHA, author = "R. F. Arnold and W. E. Bass and M. H. Hartung and F. D. Snow and R. D. Iii Stephens", title = "Uniform Hashing Algorithm", journal = j-IBM-TDB, volume = "16", number = "7", pages = "2214--2216", month = dec, year = "1973", CODEN = "IBMTAA", ISSN = "0018-8689", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "A hashing algorithm is described that achieves a uniform distribution of the virtual space onto the real space. If the functions defined in the algorithm have the further property of uniform random distribution, additional properties are satisfied.", acknowledgement = ack-nhfb, classification = "723", journalabr = "IBM Tech Disclosure Bull", keywords = "computer programming", } @Article{Bays:1973:RHC, author = "Carter Bays", title = "The Reallocation of Hash-Coded Tables", journal = j-CACM, volume = "16", number = "1", pages = "11--14", month = jan, year = "1973", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "When the space allocation for a hash-coded table is altered, the table entries must be rescattered over the new space. A technique for accomplishing this rescattering is presented. The technique is independent of both the length of the table and the hashing function used, and can be utilized in conjunction with a linear reallocation of the table being rescattered. Moreover, it can be used to eliminate previously flagged deletions from any hash-coded table, or to change from one hashing method to another. The efficiency of the technique is discussed and theoretical statistics are given.", acknowledgement = ack-nhfb, annote = "Algorithm to handle increase or decrease within a direct access table containing entries.", classification = "723", journalabr = "Commun ACM", keywords = "computer systems programming; data storage, digital; dynamic storage; hash code; reallocation; scatter storage", } @Article{Bays:1973:STS, author = "C. Bays", title = "Some Techniques for Structuring Chained Hash Tables", journal = j-COMP-J, volume = "16", number = "2", pages = "126--131", month = may, year = "1973", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Fri Sep 29 08:52:11 MDT 2000", bibsource = "Database/Wiederhold.bib; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/", URL = "http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/160126.sgm.abs.html; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/tiff/126.tif; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/tiff/127.tif; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/tiff/128.tif; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/tiff/129.tif; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/tiff/130.tif; http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_02/tiff/131.tif", acknowledgement = ack-nhfb, classcodes = "C6130 (Data handling techniques)", corpsource = "Univ. South Carolina, Columbia, SC, USA", keywords = "chained hash tables; data handling; structuring; techniques", } @Article{Brent:1973:RRT, author = "Richard P. Brent", title = "Reducing the Retrieval Time of Scatter Storage Techniques", journal = j-CACM, volume = "16", number = "2", pages = "105--109", month = feb, year = "1973", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", note = "Modification of open addressing with double hashing to reduce the average number of probes for a successful search.", abstract = "A new method for entering and retrieving information in a hash table is described. The method is intended to be efficient if most entries are looked up several times. The expected number of probes to look up an entry, predicted theoretically and verified by Monte Carlo experiments, is considerably less than for other comparable methods if the table is nearly full. An example of a possible Fortran implementation is given.", acknowledgement = ack-nhfb, classification = "723; 901", journalabr = "Commun ACM", keywords = "address calculation; computer programming languages --- fortran; content addressing; data storage, digital --- Random Access; hash addressing; information retrieval systems; linear quotient method", } @Article{Davison:1973:RSC, author = "G. A. Davison", title = "Rapidly Searching for Character String Matches Using Hash Coding", journal = j-IBM-TDB, volume = "16", number = "1", pages = "??--??", month = jun, year = "1973", CODEN = "IBMTAA", ISSN = "0018-8689", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", acknowledgement = ack-nhfb, classification = "723", journalabr = "IBM Tech Disclosure Bull", keywords = "computer programming", } @Article{Feldman:1973:CBS, author = "J. A. Feldman and J. R. Low", title = "Comment on {Brent}'s Scatter Storage Algorithm", journal = j-CACM, volume = "16", number = "11", pages = "??--??", month = nov, year = "1973", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Tue May 28 11:57:54 1996", acknowledgement = ack-nhfb, keywords = "Hashing, information storage and retrieval, scatter storage, searching, symbol table", } @TechReport{Ghosh:1973:ACW, author = "S. P. Ghosh and V. Y. Lum", title = "An Analysis of Collisions When Hashing by Division", type = "Technical Report", number = "RJ-1218", institution = inst-IBM, address = inst-IBM:adr, month = may, year = "1973", bibdate = "Mon Sep 26 23:33:08 1994", acknowledgement = ack-nhfb, } @Article{Gurski:1973:NAK, author = "Aaron Gurski", title = "A Note on Analysis of Keys for Use in Hashing", journal = j-BIT, volume = "13", number = "1", pages = "120--122", year = "1973", CODEN = "BITTEL, NBITAB", ISSN = "0006-3835", bibdate = "Mon Nov 16 16:10:56 1998", acknowledgement = ack-nhfb, annote = "Digit selection by bit.", } @Book{Harrison:1973:DSP, author = "Malcolm C. Harrison", title = "Data-structures and Programming", publisher = pub-SF, address = pub-SF:adr, pages = "322", year = "1973", ISBN = "0-673-05964-2", ISBN-13 = "978-0-673-05964-2", LCCN = "QA76.6 .H37", bibdate = "Wed Jul 13 19:05:04 1994", note = "See \cite{Harrison:1971:DSP}.", acknowledgement = ack-nhfb, } @TechReport{Kennedy:1973:RSU, author = "Ken Kennedy", title = "Reduction in strength using hashed temporaries", type = "Technical Report", number = "SETL Newsletter \#102", institution = "Courant Inst. of Math. Sciences, New York University, New York", pages = "??", month = mar, year = "1973", bibdate = "Thu Jul 21 08:43:53 1994", acknowledgement = ack-nhfb, } @Book{Knuth:1973:ACP, author = "D. E. Knuth", title = "The Art of Computer Programming, Sorting and Searching", volume = "3", publisher = pub-AW, address = pub-AW:adr, pages = "xi + 723", year = "1973", ISBN = "0-201-03803-X", ISBN-13 = "978-0-201-03803-3", LCCN = "QA76.5 .K74", bibdate = "Wed Dec 15 15:47:47 1993", acknowledgement = ack-nhfb, annote = "Standardwerk ueber Suchen und Sortieren 5. Sorting 5.1. Combinatorial Properties of Permutations 5.2. Internal Sorting 5.3. Optimum Sorting 5.4. External Sorting 5.5. Summary, History, and Bibliography 6. Searching 6.1. Sequential Search 6.2. Searching By Comparison of Keys 6.3. Digital Searching 6.4. Hashing 6.5. Retrieval on Secondary Keys Answers to Exercises Appendix A: Tables of Numerical Quantities Appendix B: Index to Notations Index and Glossary.", annote-2 = "A basic source for computational algorithms such as hashing (pp.506--568), search tree construction(pp.406--505), and some notes on disk performance evaluation (pp.361--371).", descriptor = "Algorithmus, B-baum, Baum, Binaer-baum, Gestreute Speicherung, Hash-verfahren, Mischen, Sortieren, Speicherung, Suchen, Zugriff", } @Article{Lum:1973:GPA, author = "Vincent Y. Lum", title = "General Performance Analysis of Key-to-Address Transformation Methods Using an Abstract File Concept", journal = j-CACM, volume = "16", number = "10", pages = "603--612", month = oct, year = "1973", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Wed Oct 05 14:01:15 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib", acknowledgement = ack-nhfb, annote = "analysis and results using distributions from the entire key domain.", } @Article{Mitra:1973:SHP, author = "Debasis Mitra", title = "Solution to the Hashing Problem for Code Length 3", journal = j-INF-CONTROL, volume = "23", number = "3", pages = "205--220", month = oct, year = "1973", CODEN = "IFCNA4", ISSN = "0019-9958", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "In the hashing procedure considered, each name in a long list of names is associated with a hash code which is a permutation of the triplet (1, 2, 3). The code denotes an ordering of preferences of locations for storing the name; the ith element of the code denotes the ith most preferred location. In each sample three names are picked at random from the list; the names are then stored in a collection of three numbered locations. The policy for storing is based on the respective codes, i. e., at any stage a name is stored in the most preferred of the empty locations. For each sample the number of excess pokes is defined to be the number of searched-but-occupied locations. The solution given is to the problem of obtaining all probability distributions of codes which minimize the expected number of excess pokes.", acknowledgement = ack-nhfb, classification = "723; 731", journalabr = "Inf Control", keywords = "codes, symbolic", } @Article{Pawson:1973:CHT, author = "A. J. D. Pawson and F. R. A. Hopgood", title = "Correspondence: Hashing techniques for table searching", journal = j-COMP-J, volume = "16", number = "3", pages = "285--285", month = aug, year = "1973", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Sat Oct 07 17:13:59 2000", bibsource = "http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_03/", note = "See \cite{Hopgood:1972:QHM}.", URL = "http://www3.oup.co.uk/computer_journal/hdb/Volume_16/Issue_03/tiff/285.tif", acknowledgement = ack-nhfb, } @Article{Perry:1973:IME, author = "O. R. Perry", title = "Indexing Method Employing Hashing", journal = j-IBM-TDB, volume = "16", number = "3", pages = "694--697", month = aug, year = "1973", CODEN = "IBMTAA", ISSN = "0018-8689", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", acknowledgement = ack-nhfb, classification = "723", journalabr = "IBM Tech Disclosure Bull", keywords = "data processing", } @Article{Stahl:1973:HLB, author = "Hans Michael Stahl", title = "{Hashcodingverfahren}. [Hash Coding Techniques]", journal = "Angewandte Informatik/Applied Informatics", volume = "15", number = "10", pages = "435--440", month = oct, year = "1973", CODEN = "AWIFA7", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Various hash-coding techniques are considered. An extension of the quadratic method is included. Besides the average number of probes for each of the different methods, the amount of time needed for a single probe is discussed. To prove the analytical results, all methods were simulated. Those methods found to be best are presented in greater detail with their simulation results and their flow charts.", acknowledgement = ack-nhfb, classification = "723", journalabr = "Angew Inf Appl Inf", keywords = "codes, symbolic", language = "German", } @Article{vanderPool:1973:OSA, author = "J. A. van der Pool", title = "Optimum Storage Allocation for a File in Steady State", journal = j-IBM-JRD, volume = "17", number = "1", pages = "27--38", month = jan, year = "1973", CODEN = "IBMJAE", ISSN = "0018-8646", bibdate = "Tue Sep 27 00:07:03 1994", acknowledgement = ack-nhfb, } @Article{Ackerman:1974:QSH, author = "A. Frank Ackerman", title = "Quadratic Search for Hash Tables of Size $p^n$", journal = j-CACM, volume = "17", number = "3", pages = "164", month = mar, year = "1974", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Wed Jul 20 23:01:58 1994", acknowledgement = ack-nhfb, } @Article{Amble:1974:OHT, author = "O. Amble and D. E. Knuth", title = "Ordered Hash Tables", journal = j-COMP-J, volume = "17", number = "2", pages = "135--142", month = may, year = "1974", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Some variants of the traditional hash method, making use of the numerical or alphabetical order of the keys, lead to faster searching at the expense of a little extra work when items are inserted. This paper presents the new algorithms and analyzes their average running time. Refs.", acknowledgement = ack-nhfb, classcodes = "C6130 (Data handling techniques)", classification = "723", corpsource = "Univ. Oslo, Norway", journalabr = "Comput J", keywords = "address; average running time; calculation; computer operating systems; computer programming --- Subroutines; faster searching; hash tables; list processing; method; ordered hash tables; table lookup; variants of the traditional hash", treatment = "P Practical", } @Article{Atkinson:1974:FPQ, author = "L. V. Atkinson and A. J. Cornah", title = "Full Period Quadratic Hashing", journal = j-INT-J-COMPUT-MATH, volume = "4", number = "2", pages = "177--189", month = sep, year = "1974", CODEN = "IJCMAT", ISSN = "0020-7160", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "If n, the size of an open hash table, is a prime number then quadratic displacement guarantees that, in the event of successive collisions, exactly (n plus 1)/2 different entries are eventually examined (although more than (n plus 1)/2 probes may be necessary to achieve this). If n is a power of 2 then in general only a small portion of the table will be searched. Two sets of quadratic polynomials are presented here which guarantee full period search (n different entries hit in n probes) for any table size which is a power of 2. It is also proved that these are the only quadratic polynomials with this property.", acknowledgement = ack-nhfb, classification = "723", journalabr = "Int J Comput Math", keywords = "computer systems programming; hashing", } @InProceedings{Bayer:1974:SCM, author = "Rudolf Bayer", title = "Storage Characteristics and Methods for Searching and Addressing", crossref = "Rosenfeld:1974:IPP", pages = "??", year = "1974", bibdate = "Thu Jul 21 09:31:17 1994", acknowledgement = ack-nhfb, annote = "Hashing versus trees.", } @Article{Bookstein:1974:HCN, author = "Abraham Bookstein", title = "Hash Coding with a Non-Unique Search Key", journal = j-J-AM-SOC-INF-SCI, volume = "25", number = "4", pages = "232--236", month = jul # "--" # aug, year = "1974", CODEN = "AISJB6", ISSN = "0002-8231", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "This paper defines a hash coding model for nonunique search keys and derives the expected number of accesses needed to retrieve all desired records from a computer storage device. The assumption that the records are stored on the basis of a nonunique key is often realized in information retrieval environments. The model assumes that the hashing algorithm and, should a collision occur, the skipping algorithm, both distribute the records randomly in memory. The results of this analysis are compared with those from a simulation in which the randomness criterion is not strictly met.", acknowledgement = ack-nhfb, classification = "723; 731; 901", journalabr = "J Am Soc Inf Sci", keywords = "codes, symbolic --- Encoding; hash coding; information retrieval systems; information science", } @Article{deVillers:1974:HSS, author = "E. v. d. S. {de Villers} and L. B. Wilson", title = "Hashing the Subscripts of a Sparse Matrix", journal = j-BIT, volume = "14", number = "3", pages = "347--358", year = "1974", CODEN = "BITTEL, NBITAB", ISSN = "0006-3835", bibdate = "Sat Nov 14 20:58:37 1998", acknowledgement = ack-nhfb, annote = "Yes, first author name is ``E. v. d. S. {de Villers}''", keywords = "nla, sparse, hashing", } @Article{DeVilliers:1974:HSS, author = "E. v. d. S. {De Villiers} and L. B. Wilson", title = "Hashing the Subscripts of a Sparse Matrix", journal = "BIT (Copenhagen)", volume = "14", number = "3", pages = "347--358", month = "????", year = "1974", CODEN = "NBITAB", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "It has been suggested that key transformation techniques might be a very effective way of manipulating sparse matrices particularly if the operations on the matrix access the elements in an unsystematic way. The purpose of the present paper is to investigate methods of hashing the subscripts of a matrix to give a suitable address in the scatter storage table. Various different types of sparse matrices are considered.", acknowledgement = ack-nhfb, classification = "723", journalabr = "BIT", keywords = "computer programming; data processing --- File Organization", } @Article{Ecker:1974:BRL, author = "A. Ecker", title = "{Eine Bemerkung zum Restklassenhash} [{Remark} on the Division Hash Code]", journal = "Angewandte Informatik/Applied Informatics", volume = "16", number = "6", pages = "253--256", month = jun, year = "1974", CODEN = "AWIFA7", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "A file addressing problem is proved to be equivalent to a problem in the theory of AN codes for the division hash code. Results in the theory of AN codes can thus be used in solving this file addressing problem. An algorithm is given to obtain the right table length.", acknowledgement = ack-nhfb, classification = "723", journalabr = "Angew Inf Appl Inf", keywords = "codes, symbolic; data processing --- File Organization", } @Article{Ecker:1974:PSQ, author = "A. Ecker", title = "Period of Search for the Quadratic and Related Hash Methods", journal = j-COMP-J, volume = "17", number = "4", pages = "340--343", month = nov, year = "1974", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "A systematic approach to estimate the period of search for the quadratic hash method is presented. A generalization of that method is given and upper or lower bounds for the search period are evaluated. It turns out that contrary to what is normally believed in most cases of practical interest, it is possible to search the complete table.", acknowledgement = ack-nhfb, classification = "723; 921", journalabr = "Comput J", keywords = "computer programming; hash methods; mathematical techniques", } @Article{Grimson:1974:PSS, author = "J. B. Grimson", title = "A Performance Study of Some Directory Structures for Large Data Files", journal = j-ISR, volume = "10", number = "11", pages = "??", year = "1974", bibdate = "Thu Jul 21 09:31:37 1994", acknowledgement = ack-nhfb, annote = "Tests on hashing.", } @InProceedings{Groner:1974:CHF, author = "L. H. Groner and A. L. Goel", title = "Concurrency in Hashed File Access", crossref = "Rosenfeld:1974:IPP", pages = "??", year = "1974", bibdate = "Thu Jul 21 09:31:52 1994", acknowledgement = ack-nhfb, annote = "Look-up direct access records simultaneously in primary and overflow files.", } @Article{Kaman:1974:HC, author = "Charles H. Kaman", title = "Hash Coding", journal = "Polimery", volume = "??", number = "??", pages = "229--232", month = "????", year = "1974", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Hash coding method is described for accessing tables and for implementing associative memories in software.", acknowledgement = ack-nhfb, classification = "723", conference = "Digital Equip Comput Users Soc, Fall Symp, DECUS Proc, Pap and Presentations", keywords = "codes, symbolic; computer programming; data processing; hash coding", meetingaddress = "San Francisco, CA, USA", meetingdate = "Nov 28--30 1973", meetingdate2 = "11/28--30/73", } @Article{Knuth:1974:CSR, author = "Donald E. Knuth", title = "Computer Science and its Relation to Mathematics", journal = j-AMER-MATH-MONTHLY, volume = "81", pages = "323--343", month = apr, year = "1974", CODEN = "AMMYAE", ISSN = "0002-9890", bibdate = "Fri Aug 12 23:24:40 1994", note = "A~shorter form of this article appeared in {\sl American Scientist\/ \bf 61} (1973), 707--713; reprinted in {\sl Computers and People\/ \bf 23},9 (September 1974), 8--11; and in {\sl Mathematics: People, Problems, Results}, ed.\ by Douglas M. Campbell and John C. Higgins, vol.~3 (Belmont, Calif.: Wadsworth, 1984), 37--47. Hungarian translation in {\sl Matematikai Lapok\/ \bf 24} (1973, published 1975), 345--363. Slovenian translation in {\sl Obzornik za Matematiko in Fiziko\/ \bf22} (1975), 129--138, 161--167. Slovak translation (abridged) in {\sl Pokroky Matematiky, Fiziky a Astronomie\/ \bf21} (1976), 88--96. Russian translation by Natal'{\t\i{a}} G. Gurevich in {\sl Sovremennye Problemy Matematiki\/ \bf11},12 (Moscow: Znanie, 1977), 4--32.", acknowledgement = ack-nhfb, } @Article{Knuth:1974:OHT, author = "Donald E. Knuth and O. Amble", title = "Ordered hash tables", journal = j-COMP-J, volume = "17", pages = "135--142", year = "1974", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Fri Aug 12 23:24:40 1994", acknowledgement = ack-nhfb, } @TechReport{Rivest:1974:AAR, author = "Ronald L. Rivest", title = "Analysis of Associative Retrieval Algorithms", type = "Technical Report", number = "TR.54", institution = "Institut de la Recherche en Informatique et Automatique, now Institut National de Recherche en Informatique et Automatique (INRIA)", address = "Domaine de Voluceau --- Rocquencourt --- B.P. 105, 78153 Le Chesnay Cedex, France", pages = "??", month = feb, year = "1974", bibdate = "Thu Jul 21 09:32:07 1994", note = "Also published in/as: Stanford CSD report 74-415. Also published in/as: SIAM Journal for Computing, Springer Verlag (Heidelberg, FRG and New York NY, USA)-Verlag, 1976, with mod. title.", acknowledgement = ack-nhfb, annote = "Combinatorial hashing for retrieval.", } @InProceedings{Rivest:1974:HCA, author = "R. L. Rivest", title = "On hash-coding algorithms for partial-match retrieval", crossref = "IEEE:1974:ASS", pages = "95--103", year = "1974", bibdate = "Mon Jul 18 10:06:22 1994", acknowledgement = ack-nhfb, } @Article{Rothnie:1974:ABF, author = "James B. {Rothnie, Jr.} and Tomas Lozano", title = "Attribute Based File Organization in a Paged Memory Environment", journal = j-CACM, volume = "17", number = "2", pages = "63--69", month = feb, year = "1974", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Fri Apr 30 11:16:38 1999", note = "See remarks \cite{Chang:1984:OIR}.", acknowledgement = ack-nhfb, } @Article{Severance:1974:ISM, author = "Dennis G. Severance", title = "Identifier Search Mechanisms: {A} Survey and Generalized Model", journal = j-COMP-SURV, volume = "6", number = "3", pages = "175--194", month = sep, year = "1974", CODEN = "CMSVAN", ISSN = "0360-0300", bibdate = "Sun Sep 18 11:25:49 1994", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib", acknowledgement = ack-nhfb, annote = "Evaluation model is core memory oriented.", } @Book{Waldschmidt:1974:OIC, author = "Helmut Waldschmidt", title = "Optimierungsfragen im Compilerbau", publisher = pub-HANSER, address = pub-HANSER:adr, pages = "154", year = "1974", ISBN = "3-446-11895-0", ISBN-13 = "978-3-446-11895-9", LCCN = "QA76.6 .W326", bibdate = "Wed Jul 13 19:00:58 1994", acknowledgement = ack-nhfb, descriptor = "Compilerbau, Globale Programmoptimierung, Hash-verfahren, Optimierung, Tabellenorganisation, Uebersetzer", } @Article{Atkinson:1975:HMS, author = "L. V. Atkinson", title = "Hashing Matrix Subscripts", journal = j-BIT, volume = "15", number = "3", pages = "328--330", year = "1975", CODEN = "BITTEL, NBITAB", ISSN = "0006-3835", bibdate = "Mon Nov 16 14:36:22 1998", acknowledgement = ack-nhfb, } @Article{Batagelj:1975:QHM, author = "Vladimir Batagelj", title = "Quadratic Hash Method When the Table Size is not a Prime Number", journal = j-CACM, volume = "18", number = "4", pages = "216--217", month = apr, year = "1975", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Previous work on quadratic hash methods is limited mainly to the case where the table size is a prime number. Here, certain results are derived for composite numbers. It is shown that all composite numbers containing at least the square of one of the component primes have full-period integer-coefficient quadratic hash functions.", acknowledgement = ack-nhfb, classification = "723", journalabr = "Commun ACM", keywords = "computer programming", } @Article{Bobrow:1975:NHL, author = "Daniel G. Bobrow", title = "A Note on Hash Linking", journal = j-CACM, volume = "18", number = "7", pages = "413--415", month = jul, year = "1975", CODEN = "CACMA2", ISSN = "0001-0782", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "Hash searching is a technique in which a key is mapped into a unique address associated with that key. Most applications of this technique are for insertion and fast retrieval of data records containing key fields. In the use of hash search described in this paper, the key field is the virtual address of a machine cell with which additional information is associated. An address to auxiliary data not contained in that cell is called hash linking. (A hash link function is one which maps any machine virtual address into another unique address where additional information can be stored. ) This note describes several nonobvious applications of this technique.", acknowledgement = ack-nhfb, classification = "723; 901", journalabr = "Commun ACM", keywords = "computer programming; hash linking; information retrieval systems; LISP", } @InProceedings{Burkhard:1975:PMQ, author = "Walter A. Burkhard", title = "Partial-Match Queries and File Designs", crossref = "Kerr:1975:PIC", pages = "??", year = "1975", bibdate = "Thu Jul 21 08:44:14 1994", acknowledgement = ack-nhfb, annote = "Tries and hashing.", } @InProceedings{Deutscher:1975:CSD, author = "R. F. Deutscher and R. P. Tremblay and P. G. Sorenson", title = "A Comparative Study of Distribution-Dependent and Distribution-Independent Hashing Functions", crossref = "ACM:1975:DUO", pages = "??", year = "1975", bibdate = "Sat Nov 12 21:01:57 1994", note = "Also published in/as: Dept. Computational Science, Report 75.4, Mar. 1975.", acknowledgement = ack-nhfb, } @TechReport{Dubost:1975:SIN, author = "P. Dubost and J.-M. Trousse", title = "Software Implementation of a new Method of Combinatorial Hashing", number = "STAN-CS-75-511", institution = "Stanford University Computer Science Department", pages = "??", month = sep, year = "1975", bibdate = "Sat Nov 12 21:02:07 1994", acknowledgement = ack-nhfb, annote = "An Implementation of Burkhard's partial match retrieval scheme using binary trees instead of binary strings.", } @Article{Goble:1975:FRS, author = "C. E. Goble", title = "Free-Text Retrieval System Using Hash Codes", journal = j-COMP-J, volume = "18", number = "1", pages = "18--20", month = feb, year = "1975", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "An algorithm is presented for efficient serial searching of files whose records have arbitrary length free-text retrieval keys. It is most applicable when a batch of enquiries is to search a given file once only, which is an implicit feature of the SDI (Selective Dissemination of Information) application for which it was designed. Unlike some other serial systems, an arbitrary number of enquiries can be handled with a single pass of the search file, and the algorithm is simple in concept, and straightforward to implement. Specimen performance figures are quoted in the appendix.", acknowledgement = ack-nhfb, classcodes = "C6120 (File organisation); C7220 (Generation, dissemination, and use of information); C7250 (Information storage and retrieval)", classification = "723", corpsource = "IEE, London, UK", journalabr = "Comput J", keywords = "algorithm; arbitrary length; data processing; files; free text; hash codes; information dissemination; information retrieval systems; keys; retrieval system; SDI; serial searching", treatment = "P Practical", } @InProceedings{Guibas:1975:HTE, author = "Leo J. Guibas", booktitle = "USA-Jpn Comput Conf, 2nd, Proc", title = "Hashing Techniques that Exhibit Secondary or Tertiary Clustering", publisher = "AFIPS", address = "Montvale, NJ", pages = "324--328", year = "1975", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "A hashing technique is said to exhibit secondary (or tertiary) clustering, if it begins a search into the table with one random probe (or two independently random probes) and from then on proves the table positions in a fixed permutation that depends only on the location of the initial probe (or the locations of the two initial probes). The performance of such a hashing technique is analyzed when the permutations described above are randomly chosen. The results obtained contribute insight to the issue of comparing alternate strategies for collision resolution.", acknowledgement = ack-nhfb, classification = "723", keywords = "computer programming", meetingaddress = "Tokyo, Jpn", meetingdate = "Aug 26--28 1975", meetingdate2 = "08/26--28/75", } @Article{Herschel:1975:WHL, author = "R. Herschel and B. Jonsson", title = "{Was ist Hash-coding}? [What Is Hash-Coding?]", journal = "{Elektronische Rechenanlagen mit Computer Praxis}", volume = "17", number = "4", pages = "131--138", month = jun, year = "1975", CODEN = "ERCPDJ", bibdate = "Mon Oct 26 07:01:32 1998", bibsource = "Compendex database", abstract = "Hash-coding is an effective method for the retrieval of single data items within large quantities of data. Two problems associated with the utilization of hash-coding in practice are pointed out.", acknowledgement = ack-nhfb, classification = "723", journalabr = "Elektron Rechenanlagen Comput Prax", keywords = "codes, symbolic; hash coding", language = "German", } @Article{Knott:1975:HF, author = "G. D. Knott", title = "Hashing Functions", journal = j-COMP-J, volume = "18", number = "3", pages = "265--278", month = aug, year = "1975", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "Compendex database", abstract = "The object of this paper is to survey various hashing functions, to present a brief history of hashing schemes and their development, and to give an exhaustive bibliography on hashing and hash table storage and retrieval methods.", acknowledgement = ack-nhfb, classification = "921; 901", journalabr = "Comput J", keywords = "hashing functions; information retrieval systems; mathematical techniques", } @Article{Knott:1975:HFH, author = "Gary D. Knott", title = "Hashing Functions and Hash Table --- Storage and Retrieval", journal = j-COMP-J, volume = "18", number = "3", pages = "265--278", month = aug, year = "1975", CODEN = "CMPJA6", ISSN = "0010-4620", bibdate = "Tue Jul 19 22:44:05 1994", bibsource = "Compendex database", note = "Also published in/as: Stanford University Report, 1975.", acknowledgement = ack-nhfb, annote = "All you wanted to know about hashing.", classification = "901; 921", keywords = "hashing functions; information retrieval systems; mathematical techniques", } @Book{Knuth:1975:ACP, author = "D. E. Knuth", title = "The Art of Computer Programming, Sorting and Searching", publisher = pub-AW, address = pub-AW:adr, edition = "2", pages = "xi + 723", year = "1975", ISBN = "0-201-03803-X", ISBN-13 = "978-0-201-03803-3", LCCN = "QA76.5 .K74", bibdate = "Wed Jul 13 18:55:26 1994", acknowledgement = ack-nhfb, annote = "Standardwerk ueber Suchen und Sortieren 5. Sorting 5.1. Combinatorial Properties of Permutations 5.2. Internal Sorting 5.3. Optimum Sorting 5.4. External Sorting 5.5. Summary, History, and Bibliography 6. Searching 6.1. Sequential Search 6.2. Searching By Comparison of Keys 6.3. Digital Searching 6.4. Hashing 6.5. Retrieval on Secondary Keys Answers to Exercises Appendix A: Tables of Numerical Quantities Appendix B: Index to Notations Index and Glossary.", descriptor = "Algorithmus, B-baum, Baum, Binaer-baum, Gestreute Speicherung, Hash-verfahren, Mischen, Sortieren, Speicherung, Suchen, Zugriff", } @Book{Martin:1975:CDB, author = "James Martin", title = "Computer Data-base Organization", publisher = pub-PH, address = pub-PH:adr, pages = "xviii + 558", year = "1975", ISBN = "0-13-165506-X", ISBN-13 = "978-0-13-165506-5", LCCN = "QA76 .M324", bibdate = "Thu Jul 14 16:38:51 1994", acknowledgement = ack-nhfb, annote = "Contents: Part I: Logical Organization 4. What Should be the Objectives of a Data Base Organization 5. Entities and Attributes 6. Schemas and Subschemas 7. Data Base Management Systems 8. Tree Structures 9. Plex Structures 10. Data Description Languages 11. The Codasyl Data Description Language 12. IBM's Data Language/I 13. Relational Data Bases 14. Third Normal Form 15. Varieties of Data Independence 16. Operations Systems Versus Information Systems Part II: Physical Organization 17. Criteria Affecting Physical Organization 18. Differences Between Physical and Logical Organiation 19. Pointers 20. Chains and Ring Structures 21. Addessing Techniques 22. Indexed Sequential Organizations 23. Hashing 24. Physical Representations of Tree Structures 25. Physical Representations of Plex Structures 26. Multiple-key Retrieval 27. Index Organization 28. A Comparison of Multiple-key Organizations 29. Separating Data and Relationships 30. Index Searching Techniques 31. Data Compaction 32. Virtual Memory and Storage Hierarchies 33. Inverted File Systems 34. Volatile Files 35. Fast Response Systems 36. Associative Memory App. A. The Mean Number of Probes in a Binary Search App. B. Sample Logical Data Descriptions Class Questions Index.", descriptor = "Computer, Datenbank, Datenbanksystem, Datenfernverarbeitung, Informationssystem, Datenorganisation, Datenuebertragung, Datenverwaltung, Dokumentationssystem, Organisation, Relationen-modell, Software-technologie", } @Article{Maurer:1975:HTM, author = "W. D. Maurer and T. G. Lewis", title = "Hash Table Methods", journal = j-COMP-SURV, volume = "7", number = "1", pages = "5--19", month = mar, year = "1975", CODEN = "CMSVAN", ISSN = "0360-0300", bibdate = "Sat Jan 25 17:38:12 MST 1997", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Database/Wiederhold.bib, Compendex database", abstract = "This is a survey of hash table methods, chiefly intended for programmers and students of programming who are encountering the subject for the first time. The better-known methods of calculating hash addresses and of handling collisions and bucket overflow are presented and compared. It is shown that under certain conditions we can guarantee that no two items belonging to a certain class will have the same hash code, thus providing an improvement over the usual notion of a hash code as a randomizing technique. Several alternatives to hashing are discussed, and suggestions are made for further research and further development.", acknowledgement = ack-nhfb, annote = "Short review of key-to-address transformation, collision handling, and other access techniques.", classification = "723", journalabr = "Comput Surv", keywords = "computer programming", } @Book{Niemeyer:1975:DV, author = "Gerhard Niemeyer", title = "Dateiorganisation und -verarbeitung", publisher = pub-VAHLEN, address = pub-VAHLEN:adr, pages = "258", year = "1975", ISBN = "3-8006-0528-7", ISBN-13 = "978-3-8006-0528-6", LCCN = "QA76 .N52", bibdate = "Wed Jul 13 18:39:58 1994", price = "DM24.80", acknowledgement = ack-nhfb, annote = "1. Einfuehrung und Grundlagen 2. Dateistrukturen, Speicherkonzepte und Elementare Algorithmen 3. Sortierverfahren 4. Suchverfahren.", descriptor = "Baum, Binaer-baum, Dateiorganisation, Dateiverwaltung, Datenverwaltung, Gestreut, Hashing, Indexsequentiell, Liste, Mischen, Serielle Speicherung, Sortieren, Speicherung, Suchen, Verkettet, Zugriff", } @Article{Ramamohanarao:1975:DHS, author = "K. Ramamohanarao and J. W. Lloyd", title = "Dynamic Hashing Schemes", journal = j-COMP-J # " (to appear)", volume = "??", number = "??-??", pages = "??", year = "1975", bibdate = "Thu Jul 21 08:44:26 1994", acknowledgement = ack-nhfb, } @InProceedings{Rosenberg:1975:HSE, author = "A. L. Rosenberg and L. J. Stockmeyer", title = "Hashing schemes for extendible arrays", crossref = "ACM:1975:CRS", pages = "159--166", year = "1975", bibdate = "Mon Jul 18 10:15:45 1994", acknowledgement = ack-nhfb, } @InProceedings{Sorenson:1975:DDH, author = "P. G. Sorenson and R. F. Deutscher and J. P. Tremblay", booktitle = "19 ACM SIGMOD Conf. on the Management of Data, King(ed)", title = "Distribution-Dependent Hashing Functions and Their Characteristics", publisher = pub-ACM, address = pub-ACM:adr, pages = "??", month = may, year = "1975", bibdate = "Thu Jul 21 09:32:27 1994", acknowledgement = ack-nhfb, } @Book{Wirth:1975:AD, author = "Niklaus Wirth", title = "Algorithmen und Datenstrukturen", publisher = pub-TEUBNER, address = pub-TEUBNER:adr, pages = "376", year = "1975", ISBN = "3-519-02330-X", ISBN-13 = "978-3-519-02330-2", LCCN = "QA76.9.D35 W57", price = "DM26.80", acknowledgement = ack-nhfb, annote = "Inhalt: 1. Fundamentale Datenstrukturen 2. Sortieren 3. Rekursive Algorithmen 4. Dynamische Informationsstrukturen Einfuehrung in Theorie und Praxis Fundamentaler Algorithmen. Ausfuehrliche Anleitung zur Wahl Geeigneter Datenstrukturen. Methodik Rekursiver Programme, Suchen und Sortieren. Beispielprogramme in Pascal-notation.", descriptor = "Algorithmus, Baum, Datenstruktur, Digitalrechner, Grundstruktur, Hashing, Liste, Programmierung, Referenz, Rekursion, Sortieralgorithmus, Sortieren, Zeiger", } @Article{Bayer:1976:EST, author = "R. Bayer and J. K. Metzger", title = "On the Encipherment of Search Trees and Random Access Files", journal = j-TODS, volume = "1", number = "1", pages = "37--52", month = mar, year = "1976", CODEN = "ATDSD3", ISSN = "0362-5915", bibdate = "Wed Jul 20 23:01:51 1994", note = "Also published in \cite[p.~508--510]{Kerr:1975:PIC}.", acknowledgement = ack-nhfb, annote = "Trees versus hashing as his 1974 IFIP paper?", } @InProceedings{Burkhard:1976:ART, author = "Walter A. Burkhard", title = "Associative retrieval trie hash-coding", crossref = "ACM:1976:CRE", pages = "211--219", year = "1976", bibdate = "Mon Jul 18 10:17:50 1994", acknowledgement = ack-nhfb, } @Article{Burkhard:1976:HTA, author = "Walter A. Burkhard", title = "Hashing and Trie Algorithms for Partial-Match Retrieval", journal = j-TODS, volume = "1", number = "2", pages = "175--187", year = "1976", CODEN = "ATDSD3", ISSN = "0362-5915", bibdate = "Wed Jul 13 21:41:17 1994", note = "Also published in/as: UCSD, Appl. Physics and Inf. Sc, CS TR.2, Jun. 1975.", acknowledgement = ack-nhfb, } @Article{Burkhard:1976:PMR, author = "Walter A. Burkhard", title = "Partial Match Retrieval", journal = j-BIT, volume = "16", number = "1", pages = "13--31", year = "1976", CODEN = "BITTEL, NBITAB", ISSN = "0006-3835",