# 2020q3 Homework3 (dict)
contributed by < ` JulianATA ` >

## Xor Filter 論文與實作
* 在看論文的同時，就順手實作了程式碼。
* 全部程式碼大約 300 行。
* 論文閱讀+實作時間大約 11 小時。
* 程式碼通過Valgrind/Cppcheck
* 程式碼: 目前更新在 dict 專案當中，改進後將建立獨立 repository
* [xor_filter.h](https://github.com/JulianATA/dict/blob/master/xor_filter.h)
* [xor_filter.c](https://github.com/JulianATA/dict/blob/master/xor_filter.c)
* 所實作的程式碼中，使用到以下基本資料結構。
* stack: 基於 [lab0-c](https://github.com/sysprog21/lab0-c) 的程式碼改寫而成。
* 以下解說將搭配程式碼實作時候遇到困難與思考。

### 什麼是 Xor Filter ？
不論是 Xor Filter 或是 Bloom Filter 都是在不走訪全部元素的情況下，預測元素是否存在一個集合內。 具體的流程如下：

digraph R{
node [shape=record]
Equivalent [shape=diamond]
Element->{FingerprintHash Hash0 Hash1 Hash2}
{Hash0 Hash1 Hash2}->FingerprintSet
FingerprintSet->{Fingerprint0 Fingerprint1 Fingerpirnt2}
{Fingerprint0 Fingerprint1 Fingerpirnt2}->Xor


{FingerprintHash Xor}->Equivalent
Equivalent->{True False}
}

* 輸入元素到 Xor Filter
* 會作 4 次 Hash
* Hash0/1/2
* FingerprintHash
* 將 Hash0/1/2 分別作為 Index 放入 FingerprintSet ( 在論文中以 B 表示 )
* 得到 Fingerpint0/1/2
* 將三者作 Xor
* 將得到的 Fingerprint 與 FingerprintHash 作比對
* 相等就預測元素於集合內

在使用上，Xor Filter 相當簡單。困難的點在於如何建立 Xor Filter 。

### 建立 Xor Filter
* 原文: [Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters](https://arxiv.org/abs/1912.08258)

論文中的 Algorithm2 就是在建立整個 Xor Filter 的過程， Algorithm3 則是建立中最重要的環節，測試 Hash Function 0/1/2。

首先看 Algorithm2

Algorithm 2 Construction
Require: set of keys S
Require: a fingerprint function
repeat
 pick three hash functions h 0 , h 1 , h 2 at random, independently from the fingerprint function
until map(S, h 0 , h 1 , h 2 ) returns success with a stack σ (see Algorithm 3)
B ← an array of size ⌊1.23 · |S |⌋ + 32 containing k-bit values (uninitialized)
assign(σ , B, h 0 , h 1 , h 2 ) (see Algorithm 4)
return the array B and the hash functions h 0 , h 1 , h 2

流程如下：
* 重複抽取三個 Hash function， 直到 Alogrithm3 測試成功
* 配置 Fingerprint Set B 空間
* 將 Stack 中的 Fingerprint 配置至 Fingerprint Set B 中。
* 即可獲得上述的 Xor Filter 流程中的 Fingerprint Set 與 Hash function 0/1/2
* 建立成功

> 實際上 Hash Funciton 0/1/2 取得的值比較類似 Index ， 後面會解釋。
> 根據論文中的描述 Hash Function 0/1/2 需要具備以下性質：
>> Hash functions from U to integers in
>> $[0, \lfloor \frac{c}{3} \rfloor), [\lfloor \frac{c}{3}\rfloor, \lfloor \frac{2c}{3}\rfloor),[\lfloor \frac{2c}{3} \rfloor, c)$ respectively.
>
> [name=Julian Fang]

接下來，看一下 Algorithm3

Algorithm 3 Mapping Step (map)
Require: set of keys S, k-bit integer-valued hash functions h 0 , h 1 , h 2 .
let c ← ⌊1.23 · |S |⌋ + 32
H ← an array of size c containing a set of keys (values from S), initially empty
for all x in S do
append x to H [h 0 (x)]
append x to H [h 1 (x)]
append x to H [h 2 (x)]
end for
Q ← initially empty queue
for i = 0 to |H | do
if the set H [i] contains a single key then add i to Q endif
end for
σ ← initially empty stack
while queue Q is not empty do
remove an element i from the queue Q
if the set H [i] contains a single key then
let x be the sole value in the set H [i]
push the pair (x, i) on the stack σ
for j = 0 to 2 do
remove x from the set H [h j (x)]
if the set H [h j (x)] contains a single key then add h j (x) to Q endif
end for
end if
end while
return success and the stack σ if |σ | = |S |, else return failure

* 首先定義以下變數
* $S$ ( Set ): 所有元素的集合。
* $|S|$ : 集合中元素的數量。
* $c$ ( Capacity ): 整個 FingerprintSet B 的 大小，論文中為 $\lfloor{1.23\times|S|}\rfloor+32$。
* 實作上，我取最接近論文中的 3 的倍數作為 $c$ 。
* $H$ :一個暫時的 Fingerprint Set。
* $Q$ :紀錄 Element 與 index 用的。
* 我在實作上，沒有使用到 $Q$
* $\sigma$ :紀錄 Element 與 index 用的。
* 首先，所有elements 透過 Hash function 0/1/2 得到 index 0/1/2
* 並透過 index 存入 $H$ 中對應的 Set。
* 將所有 $H$ 中的 Set 掃過，當 Set 中 element 數量為 1 的時候， 存入 $Q$ 。
* 當$Q$ 中仍有元素的時候，作以下迴圈：
* 移除一個 $Q$ 中的元素。
* 將此元素與其 index，放入 stack $\sigma$
* 移除所有 $H$ 中的元素
* 當 Set 中 element 數量為 1 的時候， 存入 $Q$ 。
* 結束迴圈。
* 如果 Stack 中的元素數量等於 $|S|$
* 成立，則透過 Hash Function 0/1/2 建立 Filter
* 不成立，重新抽取 Hash Function 0/1/2

這個部份在做什麼呢？ 在於確立找到 Hash Function 0/1/2 具有以下特性
* 所有於 Set $S$ 中的元素 $e_0$
* 透過 Hash Function 0/1/2 得到 index $i_{00}$, $i_{01}$, $i_{02}$
* 所有於 Set $S$ 中的元素 $e_1$
* 透過 Hash Function 0/1/2 得到 index $i_{10}$, $i_{11}$, $i_{12}$
* 只要於 Set 內，$e_0\neq e_1$則保證
* {$i_{00}$, $i_{01}$, $i_{02}$} $\neq${$i_{10}$, $i_{11}$, $i_{12}$}
* 可能部份相同，但不會出現完全一樣的情況。

## Xor Filter/Bloom Filter 效能比較

###### tags: `Cprogramming`