The analysis of closed hashing under limited randomness

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The analysis of closed hashing under limited randomness

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-second annual ACM symposium on Theory of computing table of contents

Baltimore, Maryland, United States

Pages: 224 - 234

Year of Publication: 1990

ISBN:0-89791-361-2

Authors

J. P. Schmidt	Department of Computer Science, Polytechnic University, 333 Jay Street, Brooklyn, NY
A. Siegel	Department of Computer Science, Courant Institute, 251 Mercer Street, N.Y.C. NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 24, Citation Count: 11

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/100216.100245 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.

	AKS-78	M. Ajtai, J. Koml6s, E. Szemerddi. "There Is No Fast Single Hashing Algorithm," IPL, 7,6, 1978, pp. 270-273.
	BBS	Béla Bollobás , Andrei Z. Broder , Istvan Simon, The cost distribution of clustering in random probing, Journal of the ACM (JACM), v.37 n.2, p.224-237, April 1990 [doi>10.1145/77600.77619]
	CW-79	J. L. Carter and M. N. Wegman "Universal Classes of Hash Functions," JCSS, 18, 1979, pp. 143- 154.
	GS-78	L. Guibas and E. Szemerddi. "The Analysis of Double Hashing," JCSS, 16, 1978, pp. 226-274.
	Kn-73	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
	LM-88	George Lueker , Mariko Molodowitch, More analysis of double hashing, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.354-359, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62246]
	Me-84	K. Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching, Springer-Verlag, Berlin Heidelberg, 1984.
	S-89	A. Siegel. "On universal classes of fast hash functions, their time-space tradeoff, and their applications," 30th FOCS, Oct., 1989,pp. 20-25.
	SS-89	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]
	Ul-72	J. D. Ullman, A Note on the Efficiency of Hashing Functions, Journal of the ACM (JACM), v.19 n.3, p.569-575, July 1972 [doi>10.1145/321707.321722]
	WC-79	M. N. Wegman and 3. L. Carter. "New Classes and Applications of Hash Functions," 20th FOCS, Oct., 1979, pp. 175-182.
	Ya-85	Andrew C. Yao, Uniform hashing is optimal, Journal of the ACM (JACM), v.32 n.3, p.687-693, July 1985 [doi>10.1145/3828.3836]

CITED BY 11

	Moni Naor , Vanessa Teague, Anti-presistence: history independent data structures, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.492-501, July 2001, Hersonissos, Greece
	Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
	Alan Siegel, On the statistical dependencies of coalesced hashing and their implications for both full and limited independence, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.10-19, January 22-24, 1995, San Francisco, California, United States
	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
	Anna Ostlin , Rasmus Pagh, Uniform hashing in constant time and linear space, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Rasmus Pagh , Flemming Friche Rodler, Cuckoo hashing, Journal of Algorithms, v.51 n.2, p.122-144, May 2004
	Mette Berger , Esben Rune Hansen , Rasmus Pagh , Mihai Pǎtraşcu , Milan Ružić , Peter Tiedemann, Deterministic load balancing and dictionaries in the parallel disk model, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Anna Pagh , Rasmus Pagh , Milan Ruzic, Linear probing with constant independence, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
	Michael Mitzenmacher , Salil Vadhan, Why simple hash functions work: exploiting the entropy in a data stream, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.746-755, January 20-22, 2008, San Francisco, California
	Mikkel Thorup, String hashing for linear probing, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.655-664, January 04-06, 2009, New York, New York
	Yuval Rabani , Amir Shpilka, Explicit construction of a small epsilon-net for linear threshold functions, Proceedings of the 41st annual ACM symposium on Theory of computing, May 31-June 02, 2009, Bethesda, MD, USA