0
$\begingroup$

Given a sequence $x \in \{ 1,2,3...,\vert \Sigma \vert \}^*$ one wants to create a sketch of it say $s(x)$ of size $\frac{2c}{3}k (ln^2 k)$ bits. And that seems to be achieved as follows,

  • pick at random 2k-wise independent hash functions,

$h : [n \vert \Sigma\vert] \rightarrow [(k/3)ln (k)$

$h^0 : [n \vert \Sigma\vert] \times [2ln(k)] \rightarrow [c ln^2 (k)]$

(where apparently $c = 72e$ helps!)

For each new element $\sigma_i \in x$ the following update is done to the sketch

  • Let $bucket = h((i-1)\vert \Sigma\vert + \sigma_i )$

  • For $t \in \{1,2,3..,2ln(k)\}$

    • $sub-bucket = h^0((i-1)\vert \Sigma\vert + \sigma_i,t )$

    • $d = (bucket-1)2cln^3k + (t-1)cln^2(k) + sub-bucket$

    • $s(x)_d = s(x)_d \oplus 1 $

Can someone kindly explain as to what exactly happened here? I am not seeing the intuition at all..

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ 1. Please give us some context. Help us help you. Where did you see this construction? What types of operations is the sketch supposed to perform? Is this a standard sketch and if so what is its name (or the names of the authors, or where it was published)? 2. Please give us a more specific question. "What happened here?" is vague -- I can't tell what you are looking for. Specifically what problem are you trying to solve? What exactly are you confused about? (If you say "all of it", then this question isn't a good fit for this site.) 3. What have you tried? Where did you get stuck? $\endgroup$ – D.W.♦ May 28 '15 at 5:53
  • 1
    $\begingroup$ What you describe looks like a variant of the CountSketch streaming algorithm by Charikar, Chen, and Farach-Colton. I'm not sure what you are trying to achieve, but you should be able to get all the main ideas from that (great!) paper. $\endgroup$ – Ran G. May 29 '15 at 0:45
  • 1
    $\begingroup$ The thing that you might be looking for is that if we treat a hash as a black box, it looks like deterministic randomness — deterministic in that it always gives the same output for the same input, but random in that all the bits of the hash are affected by the input in unpredictable ways. We can treat n different hashes of an unknown input as n independent random variables, and get probabilistic results about the algorithm's performance. $\endgroup$ – hobbs May 29 '15 at 5:49
  • $\begingroup$ Can someone help understand what is the "bucket" doing? What is this $s(x)_d$ thing? Why these peculiar numbers $(k/3)ln(k)$, $2ln(k)$ and $cln^2(k)$ ? $\endgroup$ – user6818 May 29 '15 at 6:49
  • $\begingroup$ @user6818 no idea. It's an awful example. Where does it come from? $\endgroup$ – hobbs May 29 '15 at 17:17

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.