0
$\begingroup$

My question is related to this question I posted in math forum:

https://math.stackexchange.com/questions/1512644/balls-and-bins-hash-table-a-concrete-example

but I could not get an answer that I need.


Please assume upper bound on set cardinality is $n$ (so the set has at most $n$ elements). A server wants to construct a hash table in away that each bucket would contain at most $d$ elements with a high probability. So for any client having set $S_i$ where $|S_i|<n$, any bucket of hash table would not overflow. In setting, any client can independently insert its elements in the hash table, given the hash table length and hash function; and send the hash table to the server.

I need to know how the server can compute the hash table length (or number of buckets in the hash table), given $n$ and $d$.

In [1,2] it is said $\frac{n}{k}+O(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$ is a max load for a bucket with a high probability, where $n$ denotes number of elements and $k$ denotes number of buckets (alternatively we can re-write it as $\frac{n}{k}+C(\sqrt[2]{(\frac{n}{k})\log k}+\log k)$, where $C$ is a constant value). But, I need to know how this works in practice. More specifically how we can compute the probability and constant value, $C$.


[1]. http://www.pinkas.net/PAPERS/FNP04.pdf

[2]. http://www14.in.tum.de/personen/raab/publ/balls.pdf

$\endgroup$

migrated from crypto.stackexchange.com Nov 5 '15 at 21:21

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • 4
    $\begingroup$ The answer is in the papers. Since you are the one who wants to know the answer, it makes more sense for you rather than us to read the papers. $\endgroup$ – Yuval Filmus Nov 5 '15 at 23:47
  • 1
    $\begingroup$ What have you tried? Have you tried simulating it to estimate the value of $C$ and the probability? That will probably give you a more accurate estimate than any asymptotic analysis, anyway. $\endgroup$ – D.W. Nov 6 '15 at 0:09
  • $\begingroup$ Don't we have a duplicate of this? Ah, your own question. Duplicate or only related? $\endgroup$ – Raphael Nov 6 '15 at 8:21
  • $\begingroup$ Why do you think you'd need this probability and $C$ "in practice"? $\endgroup$ – Raphael Nov 6 '15 at 8:23
  • $\begingroup$ @Raphael The scenario in the question explains why I need it I explain again, here: Please consider we have two clients and a server( e.g. cloud). The server picks the parameters (i.e. $k$ and $n$ and max-load $d$) for the hash table (HT) and publishes it. Now any client who wants to upload its set constructs the HT using the parameters, inserts its value and sends it to the server. If the server calculates the parameters in a way that with high probability there would be no overflow for every bucket, each client can insert is values into HT and send it to the server. $\endgroup$ – user153465 Nov 6 '15 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.