BDA-DGIM

Please describe the mechanism of DGIM. How the error bound is estimated? Is there a way to further reduce this error bound. Submit your response online within the allow time frame.

Mechanism

When a new bit comes in, drop the last (oldest) bucket if its end-time is prior to N time units before the current time.

2 cases: Current bit is 0 or 1 If the current bit is 0:

• no other changes are needed

If the current bit is 1:

• Create a new bucket of size 1, for just this bit.
  • End timestamp = current time
• If there are now three buckets of size 1, combine the oldest two into a bucket of size 2
• If there are now three buckets of size 2, combine the oldest two into a bucket of size 4
• And so on …

Solution

To reduce the error bound in the DGIM algorithm, consider this:

Instead of maintaining 1 or 2 of each size bucket, we allow either r-1 or r buckets (r > 2)

• Except for the largest size buckets; we can have any number between 1 and r of those