Filtrage géospatial et recherche vectorielle avec les champs géométriques et RTREE dans Milvus 2.6

Alors que les systèmes d'IA sont de plus en plus appliqués à la prise de décision en temps réel, les données géospatiales deviennent de plus en plus importantes dans un ensemble croissant d'applications - en particulier celles qui opèrent dans le monde physique ou servent les utilisateurs à travers des lieux réels.

Prenons l'exemple des plateformes de livraison de nourriture comme DoorDash ou Uber Eats. Lorsqu'un utilisateur passe une commande, le système ne se contente pas de calculer la distance la plus courte entre deux points. Il évalue la qualité des restaurants, la disponibilité des coursiers, les conditions de circulation en direct, les zones de service et, de plus en plus, l'intégration des utilisateurs et des articles qui représentent les préférences personnelles. De même, les véhicules autonomes doivent planifier leur trajet, détecter les obstacles et comprendre la sémantique de la scène en respectant des contraintes de latence strictes, souvent en l'espace de quelques millisecondes. Dans ces domaines, les décisions efficaces dépendent de la combinaison des contraintes spatiales et de la similarité sémantique, plutôt que de les traiter comme des étapes indépendantes.

Cependant, au niveau des données, les données spatiales et sémantiques sont traditionnellement traitées par des systèmes distincts.

• Les bases de données géospatiales et les extensions spatiales sont conçues pour stocker les coordonnées, les polygones et les relations spatiales telles que le confinement ou la distance.

• Les bases de données vectorielles, quant à elles, traitent les encastrements vectoriels qui représentent la signification sémantique des données.

Lorsque les applications ont besoin des deux, elles sont souvent obligées d'utiliser des pipelines de requête en plusieurs étapes : filtrage par emplacement dans un système, puis recherche vectorielle dans un autre. Cette séparation accroît la complexité du système, augmente le temps de latence des requêtes et rend difficile l'exécution efficace du raisonnement spatial et sémantique à grande échelle.

Milvus 2.6 résout ce problème en introduisant le champ géométrique, qui permet de combiner directement la recherche de similarité vectorielle avec des contraintes spatiales. Cela permet des cas d'utilisation tels que :

• Service de localisation (LBS) : "trouver des points d'intérêt similaires dans ce pâté de maisons".

• Recherche multimodale : recherche multimodale : "trouver des photos similaires dans un rayon de 1 km autour de ce point".

• Cartes et logistique : "actifs à l'intérieur d'une région" ou "itinéraires croisant un chemin".

Associé au nouvel index RTREE - unestructure arborescente optimisée pour le filtrage spatial - Milvus prend désormais en charge des opérateurs géospatiaux efficaces tels que st_contains, st_within, et st_dwithin, ainsi que la recherche vectorielle à haute dimension. Ensemble, ils rendent la recherche intelligente spatialement consciente non seulement possible, mais pratique.

Dans ce billet, nous verrons comment fonctionnent le champ géométrique et l'index RTREE, et comment ils se combinent avec la recherche de similarité vectorielle pour permettre des applications sémantiques spatiales dans le monde réel.

Qu'est-ce qu'un champ géométrique dans Milvus ?

Un champ géométrique est un type de données défini par le schéma (DataType.GEOMETRY) dans Milvus utilisé pour stocker des données géométriques. Contrairement aux systèmes qui ne traitent que les coordonnées brutes, Milvus prend en charge une gamme de structures spatiales, notamment Point, LineString et Polygon.

Il est ainsi possible de représenter des concepts du monde réel tels que des emplacements de restaurants (Point), des zones de livraison (Polygone) ou des trajectoires de véhicules autonomes (LineString), le tout dans la même base de données que celle qui stocke les vecteurs sémantiques. En d'autres termes, Milvus devient un système unifié permettant de savoir à la fois où se trouve quelque chose et ce que cela signifie.

Les valeurs géométriques sont stockées à l'aide du format Well-Known Text (WKT), une norme lisible par l'homme pour l'insertion et l'interrogation de données géométriques. Cela simplifie l'ingestion et l'interrogation des données car les chaînes WKT peuvent être insérées directement dans un enregistrement Milvus. Par exemple :

