0
$\begingroup$

So I am looking for an explanation of an experiment. In this experiment, I took a set of k hash functions. Say the total number of data points I am working on is d. Call an algorithm A which used that set of hash functions to do some operations on d data points and have modified them to a matrix B.It is mentionable that algorithm A introduces a bunch of randomization. So applying algorithm A different times with same set of hash functions and same set of data points will produce different results. Now we apply algorithm C on that matrix B and get a result, call it D. So this is the summary of what I am trying to do in short. Now I can do this multiple times in two ways-

  1. I take a set of k hash functions in the beginning. Now I run algorithm A with the same set of hash functions and on the same set of data points n times and produced n different matrixes and averaged the respective elements of those matrixes to produce a final matrix, call B'. So in short, the (i,j)th entry of the matrix B' is the average of (i,j)th entry of n matrixes we got before. Now , we run algorithm C on matrix B' and get a result D
  2. I take a set of k hash functions, run algorithm A, generate matrix B and then run algorithm C on matrix B to produce result D. Now, I run this process multiple times, every time with a different set of hash functions and then average all such Ds and produce D' Interestingly, process 2 gives just radically more accurate results and I don't know how to explain this behavior. One thing to mention, I was using sha256 in this experiment. I hope to get help from kind people out here in order to solve this. Thanks in advance! Edit: This has been used for some differential privacy operations and the results accuracy is being measured by comparing with the ground truth
    Edit2: By indicating that I used k different sha256 hash functions, I meant that I just generated k seeds and appended them before the string I am tryna hash, for example,
hex_num = hashlib.sha256((str(seed[i])+str(d)).encode('utf-8')).hexdigest()

Hope it is clear now

Improve this question
$\endgroup$
4
  • $\begingroup$ Can you explain what you're using the hash functions for and what do you mean by "more accurate"? In general, it doesn't make sense to do computations on hash values and talk about the accuracy of the result. $\endgroup$ – Aman Grewal Aug 12 '20 at 16:46
  • $\begingroup$ @AmanGrewal I edited the statement a bit $\endgroup$ – Anastasia Tillibiu Aug 12 '20 at 17:08
  • $\begingroup$ It's not clear what property of hash functions you are using (could you try to clarify this?). Moreover, do you need a cryptographic hash function for your construction, or a universal hash function family? You mention SHA256 (which is a cryptographic hash function), but choosing hash functions randomly from some family is a hallmark of universal hash function families. $\endgroup$ – Mark Aug 12 '20 at 18:36
  • $\begingroup$ @Mark, I added more clarification above :) $\endgroup$ – Anastasia Tillibiu Aug 12 '20 at 19:13
0
$\begingroup$

A possibility is that algorithm A is randomized, but at least one of the following holds

  • the source of randomness used is poor (e.g. tends to repeat), and using several sets of hash functions fixes that, merely by introducing more of the randomness necessary for accurate results (whatever that means) of the overall procedure.
  • there is no randomness fed into the input of at least one of the hash functions in a set, therefore changing that hash function adds some of the beneficial randomness.
Improve this answer
$\endgroup$

Your Answer

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

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