前提:

這一篇主要是看FOSDEM 2016 影片的簡單心得(投影片在這裡),順便把之前學的 Bloom Filter 複習一下. 這裡有我之前寫的程式

心得

這篇文章主要都介紹透過 Golang 來開發一個 Data Application . 從 Bloom Filter 到 Count-Min (透過 Hash 方式來存放資料,主要是記錄有出現多少次),到了 HyperLogLog (

關於 Bloom Filter

這是什麼?

Bloom Filter 是一個資料結構.主要是拿來能夠快速的確認一個數值有沒有存在的資料結構.具有以下特性:

  • 極小使用空間(由於不存在原本的 Value ) 只需要儲存 k 個資料結構就好.
  • 具有 可以判斷該數值絕對不存在 效率 ( 也就是不具有 False Nagative ,但是具有 False Postive ). 搜尋時間複雜度: \(O(n)\)

 使用場景:

  • 爬蟲可以記錄該網址是否有爬過
  • Google 惡意 URL 判斷
  • Canssandra 判斷該 Partition 是否有存放該數值

參考鏈結


Buy Me A Coffee

Evan

Attitude is everything