利用 XOR 處理 time series data 壓縮資料

在「The simple beauty of XOR floating point compression (clemenswinter.com)」這邊看到的內容,原文在「The Simple Beauty of XOR Floating Point Compression」這邊。這也是上一篇文章「Golomb coding」的延續。

文章作者在處理 time series data 時預先用 XOR 處理過 (對上一筆資料做),因為 time series data 的特性,通常 XOR 出來的結果會有很多都是 0 (表示相同的 bit),然後再用自己設計的演算法讓 raw data 變小。

以作者拿的第一個範例可以看到變小很多 (開原圖可以看比較清楚),不過這邊 low bit 都是 0 有點作弊:

後面有 unix timestamp 的部分,這個部分的資料就比較接近實際情況,也可以看出來效果不錯:

這邊似乎也可以選擇套 Golomb coding 或是 Rice coding (i.e. M 是 2 的冪次的特殊情況,2^n,這時候 Truncated binary encoding 剛好就是 Binary encoding)。

算是個有趣的處理法... 不過我猜大多數人為了方便處理,還是只會用 framework 提供的壓縮演算法,在底層透明地處理掉,像是 LZ4gzip 或是 zstd

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一,在實際應用上有更好的選擇,像是先前提到的 Cuckoo filter:「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構,號稱又比 Bloom filter 與 Cuckoo filter 好:「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越,其中馬上可以看到的差異就是不支援 delete:

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載:「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。