ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Not all keys can be hashed in constant time
Full text PdfPdf (735 KB)
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: 244 - 253  
Year of Publication: 1990
ISBN:0-89791-361-2
Authors
J. Gil  Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, Israel
F. Meyer auf der Heide  Fachbereich 17, Mathematik/Informatik, Univesität. Gll Paderborn, D-4790 Paderborn, Fed.Rep. of Germany
A. Wigderson  Dept. of Gomp. Sc. Hebrew University, Jerusalem, 91904, Israel
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 0,   Downloads (12 Months): 11,   Citation Count: 4
Additional Information:

references   cited by   index terms   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/100216.100247
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
M. Dietzfelbinger , F. Meyer auf der Heide, How to distribute a dictionary in a complete network, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.117-127, May 13-17, 1990, Baltimore, Maryland, United States  [doi>10.1145/100216.100229]
 
2
Martin Dietzfelbinger , Friedhelm Meyer auf der Heide, A New Universal Class of Hash Functions and Dynamic Hashing in Real Time, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.6-19, July 16-20, 1990
 
3
[3] Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert, and Tarjan. Dynamic perfect hashing: upper an lower bounds. In 29th Annual Symposium on Foundations of Computer Science, pages 524-531, Oct. 1988.
4
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]
 
5
[5] Joseph Gil and Yossi Matias. o(log log n) time hashing on pram. Mar. 1990. In preparation.
6
A R Karlin , E Upfal, Parallel hashing—an efficient implementation of shared memory, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.160-168, May 28-30, 1986, Berkeley, California, United States  [doi>10.1145/12130.12146]
 
7
[7] Kurt Mehlhorn. Data Structures and Algorithms 1: Sorting and Searching. Springer-Verlag, Berlin Heidelberg, 1984.
8
Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983  [doi>10.1145/800061.808762]
 
9
[9] Larry Stockmeyer. A complexity approach to randomness. In Proceeding of 15th Annual ACM Symposium on Theory of Computing, pages 118-126, April 1983.
10
Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981  [doi>10.1145/322261.322274]

CITED BY  4
Holger Bast , Torben Hagerup, Fast and reliable parallel hashing, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.50-61, July 21-24, 1991, Hilton Head, South Carolina, United States
Torben Hagerup, Constant-time parallel integer sorting, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.299-306, May 05-08, 1991, New Orleans, Louisiana, United States
Yossi Matias , Uzi Vishkin, Converting high probability into nearly-constant time—with applications to parallel hashing, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.307-316, May 05-08, 1991, New Orleans, Louisiana, United States
Joseph Gil , Yossi Matias, Fast hashing on a PRAM—designing by expectation, Proceedings of the second annual ACM-SIAM symposium on Discrete algorithms, p.271-280, January 28-30, 1991, San Francisco, California, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  E. Data
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)


General Terms:
Algorithms, Theory, Verification

Collaborative Colleagues:
J. Gil: colleagues
F. Meyer auf der Heide: colleagues
A. Wigderson: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player