Simple fast parallel hashing. (English) Zbl 1418.68236
Abiteboul, Serge (ed.) et al., Automata, languages and programming. 21st international colloquium, ICALP ’94, Jerusalem, Israel, July 11–14, 1994. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 820, 239-250 (1994).
Summary: A hash table is a representation of a set in a linear size data structure that supports constant-time membership queries. We show how to construct a hash table for any given set of \(n\) keys in \(O(\mathrm{lg}\,\mathrm{lg}\,n)\) parallel time with high probability, using \(n\) processors on a weak version of a crcw pram.
The algorithm is simple and is sketched by the following:
For the entire collection see [Zbl 0844.00024].
The algorithm is simple and is sketched by the following:
- 1.
- Partition the input set into buckets by a random polynomial of constant degree.
- 2.
- For \(t:=1\,\,\text{to}\,\,O(\mathrm{lg}\,\mathrm{lg}\,n)\) do
- (a)
- Allocate \(M_t\) memory blocks, each of size \(B_t\), where \(M_t\) and \(B_t\) are carefully a priori selected parameters.
- (b)
- Let each bucket select a block at random, and try to injectively map its keys into the block using a random linear function. Buckets that fail carry on to the next iteration.
For the entire collection see [Zbl 0844.00024].
References:
| [1] | H. Bast and T. Hagerup. Fast and reliable parallel hashing. In 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pages 50-61, July 1991. |
| [2] | L. J. Carter and M. N. Wegman. Universal classes of hash functions. J. Comput. Syst. Sci., 18:143-154, 1979. · Zbl 0412.68090 |
| [3] | B. Chor and O. Goldreich. On the power of two-point based sampling. Journal of Complexity, 5:96-106, 1989. · Zbl 0672.60105 |
| [4] | M. Dietzfelbinger, J. Gil, Y. Matias, and N. Pippenger. Polynomial hash functions are reliable. In Proc. of 19th International Colloquium on Automata Languages and Programming, Springer LNCS 623, pages 235-246, July 1992. · Zbl 1425.68098 |
| [5] | M. Dietzfelbinger, A. R. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert, and R. E. Tarjan. Dynamic perfect hashing: Upper and lower bounds. In Proc. of the 29th IEEE Annual Symp. on Foundation of Computer Science, pages 524-531, 1988. To appear in SIAM J. Comput. · Zbl 0820.68038 |
| [6] | M. Dietzfelbinger and F. Meyer auf der Heide. An optimal parallel dictionary. In 1st Annual ACM Symposium on Parallel Algorithms and Architectures, pages 360-368, 1989. · Zbl 0786.68023 |
| [7] | M. Dietzfelbinger and F. Meyer auf der Heide. A new universal class of hash functions and dynamic hashing in real time. In Proc. of 17th International Colloquium on Automata Languages and Programming, Springer LNCS 443, pages 6-19, 1990. · Zbl 0765.68026 |
| [8] | F. E. Fich, P. L. Ragde, and A. Wigderson. Relations between concurrent-write models of parallel computation. SIAM J. Comput., 17:606-627, June 1988. · Zbl 0652.68065 |
| [9] | M. L. Fredman, J. Komlós, and E. Szemerédi. Storing a sparse table with O(1) worst case access time. J. ACM, 31(3):538-544, July 1984. · Zbl 0629.68068 |
| [10] | P. B. Gibbons, Y. Matias, and V. L. Ramachandran. Efficient low-contention parallel algorithms. In 6th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1994. · Zbl 0870.68083 |
| [11] | J. Gil and Y. Matias. Fast hashing on a PRAM—designing by expectation. In Proc. of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 271-280, Jan. 1991. · Zbl 0800.68457 |
| [12] | J. Gil and Y. Matias. Leaders election without a conflict resolution rule—fast and efficient randomized simulations among CRCW PRAMs. In Proc. of the 1st Latin American Informatics Symposium, Springer LNCS 583, pages 204-218, 1992. To appear in J. of Parallel and Distributed Computing. |
| [13] | J. Gil, Y. Matias, and U. Vishkin. Towards a theory of nearly constant time parallel algorithms. In Proc. of the 32nd IEEE Annual Symp. on Foundation of Computer Science, pages 698-710, Oct. 1991. |
| [14] | J. Gil, F. Meyer auf der Heide, and A. Wigderson. Not all keys can be hashed in constant time. In Proc. of the 22nd Ann. ACM Symp. on Theory of Computing, pages 244-253, 1990. |
| [15] | R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. A Foundation for Computer Science. Addison-Wesley Publishing Company, Inc., Reading, Massachusetts, May 1989. · Zbl 0668.00003 |
| [16] | J. JáJá. Introduction to Parallel Algorithms. Addison-Wesley Publishing Company, Inc., 1992. · Zbl 0781.68009 |
| [17] | Y. Matias and U. Vishkin. On parallel hashing and integer sorting. In Proc. of 17th International Colloquium on Automata Languages and Programming, Springer LNCS 443, pages 729-743, 1990. · Zbl 0765.68040 |
| [18] | Y. Matias and U. Vishkin. Converting high probability into nearly-constant time—with applications to parallel hashing. In Proc. of the 23rd Ann. ACM Symp. on Theory of Computing, pages 307-316, May 1991. |
| [19] | Y. Matias and U. Vishkin. On parallel hashing and integer sorting. Journal of Algorithms, 12(4):573-606, 1991. · Zbl 0767.68051 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
