Is linear hashing good?

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Is linear hashing good?

Full text

Pdf (1.42 MB)

Source

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

El Paso, Texas, United States

Pages: 465 - 474

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Noga Alon	Dep. of Math., Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel and Institute for Advanced Study, Princeton, NJ
Martin Dietzfelbinger	Fachbereich Informatik, Lehrstuhl II, Universität Dortmund, D-44221 Dortmund, Germany
Peter Bro Miltersen	BRICS, Centre of the Danish National Research Foundation, University of Aarhus, Ny Munkegade, Aarhus, Denmark
Erez Petrank	DIMACS, P.O.Box 1179, Piscataway, NJ
Gábor Tardos	Mathematical Institute of the Hungarian Academy of Sciences, Pf. 127, Budapest, H-1364 Hungary and Institute for Advanced Study, Princeton, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 25, Citation Count: 3

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

	ABI86	Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
	ABM87	N. Alon, A. Barak and U. Manber, On disseminating information reliably without broadcasting, in: Proc. 7fh International Conference on Distributed Computing Systems (ICDS), Berlin, 1987, pp. 74-81.
	AS92	N. Alon and J. H. Spencer, The Probabilistic Method, Wiley, New York, 1992.
	AHNR95	Arne Andersson , Torben Hagerup , Stefan Nilsson , Rajeev Raman, Sorting in linear time?, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.427-436, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225173]
	CW79	J.L. Carter and M.N. Wegman, Universal classes of hash functions, Or. Comput. Syst. Sci. 18 (1979) 143-154.
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	DHKP93	M. Dietzfelbinger, T. Hagerup, J. Katajaihen, and M. Penttonen, A reliable randomized algorithm for the closest-pair problem, Technical Report 513, Fachbereich Informatik, Universit~t Dortmund, 1993.
	DM90	M. Dietzfelbinger , Friedhelm Meyer auf der Heide, A new universal class of hash functions and dynamic hashing in real time, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.6-19, July 1990, Warwick University, England
	DKMHRT94	Martin Dietzfelbinger , Anna Karlin , Kurt Mehlhorn , Friedhelm MeyerAuf Der, Dynamic Perfect Hashing: Upper and Lower Bounds, SIAM Journal on Computing, v.23 n.4, p.738-761, Aug. 1994 [doi>10.1137/S0097539791194094]
	DGMP92	Martin Dietzfelbinger , Joseph Gil , Yossi Matias , Nicholas Pippenger, Polynomial Hash Functions Are Reliable (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.235-246, July 13-17, 1992
	FKS84	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]
	GBY90	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	GR90	S.W. Graham and C.J. Ringrose, Lower bounds for least quadratic nonresidues, in: Analytic Number Theory: Proceedings of a Conference in Honor of P.T. Bateman, B.C. Berndt et al. (Eds.), Birkh~iuser, Boston, 1990.
	MCW78	G. Markowsky, J.L. Carter, and M.N. Wegman, Analysis of a universal class of hash functions, in: Proc. 7th Conference on Math. Found. of Computer Science (MFCS), 1978, Springer LNCS 64, pp. 345- 354.
	MV84	Kurt Mehlhorn , Uzi Vishkin, Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories, Acta Informatica, v.21 n.4, p.339-374, Nov. 1984
	MNT93	Yishay Mansour , Noam Nisan , Prasoon Tiwari, The computational complexity of universal hashing, Theoretical Computer Science, v.107 n.1, p.121-133, Jan. 4, 1993 [doi>10.1016/0304-3975(93)90257-T]
	PA95	J. Pach and P.K. Agarwal, Combinatorial Geometry, Wiley 1995.
	S89	A. Siegel, On universal classes of fast high performance hash functions, their timespace tradeoff, and their application, in: Proc. 30th iEEE Symposium on Foundations of Computer Science, 1989, pp. 20-25.
	VC71	V.A. Vapnik and A.Y. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Prob. Applications 16 (1971) 264-280.

CITED BY 3

	Andrei Z. Broder , Uriel Feige, Min-Wise versus linear independence (extended abstract), Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.147-154, January 09-11, 2000, San Francisco, California, United States
	Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States
	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