🚀 Essayez Zilliz Cloud, la version entièrement gérée de Milvus, gratuitement—découvrez des performances 10x plus rapides ! Essayez maintenant>>

milvus-logo
LFAI
  • Home
  • Blog
  • Comment Bitset permet la polyvalence de la recherche par similarité vectorielle

Comment Bitset permet la polyvalence de la recherche par similarité vectorielle

  • Engineering
February 14, 2022
Yudong Cai

Bitset Cover Image Image de couverture de Bitset

Par Yudong Cai et Angela Ni.

Plusieurs nouvelles fonctionnalités essentielles d'une base de données vectorielle sont fournies avec la sortie de Milvus 2.0. Parmi les nouvelles fonctionnalités, les opérations de déplacement dans le temps, de filtrage des attributs et de suppression sont corrélées, car ces trois fonctionnalités sont réalisées par un mécanisme commun, le bitset.

Cet article vise donc à clarifier le concept de bitset dans Milvus et à expliquer comment il fonctionne pour prendre en charge les opérations de suppression, le voyage dans le temps et le filtrage d'attributs à l'aide de trois exemples.

Qu'est-ce qu'un ensemble de bits ?

Un ensemble de bits est un tableau de nombres de bits ("0" et "1") qui peut être utilisé pour représenter certaines informations de données. Avec les bitsets, vous pouvez stocker certains types de données de manière compacte et efficace, plutôt que de les stocker dans des Ints, des floats ou des chars. Les bitsets fonctionnent selon la logique booléenne, selon laquelle la valeur d'une sortie est soit valide, soit invalide, généralement désignée par "1" et "0" respectivement. La valeur "1" correspond à une valeur valide et la valeur "0" à une valeur non valide. Étant donné que les ensembles de bits sont très efficaces et permettent d'économiser de l'espace de stockage, ils peuvent également être utilisés pour réaliser de nombreuses fonctionnalités telles que le filtrage d'attributs, les opérations de suppression, le voyage dans le temps, etc.

À partir de la version 0.7.0, le concept de bitset a été introduit dans Milvus pour permettre la fonction de suppression. Plus précisément, le jeu de bits est utilisé pour indiquer si chaque ligne du segment est supprimée. Les entités supprimées sont marquées d'un "1" dans l'ensemble de bits correspondant et, par conséquent, les entités supprimées ne seront pas calculées lors d'une recherche ou d'une interrogation.

Dans la version 2.0 de Milvus, l'application de l'ensemble de bits est étendue à d'autres fonctions, telles que le filtrage d'attributs et le voyage dans le temps. Le principe général d'un jeu de bits reste le même. C'est-à-dire que si une entité est marquée d'un "1" dans le jeu de bits correspondant, l'entité sera ignorée lors d'une recherche ou d'une interrogation. Les jeux de bits sont utilisés pour activer 3 fonctions dans Milvus :

  • le filtrage des attributs
  • Suppression de données
  • Requête avec voyage dans le temps

Comment les bitsets fonctionnent-ils dans Milvus ?

Les exemples ci-dessous illustrent le fonctionnement des bitsets dans Milvus.

Conditions préalables

Supposons qu'il y ait un segment avec huit entités et qu'une série d'événements de langage de manipulation de données (DML) se produise dans l'ordre indiqué dans la figure ci-dessous.

  • Quatre des entités, dont les primary_keys sont respectivement [1, 2, 3, 4], sont insérées lorsque l'horodatage ts est égal à 100.
  • Les quatre entités restantes, dont les primary_keys sont [5, 6, 7, 8], sont insérées lorsque l'horodatage ts est égal à 200.
  • Les entités dont les primary_keys sont [7, 8] sont supprimées lorsque l'horodatage ts est égal à 300.
  • Seules les entités dont les primary_keys sont [1, 3, 5, 7] satisfont aux conditions de filtrage des attributs.

DML events Événements DML

Premier cas

Supposons que la valeur définie par un utilisateur pour time_travel soit 150. En d'autres termes, l'utilisateur effectue une requête sur les données stockées dans Milvus lorsque ts = 150. Le processus de génération de l'ensemble de bits est illustré par la figure 1.

Au cours de l'étape de filtrage initiale, le résultat du site filter_bitset devrait être [1, 0, 1, 0, 1, 0, 1, 0] car les entités [1, 3, 5, 7] sont des résultats de filtrage valides et marqués comme "1" dans le jeu de bits. Toutefois, les entités [4, 5, 6, 7] n'ont même pas été insérées dans la base de données vectorielle lorsque ts est égal à 150. Par conséquent, ces quatre entités doivent être marquées comme "0", quelle que soit la condition de filtrage. Le résultat de l'ensemble de bits devrait être [1, 0, 1, 0, 0, 0, 0, 0]. Étant donné que dans Milvus, le principe général du calcul de l'ensemble de bits est que les entités marquées d'un "1" dans l'ensemble de bits sont ignorées lors d'une recherche ou d'une requête, le résultat de l'ensemble de bits après le voyage dans le temps et le filtrage des attributs doit être inversé afin d'être combiné avec le schéma binaire de suppression. Le résultat inversé de filter_bitset devrait être [0, 1, 0, 1, 1, 1, 1, 1, 1].