data = [
    { 
        "id": 1,
        "geo": "POINT(116.4074 39.9042)",
        "vector": vector,
    }
]

Qu'est-ce que l'index RTREE et comment fonctionne-t-il ?

Une fois que Milvus a introduit le type de données Géométrie, il a également besoin d'un moyen efficace de filtrer les objets spatiaux. Milvus gère cela à l'aide d'un pipeline de filtrage spatial en deux étapes :

• Filtrage grossier : Réduit rapidement le nombre de candidats à l'aide d'index spatiaux tels que RTREE.

• Filtrage fin : Applique des contrôles géométriques exacts aux candidats restants, en garantissant l'exactitude des limites.

Cette conception permet d'équilibrer les performances et la précision. L'index spatial élimine de manière agressive les données non pertinentes, tandis que des contrôles géométriques précis garantissent des résultats corrects pour des opérateurs tels que le confinement, l'intersection et les seuils de distance.

Au cœur de ce pipeline se trouve RTREE (Rectangle Tree), une structure d'indexation spatiale conçue pour accélérer les requêtes sur les données géométriques. RTREE organise les objets de manière hiérarchique à l'aide de rectangles de délimitation minimale (MBR), ce qui permet de sauter de grandes portions de l'espace de recherche lors de l'exécution de la requête.

Phase 1 : Construction de l'index RTREE

La construction de l'index RTREE suit un processus ascendant qui regroupe les objets spatiaux proches dans des régions délimitées de plus en plus grandes :

1. Créer des nœuds feuilles : Pour chaque objet géométrique, calculez son rectangle minimal de délimitation (MBR) - le plus petit rectangle qui contient entièrement l'objet - et stockez-le en tant que nœud feuille.

2. Regrouper en boîtes plus grandes : Regroupez les nœuds feuilles proches et enveloppez chaque groupe à l'intérieur d'un nouveau MBR, en produisant des nœuds internes.

3. Ajouter le nœud racine : Créer un nœud racine dont le MBR couvre tous les groupes internes, formant ainsi une structure arborescente équilibrée en hauteur.

Phase 2 : Accélérer les requêtes

1. Formez le MBR de la requête : calculez le MBR de la géométrie utilisée dans votre requête.

2. Élaguez les branches : En commençant par la racine, comparez le MBR de la requête avec chaque nœud interne. Sautez toute branche dont le MBR ne croise pas le MBR de la requête.

3. Rassembler les candidats : Descendre dans les branches qui se croisent et rassembler les nœuds feuilles candidats.

4. Effectuer une correspondance exacte : pour chaque candidat, exécuter le prédicat spatial pour obtenir des résultats précis.

Pourquoi RTREE est rapide

RTREE offre d'excellentes performances en matière de filtrage spatial grâce à plusieurs caractéristiques de conception clés :

• Chaque nœud stocke un MBR : chaque nœud évalue la surface de toutes les géométries de son sous-arbre. Il est ainsi facile de décider si une branche doit être explorée au cours d'une requête.

• Élagage rapide : Seuls les sous-arbres dont le MBR croise la région interrogée sont explorés. Les zones non pertinentes sont entièrement ignorées.

• S'adapte à la taille des données : RTREE prend en charge les recherches spatiales en temps O(log N), ce qui permet d'effectuer des requêtes rapides même lorsque le jeu de données s'accroît.

• Implémentation Boost.Geometry : Milvus construit son index RTREE à l'aide de Boost.Geometry, une bibliothèque C++ largement utilisée qui fournit des algorithmes géométriques optimisés et une implémentation RTREE thread-safe adaptée aux charges de travail simultanées.

Opérateurs géométriques pris en charge

Milvus fournit un ensemble d'opérateurs spatiaux qui vous permettent de filtrer et d'extraire des entités sur la base de relations géométriques. Ces opérateurs sont essentiels pour les charges de travail qui doivent comprendre comment les objets sont liés les uns aux autres dans l'espace.

