🚀 免費嘗試 Zilliz Cloud,完全托管的 Milvus,體驗速度提升 10 倍!立即嘗試

milvus-logo
LFAI
  • Home
  • Blog
  • Bitset 如何實現向量相似性搜尋的多樣性

Bitset 如何實現向量相似性搜尋的多樣性

  • Engineering
February 14, 2022
Yudong Cai

Bitset Cover Image Bitset 封面圖片

作者:蔡裕東倪安琪

隨著 Milvus 2.0 的發布,向量資料庫的各種新的基本功能也一併提供。在這些新功能中,時間旅行、屬性過濾和刪除操作是相互關聯的,因為這三個功能是由一個共同的機制 - bitset 來實現的。

因此,這篇文章的目的是闡明 bitset 在 Milvus 中的概念,並通過三個例子解釋它是如何支援刪除操作、時間旅行和屬性過濾的。

什麼是 bitset?

bitset 是一個位元陣列 ("0 「和 」1"),可以用來表示某些資料資訊。使用比特集,您可以精簡且有效率地儲存特定類型的資料,而不需要以 Ints、Floats 或 Chars 來儲存。比特集以布林邏輯運作,根據布林邏輯,輸出的值為有效或無效,通常分別以 "1 「和 」0 "表示。"1「 代表有效,」0" 代表無效。由於 bits 集的效率很高,可以節省儲存空間,因此也可以用來實現許多功能,例如屬性過濾、刪除操作、時間旅行等。

從版本 0.7.0 開始,Milvus 中引入了 bitset 的概念來實現刪除功能。具體來說,bitset 用來標記段中的每一行是否被刪除。刪除的實體在相對應的 bitset 中會被標記為 "1",因此,在搜尋或查詢時,刪除的實體將不會被計算。

在 Milvus 2.0 版本中,比特集的應用擴展到更多的功能,例如屬性過濾和時間旅行。bitset 的一般原則維持不變。也就是說,如果一個實體在相對應的 bitset 中被標記為 "1",該實體在搜索或查詢時將被忽略。在 Milvus 中,比特集用於啟用三個功能:

  • 屬性過濾
  • 資料刪除
  • 時間旅行查詢

比特集在 Milvus 中是如何工作的?

下面的例子用來說明在 Milvus 中 bitset 是如何工作的。

先決條件

假設有一個包含八個實體的區段,一系列的資料處理語言 (DML) 事件發生的順序如下圖所示。

  • 其中四個實體,其primary_keys 分別為 [1、2、3、4],在時間戳ts 等於 100 時插入。
  • 其餘四個實體,其primary_keys 為 [5、6、7、8],會在時間戳ts 等於 200 時插入。
  • primary_keys 為 [7, 8] 的實體,會在時間戳記ts 等於 300 時刪除。
  • 只有primary_keys 是 [1, 3, 5, 7] 的實體滿足屬性過濾的條件。

DML events DML 事件

案例一

假設使用者為time_travel 設定的值是 150。換句話說,當ts = 150 時,使用者對儲存於 Milvus 的資料進行查詢。位元集的產生過程如圖 1 所示。

在初始篩選階段,filter_bitset 的結果應該是 [1,0,1,0,1,0,1,0],因為實體 [1,3,5,7] 是有效的篩選結果,並且在比特集中標記為 "1"。然而,當ts 等於 150 時,實體 [4, 5, 6, 7] 甚至沒有插入向量資料庫。因此,無論篩選條件為何,這四個實體都應該標記為 "0"。現在的 bitset 結果應該是 [1,0,1,0,0,0,0,0]。由於在 Milvus 中,比特集計算的一般原則是在搜尋或查詢時忽略比特集中標記為 "1 "的實體,因此經過時間旅行和屬性篩選後的比特集結果需要翻轉,才能與刪除位圖結合。filter_bitset 的翻轉結果應該是 [0,1,0,1,1,1,1]。

至於刪除位元集del_bitset ,初始值應該是 [0, 0, 0, 0, 0, 0, 1, 1]。但是,直到ts 為 300 時,才會刪除實體 7 和 8。因此,當ts 為 150 時,實體 7 和 8 仍然有效。因此,Time Travel 之後的del_bitset 值應該是 [0,0,0,0,0,0,0,0]。

現在,經過時間旅行和屬性篩選之後,我們有兩個位元集: filter_bitset [0, 1, 0, 1, 1, 1, 1] 和del_bitset [0, 0, 0, 0, 0, 0, 0, 0]。 使用「OR」二進制邏輯算子結合這兩個位元集。result_bitset 的最終數值是 [0,1,0,1,1,1,1]。也就是說,在接下來的搜尋或查詢階段,只有實體 1 和 3 會被計算出來。

Figure 1 圖一

情況二

假設使用者為time_travel 設定的值是 250。換句話說,當ts = 250 時,使用者對儲存於 Milvus 的資料進行查詢。比特集的產生過程如圖 2 所示。

與情況一一樣,初始屬性篩選階段的結果filter_bitset 應該是 [1,0,1,0,1,0,1,0]。

ts= 250 時,所有實體 [1, 2, 3, 4, 5, 6, 7, 8] 都會插入向量資料庫。因此,之前filter_bitset 的結果維持不變。同樣地,我們需要翻轉filter_bitset 的結果,就會得到 [0, 1, 0, 1, 0, 1, 0, 1]。

至於刪除位元集del_bitset ,初始值應該是 [0, 0, 0, 0, 0, 0, 1, 1]。但是,直到ts 為 300 時,實體 7 和 8 才被刪除。因此,當ts 為 250 時,實體 7 和 8 仍然有效。因此,Time Travel 之後的del_bitset 值應該是 [0,0,0,0,0,0,0,0]。

現在,經過時間旅行和屬性篩選之後,我們有兩個位元集: filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] 和del_bitset [0, 0, 0, 0, 0, 0, 0]。 使用「OR」二進制邏輯算子結合這兩個位元集。result_bitset 的最終數值是 [0,1,0,1,0,1,0,1]。也就是說,在接下來的搜尋或查詢階段,只有實體 [1, 3, 5, 7] 會被計算出來。

Figure 2 圖二

案例三

假設使用者為time_travel 設定的值是 350。換句話說,當ts = 350 時,使用者對儲存於 Milvus 的資料進行查詢。比特集的產生過程如圖 3 所示。

與情況一和情況二相同,初始屬性篩選階段的結果filter_bitset 是 [0,1,0,1,0,1,0,1]。

ts= 350 時,所有實體 [1, 2, 3, 4, 5, 6, 7, 8] 都會插入向量資料庫。因此,filter_bitset 的最終翻轉結果為 [0,1,0,1,0,1,0,1],與情況二相同。

至於刪除位元集del_bitset ,由於ts= 350 時,實體 7 和 8 已經被刪除,因此del_bitset 的結果應該是 [0, 0, 0, 0, 0, 0, 1, 1]。

現在,經過時間旅行和屬性篩選之後,我們有兩個位元集: filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] 和del_bitset [0, 0, 0, 0, 0, 0, 1, 1]。 使用「OR」二進制邏輯算子結合這兩個位元集。result_bitset 的最終數值是 [0,1,0,1,0,1,1]。也就是說,在接下來的搜尋或查詢階段,只有實體 [1, 3, 5] 會被計算出來。

Figure 3 圖三

下一步是什麼?

在 2.0 新功能系列部落格中,我們的目標是解釋新功能的設計。閱讀此系列部落格的更多內容!

Try Managed Milvus for Free

Zilliz Cloud is hassle-free, powered by Milvus and 10x faster.

Get Started

Like the article? Spread the word

繼續閱讀