Quant à l'ensemble de bits de suppression del_bitset, sa valeur initiale devrait être [0, 0, 0, 0, 0, 0, 1, 1]. Cependant, les entités 7 et 8 ne sont pas supprimées tant que ts n'a pas atteint la valeur 300. Par conséquent, lorsque ts vaut 150, les entités 7 et 8 sont encore valides. Par conséquent, la valeur de del_bitset après Time Travel devrait être [0, 0, 0, 0, 0, 0, 0, 0].

Nous avons maintenant deux ensembles de bits après le voyage dans le temps et le filtrage des attributs : filter_bitset [0, 1, 0, 1, 1, 1, 1, 1] et del_bitset [0, 0, 0, 0, 0, 0, 0, 0]. Combinez ces deux ensembles de bits avec l'opérateur logique binaire "OR". La valeur finale de result_bitset est [0, 1, 0, 1, 1, 1, 1, 1]. En d'autres termes, seules les entités 1 et 3 seront calculées lors de l'étape suivante de recherche ou d'interrogation.

Figure 1 Figure 1

Deuxième cas

Supposons que la valeur fixée par l'utilisateur pour time_travel soit 250. En d'autres termes, l'utilisateur effectue une requête sur les données stockées dans Milvus lorsque ts = 250. Le processus de génération de l'ensemble de bits est illustré par la figure 2.

Comme dans le premier cas, le résultat filter_bitset de l'étape initiale de filtrage des attributs devrait être [1, 0, 1, 0, 1, 0, 1, 0].

Toutes les entités [1, 2, 3, 4, 5, 6, 7, 8] sont insérées dans la base de données vectorielle lorsque ts= 250. Par conséquent, le résultat précédent de filter_bitset reste le même. Une fois encore, nous devons inverser le résultat de filter_bitset, et nous obtiendrons [0, 1, 0, 1, 0, 1, 0, 1].

Quant à l'ensemble de bits de suppression del_bitset, sa valeur initiale devrait être [0, 0, 0, 0, 0, 0, 1, 1]. Cependant, les entités 7 et 8 n'ont pas été supprimées avant que ts ne soit à 300. Par conséquent, lorsque ts vaut 250, les entités 7 et 8 sont encore valides. Par conséquent, la valeur de del_bitset après Time Travel devrait être [0, 0, 0, 0, 0, 0, 0, 0].

Nous avons maintenant deux ensembles de bits après le voyage dans le temps et le filtrage des attributs : filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] et del_bitset [0, 0, 0, 0, 0, 0, 0]. Combinez ces deux ensembles de bits avec l'opérateur logique binaire "OR". La valeur finale de result_bitset est [0, 1, 0, 1, 0, 1, 0, 1]. En d'autres termes, seules les entités [1, 3, 5, 7] seront calculées lors de l'étape suivante de recherche ou d'interrogation.

Figure 2 Figure 2

Troisième cas

Supposons que la valeur fixée par l'utilisateur pour time_travel soit 350. En d'autres termes, l'utilisateur effectue une requête sur les données stockées dans Milvus lorsque ts = 350. Le processus de génération de l'ensemble de bits est illustré par la figure 3.

Comme dans les cas 1 et 2, le résultat filter_bitset de l'étape initiale de filtrage des attributs est [0, 1, 0, 1, 0, 1, 0, 1].

Toutes les entités [1, 2, 3, 4, 5, 6, 7, 8] sont insérées dans la base de données vectorielle lorsque ts= 350. Par conséquent, le résultat final inversé de filter_bitset est [0, 1, 0, 1, 0, 1, 0, 1], comme dans le deuxième cas.

En ce qui concerne l'ensemble binaire de suppression del_bitset, les entités 7 et 8 étant déjà supprimées lorsque ts=350, le résultat de del_bitset devrait être [0, 0, 0, 0, 0, 1, 1].

Nous avons maintenant deux ensembles de bits après le voyage dans le temps et le filtrage des attributs : filter_bitset [0, 1, 0, 1, 0, 1, 0, 1] et del_bitset [0, 0, 0, 0, 0, 0, 1, 1]. Combinez ces deux ensembles de bits avec l'opérateur logique binaire "OR". La valeur finale de result_bitset est [0, 1, 0, 1, 0, 1, 1, 1]. En d'autres termes, seules les entités [1, 3, 5] seront calculées lors de l'étape suivante de recherche ou d'interrogation.

Figure 3 Figure 3

Quelles sont les prochaines nouveautés ?

Dans la série de blogs sur les nouvelles fonctionnalités de la version 2.0, nous expliquons la conception des nouvelles fonctionnalités. En savoir plus sur cette série de blogs !

Try Managed Milvus for Free

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

Get Started

Like the article? Spread the word

Continuer à Lire