Le tableau suivant répertorie les opérateurs géométriques actuellement disponibles dans Milvus.

Opérateur	Description de l'opérateur
st_intersects(A, B)	Renvoie VRAI si les géométries A et B partagent au moins un point commun.
st_contains(A, B)	Retourne VRAI si la géométrie A contient complètement la géométrie B (à l'exception de la frontière).
st_within(A, B)	Retourne VRAI si la géométrie A est complètement contenue dans la géométrie B. C'est l'inverse de st_contains(A, B).
st_covers(A, B)	Retourne VRAI si la géométrie A recouvre la géométrie B (y compris la frontière).
st_touches(A, B)	Retourne VRAI si les géométries A et B se touchent au niveau de leurs limites mais ne se coupent pas à l'intérieur.
st_equals(A, B)	Retourne VRAI si les géométries A et B sont spatialement identiques.
st_overlaps(A, B)	Retourne VRAI si les géométries A et B se chevauchent partiellement et qu'aucune ne contient entièrement l'autre.
st_dwithin(A, B, d)	Retourne VRAI si la distance entre A et B est inférieure à d.

Comment combiner l'index de géolocalisation et l'index vectoriel ?

Grâce à la prise en charge de la géométrie et à l'index RTREE, Milvus peut combiner le filtrage géospatial et la recherche de similarité vectorielle dans un seul flux de travail. Le processus se déroule en deux étapes :

1. Filtrer par emplacement à l'aide de RTREE : Milvus utilise d'abord l'index RTREE pour limiter la recherche aux entités situées dans la plage géographique spécifiée (par exemple, " dans un rayon de 2 km ").

2. Classement par sémantique à l'aide de la recherche vectorielle : Parmi les candidats restants, l'index vectoriel sélectionne les N premiers résultats les plus similaires sur la base de la similarité d'intégration.

Cas d'utilisation de la recherche géovectorielle dans le monde réel

1. Services de livraison : Recommandations plus intelligentes et tenant compte de la localisation

Des plateformes telles que DoorDash ou Uber Eats traitent des centaines de millions de demandes chaque jour. Dès qu'un utilisateur ouvre l'application, le système doit déterminer, en fonction de l'emplacement de l'utilisateur, de l'heure de la journée, de ses préférences gustatives, des délais de livraison estimés, du trafic en temps réel et de la disponibilité des coursiers, quels sont les restaurants ou les coursiers qui correspondent le mieux à l'instant présent.

Traditionnellement, cela nécessite l'interrogation d'une base de données géospatiale et d'un moteur de recommandation distinct, suivie de plusieurs cycles de filtrage et de reclassement. Avec l'index de géolocalisation, Milvus simplifie considérablement ce flux de travail :

• Stockage unifié - Les coordonnées des restaurants, les emplacements des coursiers et les préférences des utilisateurs sont regroupés dans un seul système.

• Recherche conjointe - Appliquer d'abord un filtre spatial (par exemple, restaurants dans un rayon de 3 km), puis utiliser la recherche vectorielle pour classer par similarité, préférence gustative ou qualité.

• Prise de décision dynamique - Combinez la distribution des coursiers en temps réel et les signaux de circulation pour affecter rapidement le coursier le plus proche et le plus approprié.

Cette approche unifiée permet à la plateforme d'effectuer un raisonnement spatial et sémantique en une seule requête. Par exemple, lorsqu'un utilisateur recherche "riz au curry", Milvus récupère les restaurants qui sont sémantiquement pertinents et donne la priorité à ceux qui sont proches, qui livrent rapidement et qui correspondent au profil gustatif historique de l'utilisateur.

2. Conduite autonome : Des décisions plus intelligentes

Dans la conduite autonome, l'indexation géospatiale est fondamentale pour la perception, la localisation et la prise de décision. Les véhicules doivent en permanence s'aligner sur des cartes haute définition, détecter les obstacles et planifier des trajectoires sûres, le tout en quelques millisecondes.

Avec Milvus, le type Geometry et l'index RTREE peuvent stocker et interroger des structures spatiales riches telles que :

• les limites des routes (LineString)

• Les zones de régulation du trafic (Polygone)

• Obstacles détectés (Point)

Ces structures peuvent être indexées efficacement, ce qui permet aux données géospatiales de participer directement à la boucle de décision de l'IA. Par exemple, un véhicule autonome peut rapidement déterminer si ses coordonnées actuelles se situent à l'intérieur d'une voie spécifique ou s'il croise une zone réglementée, simplement grâce à un prédicat spatial RTREE.

Lorsqu'il est associé à des intégrations vectorielles générées par le système de perception, telles que des intégrations de scènes qui capturent l'environnement de conduite actuel, Milvus peut prendre en charge des requêtes plus avancées, telles que la récupération de scénarios de conduite historiques similaires à la conduite actuelle dans un rayon de 50 mètres. Cela permet aux modèles d'interpréter l'environnement plus rapidement et de prendre de meilleures décisions.

Conclusion

La géolocalisation ne se résume pas à la latitude et à la longitude. Dans les applications sensibles à la localisation, elle fournit un contexte essentiel sur l'endroit où les événements se produisent, sur les relations spatiales entre les entités et sur la manière dont ces relations influencent le comportement du système. Combinées aux signaux sémantiques des modèles d'apprentissage automatique, les données géospatiales permettent d'enrichir les requêtes qui sont difficiles à exprimer - ou inefficaces à exécuter - lorsque les données spatiales et vectorielles sont traitées séparément.

Avec l'introduction du champ géométrique et de l'index RTREE, Milvus intègre la recherche de similarité vectorielle et le filtrage spatial dans un moteur de requête unique. Cela permet aux applications d'effectuer une recherche conjointe entre les vecteurs, les données géospatiales et le temps, en prenant en charge des cas d'utilisation tels que les systèmes de recommandation tenant compte de l'espace, la recherche multimodale basée sur l'emplacement et les analyses limitées à une région ou à un chemin. Plus important encore, il réduit la complexité de l'architecture en éliminant les pipelines à plusieurs étapes qui déplacent les données entre des systèmes spécialisés.

À mesure que les systèmes d'IA se rapprochent de la prise de décision dans le monde réel, la compréhension de la pertinence du contenu devra de plus en plus être associée à l'endroit où elle s'applique et au moment où elle est importante. Milvus fournit les éléments de base pour cette classe de charges de travail spatiales-sémantiques d'une manière qui est à la fois expressive et pratique pour fonctionner à grande échelle.

Pour plus d'informations sur le champ géométrique et l'index RTREE, consultez la documentation ci-dessous :

• Geometry Field | Milvus Documentation

• RTREE | Documentation Milvus

Vous avez des questions ou vous souhaitez approfondir l'une des fonctionnalités de la dernière version de Milvus ? Rejoignez notre canal Discord ou déposez des questions sur GitHub. Vous pouvez également réserver une session individuelle de 20 minutes pour obtenir des informations, des conseils et des réponses à vos questions dans le cadre des Heures de bureau Milvus.

En savoir plus sur les fonctionnalités de Milvus 2.6

• Présentation de Milvus 2.6 : recherche vectorielle abordable à l'échelle du milliard

• Présentation de la fonction d'intégration : Comment Milvus 2.6 rationalise la vectorisation et la recherche sémantique

• Déchiquetage JSON dans Milvus : filtrage JSON 88,9 fois plus rapide et flexible

• Déverrouiller la véritable recherche au niveau de l'entité : Nouvelles fonctionnalités Array-of-Structs et MAX_SIM dans Milvus

• MinHash LSH dans Milvus : l'arme secrète pour lutter contre les doublons dans les données de formation LLM

• La compression vectorielle à l'extrême : comment Milvus répond à 3× plus de requêtes avec RaBitQ

• Les benchmarks mentent - les bases de données vectorielles méritent un vrai test

• Nous avons remplacé Kafka/Pulsar par un Woodpecker pour Milvus

• La recherche vectorielle dans le monde réel : comment filtrer efficacement sans tuer le rappel ?