NOTE
Archive
Class
Friends
Home
Slides

BDA-DGIM

2024-11-15 1
手机查看

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
Table Of Contents
BDA-DGIM