1

I am using Parallel Algorithm (http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance#Parallel_algorithm) to merge standard deviation of two groups

Can we merge two groups if there are duplicate entries in them

example I have two groups group1 and group2 having userName and usage

group1
user1 10
user2 12
user3 15

group2
user2 14
user3 13
user4 16

merged
user1 10
user2 26
user3 28
user4 16

stdev - 7.3485

i want to find st dev of merged group, but problem is because of high data volume I can't maintain userName , so i am maintaining sum and user count, and by probablistic counting algorithm I can find unique users also

group1
count-3, sum-37, M2-9.935

group2
count-3, sum-43, M2-7.919

merged group
unique- 4
group1:: count-3, sum-37, M2-9.935
group2:: count-3, sum-43, M2-7.919

now with this information available, can i find standard deviation of merged group??

banjara
  • 23

1 Answers1

1

You can't calculate what you need from the counts and variances of the two groups. Consider the following example.

On day $1$ your data is this: $$\begin{array}{rl|rl} \text{Group }1 & & \text{Group } 2 & \\ \text{User }1 & 1 & \text{User }1& 9 \\ \text{User }2 & 10 & \text{User }3& 10 \\ \text{User }4 & 9 & \text{User }4& 1 \\ \end{array}$$

So both groups have mean $\frac{20}3$ and standard deviation $\sqrt{\frac{1238}9}$.

On day $2$ the numbers are the same but the users are different $$\begin{array}{rl|rl} \text{Group }1 & & \text{Group } 2 & \\ \text{User }1 & 10 & \text{User }1& 10 \\ \text{User }2 & 1 & \text{User }3& 1 \\ \text{User }4 & 9 & \text{User }4& 9 \\ \end{array}$$

So the means and standard deviations haven't changed for the individual groups. The list of unique users is the same for both days too. But look what happens when I combine the groups. $$\begin{array}{rl|rl} \text{Day }1 & & \text{Day } 2 & \\ \text{User }1 & 10 & \text{User }1& 20 \\ \text{User }2 & 10 & \text{User }2& 1 \\ \text{User }3 & 10 & \text{User }3& 1 \\ \text{User }4 & 10 & \text{User }4& 18 \\ \end{array}$$

The groups have the same mean, but the standard deviations are wildly different.

I don't know what you can do from here. The numbers you've got aren't enough to tell you the standard deviation. Your algorithm has to be able to distinguish between the two examples above, so you need to keep track of the user name.

I think you're going to have to merge the two data sets.

Tim
  • 5,564