A dictionary implementation based on dynamic perfect hashing. - In: Journal of experimental algorithmics, ISSN 1084-6654, Bd. 12.2008, 1.11, insges. 25 S.
We describe experimental results on an implementation of a dynamic dictionary. The basis of our implementation is dynamic perfect hashingъ as described by Dietzfelbinger et al. (SIAM J. Computing 23, 1994, pp. 738--761), an extension of the storage scheme proposed by Fredman et al. (J. ACM 31, 1984, pp. 538--544). At the top level, a hash function is used to partition the keys to be stored into several sets. On the second level, there is a perfect hash function for each of these sets. This technique guarantees O(1) worst-case time for lookup and expected O(1) amortized time for insertion and deletion, while only linear space is required. We study the practical performance of dynamic perfect hashing and describe improvements of the basic scheme. The focus is on the choice of the hash function (both for integer and string keys), on the efficiency of rehashing, on the handling of small buckets, and on the space requirements of the implementation.
http://doi.acm.org/10.1145/1370596.1370602
Taschenbuch der Algorithmen. - Berlin, Heidelberg : Springer-Verlag, 2008. - Online-Ressource (X, 448 S.). - (eXamen.press) ISBN 978-3-540-76394-9
Heriber
http://dx.doi.org/10.1007/978-3-540-76394-9
Tight bounds for blind search on the integers. - Dortmund : TU, Secretary of the SFB 531, 2008. - 13 Bl.. - (Reihe Computational Intelligence ; 240)
Probabilistic methods in the design and analysis of algorithms : 07391 abstracts collection ; Dagstuhl seminar. - [Wadern] : [Internat. Begegnungs- und Forschungszentrum für Informatik], 2007. - Online-Ressource (PDF-Datei: 18 S., 240 KB). - (Dagstuhl seminar proceedings ; 07391)
http://d-nb.info/991699130/34
Design strategies for minimal perfect hash functions. - In: Stochastic algorithms: foundations and applications, (2007), S. 2-17
http://dx.doi.org/10.1007/978-3-540-74871-7
A characterization of average case communication complexity. - In: Information processing letters, ISSN 1872-6119, Bd. 101 (2007), 6, S. 245-249
It is well known that the average case deterministic communication complexity is bounded below by an entropic quantity, which one would now call deterministic information complexity. In this paper we show a corresponding upper bound. We also improve known lower bounds for the public coin Las Vegas communication complexity by a constant factor.
http://dx.doi.org/10.1016/j.ipl.2006.10.006
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Theoretical computer science, Bd. 380 (2007), 1/2, S. 47-68
We study a particular aspect of the balanced allocation paradigm (also known as the "two-choices paradigm"): constant sized bins, packed as tightly as possible. Let d >= 1 be fixed, and assume there are m bins of capacity d each. To each of n <= d*m$ balls two possible bins are assigned at random. How close can dm/n = 1 + epsilon be to 1 so that with high probability each ball can be put into one of the two bins assigned to it, without any bin overflowing? We show that epsilon > (2/e)^(d-1) is sufficient. If a new ball arrives with two new randomly assigned bins, we wish to rearrange some of the balls already present in order to accommodate the new ball. We show that on average it takes constant time to rearrange the balls to achieve this, for epsilon > beta^d, for some constant beta < 1. An alternative way to describe the problem is in data structure language. Generalizing cuckoo hashing (Pagh and Rodler, 2004), we consider a hash table with m positions, each representing a bucket of capacity d >= 1. Keys are assigned to buckets by two fully random hash functions. How many keys can be placed in these bins, if key x may go to bin h_1(x) or to bin h_2(x)? We obtain an implementation of a dictionary that accommodates n keys in m = (1+epsilon)n/d buckets of size d = O(log(1/epsilon)), so that key x resides in bucket h_1(x) or h_2(x). For a lookup operation, only two hash functions have to be evaluated and two segments of d contiguous memory cells have to be inspected. If d >= 1 + 3.26 * ln(1/epsilon), a static arrangement exists with high probability. If d >= 16 * \ln(1/epsilon), a dynamic version of the dictionary exists so that the expected time for inserting a new key is log(1/epsilon)^(O(log log(1/epsilon))).
http://dx.doi.org/10.1016/j.tcs.2007.02.054
On the probability of rendezvous in graphs. - In: Random structures & algorithms, ISSN 1098-2418, Bd. 26 (2005), 3, S. 266-288
In a simple graph G without isolated nodes the following random experiment is carried out: each node chooses one of its neighbors uniformly at random. We say a rendezvous occurs if there are adjacent nodes u and v such that u chooses v and v chooses u; the probability that this happens is denoted by s(G). Métivier, Saheb, and Zemmari [Randomized rendezvous, Algorithms, trees, combinatorics, and probabilities, Eds. G. Gardy and A. Mokkadem, Trends in Mathematics, 183-194. Birkhäuser, Boston, 2000.] asked whether it is true that s(G) s(Kn) for all n-node graphs G, where Kn is the complete graph on n nodes. We show that this is the case. Moreover, we show that evaluating s(G) for a given graph G is a #P-complete problem, even if only d-regular graphs are considered, for any d 5.
https://doi.org/10.1002/rsa.20032
Balanced allocation and dictionaries with tightly packed constant size bins. - In: Automata, languages and programming, (2005), S. 166-178
http://dx.doi.org/10.1007/11523468_14