Practical minimal perfect hash functions for large databases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Practical minimal perfect hash functions for large databases

Full text

Pdf (2.00 MB)

Source

Communications of the ACM archive
Volume 35 , Issue 1 (January 1992) table of contents

Pages: 105 - 121

Year of Publication: 1992

ISSN:0001-0782

Authors

Edward A. Fox	Virginia Polytechnic Institute and State Univ., Blacksburg, VA
Lenwood S. Heath	Virginia Polytechnic Institute and State Univ., Blacksburg, VA
Qi Fan Chen	Virginia Polytechnic Institute and State Univ., Blacksburg, VA
Amjad M. Daoud	Western Geophysical, Houston, TX

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 25, Downloads (12 Months): 138, Citation Count: 18

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129617.129623 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Marshall D. Brain , Alan L. Tharp, Near—perfect hashing of large word sets, Software—Practice & Experience, v.19 n.10, p.967-978, Oct. 1989 [doi>10.1002/spe.4380191005]
	2	Carter, J.L., and Wegman, M.N. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 2 (1979), 143- 154.
	3	Cercone, N., Krause, M., and Boates, J. Minimal and almost minimal perfect hash function search with application to natural language lexicon design. Comput. Math. Appli. 9, 1 (1983), 215-23t.
	4	C. C. Chang, The study of an ordered minimal perfect hashing scheme, Communications of the ACM, v.27 n.4, p.384-387, April 1984 [doi>10.1145/358027.358051]
	5	C C Chang, Letter-oriented reciprocal hashing scheme, Information Sciences: an International Journal, v.38 n.3, p.243-255, June 1986 [doi>10.1016/0020-0255(86)90024-1]
	6	Richard J. Cichelli, Minimal perfect hash functions made simple, Communications of the ACM, v.23 n.1, p.17-19, Jan. 1980 [doi>10.1145/358808.358813]
	7	Cormack, G.V., Horspool, R.N.S., and Kaiserswerth, M. Practical perfect hashing. The Comput. J. 28, t (1985), 54-58.
	8	Amjad M. Daoud, Efficient data structures for information retrieval, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1993
	9	Sanjeev Datta , Edward A. Fox, Implementation of a Perfect Hash Function Scheme, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1989
	10	R. J. Enbody , H. C. Du, Dynamic hashing schemes, ACM Computing Surveys (CSUR), v.20 n.2, p.850-113, June 1988 [doi>10.1145/46157.330532]
	11	Fctler, W. An Introduction to Probability Theory and its Applications, Vol. t. John Wile}.' and Suns, N.Y., 1968.
	12	Fox, E.A. Optical disks and CD- R()M' Publishing and access, in Annual Review of Information Science and Technoto~,, Martha E. Williams, Ed. ASIS/E!sevier Scicnce Publishers B.V., Amsterdam, Vol. 23, 1988, 85-124.
	13	F~x, F.A. Virginia Disc One. CD- ROM dcvcloped at Virginia Polytechnic institute and State University, published by VPI&SU Press, and produced by Nimbus Records, Ruckersville, Va, 1990.
	14	E. A. Fox , Q. F. Chen , A. M. Daoud , L. S. Heath, Order preserving minimal perfect hash functions and information retrieval, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.279-311, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98233]
	15	Edward A. Fox , Qi Fan Chen , Amjad M. Daoud , Lenwood S. Heath, Order-preserving minimal perfect hash functions and information retrieval, ACM Transactions on Information Systems (TOIS), v.9 n.3, p.281-308, July 1991 [doi>10.1145/125187.125200]
	16	E. A. Fox , Q.-F. Chen , L. Heath , S. Datta, A more cost effective algorithm for finding perfect hash functions, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.114-122, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75440]
	17	Edward A. Fox , Lenwood S. Heath , Qi Chen, An O(n log n) Algorithm for Finding Minimal Perfect Hash Functions, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1989
	18	Fox, E.A., Nutter, .I.'1' Ahiswede, T., Evens, M. and Markowitz, {.
	19	Edward A. Fox , Robert C. Wohlwend , Phyllis R. Sheldon , Qi Chen , Robert K. France, Building the CODER Lexicon: The Collins English Dictionary and Its Adverb Definitions, Virginia Polytechnic Institute & State University, Blacksburg, VA, 1986
	20	Michael L. Fredman , János Komlós , Endre Szemerédi, Storing a Sparse Table with 0(1) Worst Case Access Time, Journal of the ACM (JACM), v.31 n.3, p.538-544, July 1984 [doi>10.1145/828.1884]
	21	Gonnet G.L. and latsore P. Exter nal instalingf with limited internal storage JK.
	22	Hanks P. ed. Collins English Dictionary. William Collings and Co. London, 1979.
	23	G. Jaeschke, Reciprocal hashing: a method for generating minimal perfect hashing functions, Communications of the ACM, v.24 n.12, p.829-833, Dec. 1981 [doi>10.1145/358800.358806]
	24	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	25	Mairson, H.G. 'l'hc program complexity of searching a table. In Proceedi.ngs of' the 24th fEEE Symposium on Foundations of Computer Science (Tucson, Ariz., Nov. 7-9), 1983, 40-47.
	26	Mchlhorn, K. On the program size of perfect and universal hash functions, tn Proceedings of the 23d IEEE Symposium on Foundations of Computer Science (Chicago, I11. Nov. 3-5, 1982), 170-175.
	27	Edgar M. Palmer, Graphical evolution: an introduction to the theory of random graphs, John Wiley & Sons, Inc., New York, NY, 1985
	28	S. K. Park , K. W. Miller, Random number generators: good ones are hard to find, Communications of the ACM, v.31 n.10, p.1192-1201, Oct. 1988 [doi>10.1145/63039.63042]
	29	Peter K. Pearson, Fast hashing of variable-length text strings, Communications of the ACM, v.33 n.6, p.677-680, June 1990 [doi>10.1145/78973.78978]
	30	M. V. Ramakrishna , P.-:1V Larson, File organization using composite perfect hashing, ACM Transactions on Database Systems (TODS), v.14 n.2, p.231-263, June 1989 [doi>10.1145/63500.63521]
	31	Sagar J. A new method for gen creating minimal perfect hashing funcations fedss rep Dept of computer sciences univer versity ofMissouri rolla Mo 1981.
	32	Thomas J. Sager, A polynomial time generator for minimal perfect hash functions, Communications of the ACM, v.28 n.5, p.523-532, May 1985 [doi>10.1145/3532.3538]
	33	J. P. Schmidt , A. Siegel, On aspects of university and performance for closed hashing, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.355-366, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73041]
	34	Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
	35	Renzo Sprugnoli, Perfect hashing functions: a single probe retrieving method for static sets, Communications of the ACM, v.20 n.11, p.841-850, Nov. 1977 [doi>10.1145/359863.359887]

