Yes, that's called rejection sampling, and it's the only way to produce truly uniform output if the range doesn't evenly divide the input range. However in a setting of say finding buckets in a hashtable which isn't a…
The conversion is free, at least on x86-like platforms, because there are no separate 32-bit and 64-bit registers. Instead, there is a fixed shared set of registers, and the instructions signal whether they operate on…
No, it's not. The method described by ARM is functionally identical, so it is equally biased as the method described in the blog post here.
Exactly, both the modulo and the multiplicative method are equally close to uniform. In fact, under the constraint of starting from a uniform input with 2^n possibilities, both produce an output that is as close to…
I recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties. A write-up is here,…
I think the most mind-blowing aspect about it is that (PinSketch) sketches are identical in size to the bandwidth that would be required to just send the difference if you did know it ahead of time. Perhaps this…
Yeah, IBLT has a size overhead which mostly matters for small differences/capacities. It's also probabilistic, so the higher your probability for recovery has to be, the larger it gets. Assuming you don't actually know…
It depends on the protocol requirements. If you have 256-bit data elements to reconcile, and want 100% guarantee that reconciliation will succeed with 1 round-trip, then you'll indeed need to use sketches with 256-bit…
Hi, other author here. 0. Indeed. Though if your set consists of 100 million elements, you'll indirectly need to have at least 27 bit elements just to be able to identify them. So for practical problems you can probably…
Yes, that's called rejection sampling, and it's the only way to produce truly uniform output if the range doesn't evenly divide the input range. However in a setting of say finding buckets in a hashtable which isn't a…
The conversion is free, at least on x86-like platforms, because there are no separate 32-bit and 64-bit registers. Instead, there is a fixed shared set of registers, and the instructions signal whether they operate on…
No, it's not. The method described by ARM is functionally identical, so it is equally biased as the method described in the blog post here.
Exactly, both the modulo and the multiplicative method are equally close to uniform. In fact, under the constraint of starting from a uniform input with 2^n possibilities, both produce an output that is as close to…
I recently discovered a generalization of this approach, which allows mapping a single hash to multiple independent numbers, each in their own range, while maintaining various uniformity properties. A write-up is here,…
I think the most mind-blowing aspect about it is that (PinSketch) sketches are identical in size to the bandwidth that would be required to just send the difference if you did know it ahead of time. Perhaps this…
Yeah, IBLT has a size overhead which mostly matters for small differences/capacities. It's also probabilistic, so the higher your probability for recovery has to be, the larger it gets. Assuming you don't actually know…
It depends on the protocol requirements. If you have 256-bit data elements to reconcile, and want 100% guarantee that reconciliation will succeed with 1 round-trip, then you'll indeed need to use sketches with 256-bit…
Hi, other author here. 0. Indeed. Though if your set consists of 100 million elements, you'll indirectly need to have at least 27 bit elements just to be able to identify them. So for practical problems you can probably…