2
$\begingroup$

I've been reading about sketches for processing streaming data (the CountMin sketch, the Count sketch, the tug-of-war sketch, FM sketches, etc.). They use hash functions that are required to be 2-independent or 4-independent or $k$-independent for some small $k$.

However from cryptography we have fast hash functions that are very good candidates to essentially perfect: $k$-independent for every value of $k$ you could ever wish for, and so on. We can essentially treat them as uniformly chosen from the set of all functions: as far as we know, no polynomial-time computation can tell that this is not the case. I suspect many practitioners might be happy to use these cryptographic hash functions, if it led to improved performance or better parameters for the sketches.

Does it change anything about the design and analysis of sketches, if we assume we have perfect hash functions like this? Can we get asymptotically better parameters if we assumed our hash function was perfect? Or, can we get simpler sketch constructions?

(For instance, I've noticed that the analysis of existing sketches is often somewhat conservative: e.g., it uses the Markov bound or Chebyshev bound. If we had a perfect hash function we could use a Chernoff-style bound. Are there any sketches where this makes a significant difference, or is it just a small constant factor in the bound?)

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

The obvious problem is that if you use a cryptographic pseudorandom number generator (PRNG), the correctness of your algorithm is conditional on a complexity conjecture. However, usually this can be avoided, because the full strength of cryptographic pseudorandmness is usually a huge overkill for streaming. If your streaming algorithm uses a small amount of space, then what you need from your PRNG is that its output cannot be distinguished from a stream of random bits by a small space algorithm. Such a PRNG was constructed by Nisan, and the proof of pseudorandomness is unconditional.

A seminal paper in streaming algorithms that used Nisan's generator is Indyk's work on sketches of $L_1$. Since the sketch uses Cauchy random variables for which the mean and the variance do not exist, the usual moment calculations do not work, so it is hard to imagine how to use $k$-wise independence. That's why the heavy hammer of Nisan's generator comes handy.

A problem with these heavy hammers is that they come at a cost in space. The seed needs to be stored in memory, and for Nisan's generator the seed length is roughly $S\log R$ where $R$ is the number of random bits and $S$ is the space complexity of the algorithm. So you end up multiplying the space complexity by roughly the logarithm of the stream length $n$. If you can use $k$-wise independence you usually add a term like $O(k\log n)$ to the space complexity.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks! However, I really don't care about avoiding complexity conjectures. Truly, I don't. Therefore, Nisan's PRNG is solving a problem I don't have. I'd prefer to take the practitioner's perspective, not a complexity theorist's: assume we are willing to accept strong assumptions (e.g., SHA3 can be modeled as a random oracle). Then what performance is achievable with sketches? Is it better than with Nisan's generator? e.g., crypto hashes won't incur any cost in space, so won't they be preferable to using Nisan's PRNG or to $k$-wise independent hashes, from a practical perspective? $\endgroup$
    – D.W.
    Dec 3, 2014 at 22:14
  • $\begingroup$ Just to make sure, SHA3 being like a random oracle is afaik not known even if you assume standard complexity conjectures. But ok, let's say you have a random oracle. Then algorithms based on stable distributions (sketches for hamming norm, $L_1$, $L_2$) and Flajolet-Martin random counting become somewhat simpler and easier to analyze. For example $L_2$ is just JL-lemma. I think for all these problems there are optimal or very close to optimal space algorithms that do not assume magic boxes, but they can be more complicated. $\endgroup$
    – Sasho Nikolov
    Dec 3, 2014 at 23:00
  • $\begingroup$ Sasho, yes, that's exactly what I had in mind. So does anything change? Does it change the decision of which sketch to use? Does it make a significant difference to the space needed or running time? Sounds like you're saying it doesn't change the best achievable performance, it just means you can achieve that best achievable performance using simpler constructions -- is that right? If so, cool, that's exactly the sort of thing I was asking about! (Yeah, I know random oracle assumptions don't follow from any complexity conjecture.) Thank you! $\endgroup$
    – D.W.
    Dec 3, 2014 at 23:32
1
$\begingroup$

Another reason for not using cryptographic algorithms in practice is speed. In the streaming setting, we typically do not want to spend too long processing each item in the stream. Computing k cryptographic hash functions will be much more expensive than computing k fast non-cryptographic hash functions, e.g. MurmurHash.

In practice, I think most people use Kirsch and Mitzenmacher's result (http://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf) to reduce the number of hashes, but I would imagine that computing two SHA3 hashes would still take significantly longer than computing two Murmur hashes.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.