CITED BY 18

	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Dennis J. Brueni , Baziley T. Cross , Edward A. Fox , Lenwood S. Heath , Deborah Hix , Lucy T. Nowell , William C. Wake, What if there were desktop access to the computer science literature?, Proceedings of the 1993 ACM conference on Computer science, p.15-22, February 16-18, 1993, Indianapolis, Indiana, United States
	Jin Wang, Parallel construction of minimal perfect hashing functions with neural networks, Proceedings of the 1993 ACM conference on Computer science, p.265-271, February 16-18, 1993, Indianapolis, Indiana, United States
	Edward A. Fox , Qi Fan Chen , Lenwood S. Heath, A faster algorithm for constructing minimal perfect hash functions, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.266-273, June 21-24, 1992, Copenhagen, Denmark
	Martin Dietzfelbinger , Philipp Woelfel, Almost random graphs with simple hash functions, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Marina Blanton , Mikhail J. Atallah, Provable bounds for portable and flexible privacy-preserving access, Proceedings of the tenth ACM symposium on Access control models and technologies, June 01-03, 2005, Stockholm, Sweden
	Tim Moors , Antonio Cantoni, Cascading Content-Addressable Memories, IEEE Micro, v.12 n.3, p.56-66, May 1992
	M. D. Brain , A. L. Tharp, Using Tries to Eliminate Pattern Collisions in Perfect Hashing, IEEE Transactions on Knowledge and Data Engineering, v.6 n.2, p.239-247, April 1994
	Zhiyu Tian , Shibai Tong , Shiyuan Yang, A new hashing function: statistical behaviour and algorithm, ACM SIGIR Forum, v.27 n.1, p.3-13, Spring 1993
	Strahil Ristov, LZ trie and dictionary compression, Software—Practice & Experience, v.35 n.5, p.445-465, 25 April 2005
	Fabiano C. Botelho , Nivio Ziviani, External perfect hashing for very large key sets, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal
	John A. Trono, Optimal table lookup for reserved words in Ada, ACM SIGAda Ada Letters, v.XXVI n.1, April 2006
	Sylvain Lefebvre , Hugues Hoppe, Perfect spatial hashing, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
	Marina Blanton , Mikhail Atallah, Succinct representation of flexible and privacy-preserving access rights, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.4, p.334-354, November 2006
	Justin Zobel , Alistair Moffat , Ron Sacks-Davis, Searching Large Lexicons for Partially Specified Terms using Compressed Inverted Files, Proceedings of the 19th International Conference on Very Large Data Bases, p.290-301, August 24-27, 1993
	John A. Trono, A comparison of three strategies for computing letter oriented, minimal perfect hashing functions, ACM SIGPLAN Notices, v.30 n.4, p.29-35, April 1995
	Amjad M. Daoud, Perfect hash functions for large dictionaries, Proceedings of the ACM first workshop on CyberInfrastructure: information management in eScience, November 09-09, 2007, Lisbon, Portugal
	Giovani Gracioli , Sebastian Fischmeister, Tracing interrupts in embedded software, ACM SIGPLAN Notices, v.44 n.7, July 2009