1
$\begingroup$

Suppose $𝐿_1,…,𝐿_𝑘$ are lists with $n$ elements each. We use a fully independent hash function ℎ to compute a value for each element of each list. (We suppose the hash function returns a value uniformly at random from $[𝑛^2]$. Note also that two elements $x$, and $y$ where $x = y$ has $ℎ(𝑥)=ℎ(𝑦)$.) Let $𝑀_1,…,𝑀_𝑘$ be sublists with the smallest $𝑋$ elements by computed hash value in each list. Let $𝐶_1$ contain $L_1$. Define more $𝐶$s by: if $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, let $𝐶_{𝑖+1}=𝐶_𝑖\cup𝐿_𝑖$; and otherwise let $𝐶_{𝑖+1}=𝐶_𝑖$. What size of $𝑋$ will ensure with probability at least $1−1/𝑛^2$ that: If $|𝐶_𝑖\cap 𝑀_𝑖|<𝑋/𝑟$, then $|𝐶_𝑖\cap𝐿_𝑖|<1.1𝑛/𝑟$; and otherwise, $|𝐶_𝑖\cap𝐿_𝑖|>0.9𝑛/𝑟$? I am looking to minimize the size of $X$.

Edit: Above simplified problem suggested by Matt F. in the comments below.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ So $X$ can depend on $n$, $r$, $c$ and $\epsilon$? That's a lot of variables. It would be easier to understand with a more concrete version of the problem where two of them are fixed, if you can find parameters that still give an interesting version of the problem. $\endgroup$
    – user44143
    Commented Oct 26, 2020 at 15:33
  • $\begingroup$ Thanks, I edited the problem statement such that $c$ is gone and $\epsilon$ is some error bound that you can determine (instead of a parameter that is an input to the problem). $\endgroup$
    – user1246462
    Commented Oct 26, 2020 at 20:49
  • $\begingroup$ Does this shorter version miss anything essential, and if so why is the missing bit essential? Suppose $L_1, \dots, L_k$ are lists with $n$ elements each, and $M_1, \dots, M_k$ are sublists with the smallest $X$ elements in each list. Let $C_1$ contain some elements from the lists. Define more $C$'s by: if $|C_i \cap M_i| < X/r$, let $C_{i+1} = C_i \cup L_i$; and otherwise let $C_{i+1} = C_i$. What size of $X$ will ensure with probability at least $1 - 1/n^2$ that: If $|C_i \cap M_i| < X/r$, then $|C_i \cap L_i| < 1.1 n/r$; and otherwise, $|C_i \cap L_i| > 0.9 n/r$? $\endgroup$
    – user44143
    Commented Oct 26, 2020 at 22:05
  • $\begingroup$ @MattF. No this doesn't miss anything. I would just add that we want to minimize the value of $X$. Feel free to update the question with this formulation. Otherwise I will update it tomorrow. $\endgroup$
    – user1246462
    Commented Oct 27, 2020 at 2:07
  • $\begingroup$ What are the random laws in your problem? $L_1,\cdots,L_k,M_1,\cdots,M_k,C_i$ are random ? $\endgroup$
    – RaphaelB4
    Commented Nov 2, 2020 at 12:32

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .