[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[lsd0003] branch master updated: Added some more description in set diff
From: |
gnunet |
Subject: |
[lsd0003] branch master updated: Added some more description in set diff |
Date: |
Mon, 21 Dec 2020 16:25:24 +0100 |
This is an automated email from the git hooks/post-receive script.
elias-summermatter pushed a commit to branch master
in repository lsd0003.
The following commit(s) were added to refs/heads/master by this push:
new 8117a47 Added some more description in set diff
8117a47 is described below
commit 8117a472e3122e371b595ef68d6c89170a36070a
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Mon Dec 21 16:24:55 2020 +0100
Added some more description in set diff
---
draft-summermatter-set-union.xml | 26 ++++++++++++++++++--------
1 file changed, 18 insertions(+), 8 deletions(-)
diff --git a/draft-summermatter-set-union.xml b/draft-summermatter-set-union.xml
index 1d96fa3..4ff8855 100644
--- 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
--
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [lsd0003] branch master updated: Added some more description in set diff,
gnunet <=