commit 8117a472e3122e371b595ef68d6c89170a36070a
parent 4b67341d57bf93d247faf9ff173e19cf0a867962
Author: Elias Summermatter <elias.summermatter@seccom.ch>
Date: Mon, 21 Dec 2020 16:24:55 +0100
Added some more description in set diff
Diffstat:
1 file changed, 18 insertions(+), 8 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
@@ -160,7 +160,7 @@
</figure>
</section>
- <section anchor="ibv_operations" numbered="true" toc="default">
+ <section anchor="ibf_operations" numbered="true" toc="default">
<name>Operations</name>
<section anchor="ibv_operations_insert" numbered="true" toc="default">
<name>Insert Element</name>
@@ -208,7 +208,7 @@
]]></artwork>
</figure>
</section>
- <section anchor="ibv_operations_remove" numbered="true" toc="default">
+ <section anchor="ibf_operations_remove" numbered="true" toc="default">
<name>Remove Element</name>
<t>
To remove an element from the IBF the element is hashed with the same hash functions that it was
@@ -242,7 +242,7 @@
]]></artwork>
</figure>
</section>
- <section anchor="ibv_operations_decode" numbered="true" toc="default">
+ <section anchor="ibf_operations_decode" numbered="true" toc="default">
<name>Decode IBF</name>
<t>
To decode a IBF there are pure buckets needed, pure buckets are buckets where which contain only
@@ -300,13 +300,23 @@
</figure>
</section>
<section anchor="ibv_operations_setdiff" numbered="true" toc="default">
- <name>Set difference</name>
+ <name>Set Difference</name>
<t>
- To calculate the difference between two sets. The two IBFs can be compared by XORing both IBFs and
- subtracting counts on all buckets which results in a new IBF. This new IBF can then be decoded as described in the decoding section.
+ One of the most interesting capability of IBF's is the possibility to easily calculate the difference
+ between two IBF's.
+ To calculate the difference between two IBF's its only necessary to XOR the value of both IBF's bucket by bucket and
+ subtracting the counts which results in a new IBF with the same amount of buckets.
+ This new IBF can be decoded as described in section <xref target="ibf_operations_decode" format="counter" />.
The new IBF can have two types of pure buckets with counter set to 1 or -1. If the counter is set to 1
- the element is missing in the second set and if the counter is set to -1 the element is missing in
- the first set.
+ the element is missing in the secondary set and if the counter is set to -1 the element is missing in
+ the primary set.
+ </t>
+ <t>
+ Through this addition/subtraction its possible that a bucket seams pure but in reality isn't pure,
+ a falsely pure bucket. This case its easy to detect by checking if an element exist in either set, if
+ the element does not exist its a falsely pure bucket in this case continue test the
+ next pure bucket until one is found that is truly pure. If no truly pure buckets are found the IBF
+ fails to decode.
</t>
<t>
To demonstrate the set difference operation we compare IBF-A with IBF-B and generate as described
