Filtraggio geospaziale e ricerca vettoriale insieme a campi geometrici e RTREE in Milvus 2.6

Poiché i sistemi di intelligenza artificiale sono sempre più applicati al processo decisionale in tempo reale, i dati geospaziali diventano sempre più importanti in una serie crescente di applicazioni, in particolare quelle che operano nel mondo fisico o che servono gli utenti in luoghi reali.

Si pensi alle piattaforme di consegna di cibo come DoorDash o Uber Eats. Quando un utente effettua un ordine, il sistema non si limita a calcolare la distanza più breve tra due punti. Valuta la qualità del ristorante, la disponibilità del corriere, le condizioni del traffico in tempo reale, le aree di servizio e, sempre più spesso, le incorporazioni di utenti e articoli che rappresentano le preferenze personali. Allo stesso modo, i veicoli autonomi devono eseguire la pianificazione del percorso, il rilevamento degli ostacoli e la comprensione semantica della scena con vincoli di latenza molto stretti, spesso entro i millisecondi. In questi domini, le decisioni efficaci dipendono dalla combinazione di vincoli spaziali e similarità semantica, piuttosto che trattarli come fasi indipendenti.

A livello di dati, tuttavia, i dati spaziali e semantici sono stati tradizionalmente gestiti da sistemi separati.

• I database geospaziali e le estensioni spaziali sono progettati per memorizzare coordinate, poligoni e relazioni spaziali come il contenimento o la distanza.

• I database vettoriali gestiscono le incorporazioni vettoriali che rappresentano il significato semantico dei dati.

Quando le applicazioni hanno bisogno di entrambe le cose, sono spesso costrette a eseguire query in più fasi: filtrare in base alla posizione in un sistema, quindi eseguire la ricerca vettoriale in un altro. Questa separazione aumenta la complessità del sistema, la latenza delle interrogazioni e rende difficile eseguire ragionamenti spaziali e semantici in modo efficiente su scala.

Milvus 2.6 affronta questo problema introducendo il campo geometrico, che consente di combinare la ricerca di similarità vettoriale direttamente con i vincoli spaziali. Ciò consente di risolvere casi d'uso quali:

• Servizi di localizzazione (LBS): "trovare POI simili all'interno di questo isolato".

• Ricerca multimodale: "trovare foto simili nel raggio di 1 km da questo punto".

• Mappe e logistica: "beni all'interno di una regione" o "percorsi che intersecano un percorso".

Insieme al nuovo indice RTREE, unastruttura ad albero ottimizzata per il filtraggio spaziale, Milvus supporta ora operatori geospaziali efficienti come st_contains, st_within e st_dwithin oltre alla ricerca vettoriale ad alta dimensione. Insieme, questi strumenti rendono il reperimento intelligente e consapevole dello spazio non solo possibile, ma anche pratico.

In questo post spiegheremo come funzionano il campo geometrico e l'indice RTREE e come si combinano con la ricerca per similarità vettoriale per consentire applicazioni spaziali-semantiche del mondo reale.

Cos'è un campo geometrico in Milvus?

Un campo geometrico è un tipo di dati definito dallo schema (DataType.GEOMETRY) in Milvus utilizzato per memorizzare dati geometrici. A differenza dei sistemi che gestiscono solo le coordinate grezze, Milvus supporta una serie di strutture spaziali, tra cui Point, LineString e Polygon.

In questo modo è possibile rappresentare concetti del mondo reale come la posizione di un ristorante (Point), le zone di consegna (Polygon) o le traiettorie di un veicolo autonomo (LineString), il tutto all'interno dello stesso database che memorizza i vettori semantici. In altre parole, Milvus diventa un sistema unificato per sapere sia dove si trova qualcosa che cosa significa.

I valori geometrici sono memorizzati utilizzando il formato Well-Known Text (WKT), uno standard leggibile dall'uomo per l'inserimento e l'interrogazione dei dati geometrici. Questo semplifica l'inserimento e l'interrogazione dei dati perché le stringhe WKT possono essere inserite direttamente in un record Milvus. Per esempio:

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

Cos'è l'indice RTREE e come funziona?

Una volta introdotto il tipo di dati Geometry, Milvus ha bisogno di un modo efficiente per filtrare gli oggetti spaziali. Milvus gestisce questo aspetto utilizzando una pipeline di filtraggio spaziale a due stadi:

• Filtraggio grossolano: Restringe rapidamente i candidati utilizzando indici spaziali come RTREE.

• Filtraggio fine: Applica controlli geometrici esatti ai candidati rimasti, garantendo la correttezza ai confini.

Questo progetto bilancia prestazioni e accuratezza. L'indice spaziale elimina in modo aggressivo i dati irrilevanti, mentre i controlli geometrici precisi assicurano risultati corretti per operatori come il contenimento, l'intersezione e le soglie di distanza.

Il cuore di questa pipeline è RTREE (Rectangle Tree), una struttura di indicizzazione spaziale progettata per accelerare le interrogazioni sui dati geometrici. RTREE funziona organizzando gli oggetti in modo gerarchico utilizzando i rettangoli minimi di delimitazione (MBR), consentendo di saltare ampie porzioni dello spazio di ricerca durante l'esecuzione delle query.

Fase 1: costruzione dell'indice RTREE

La costruzione di RTREE segue un processo bottom-up che raggruppa gli oggetti spaziali vicini in regioni di delimitazione sempre più grandi:

1. Creare i nodi foglia: Per ogni oggetto geometrico, calcolare il suo Minimum Bounding Rectangle (MBR)- il rettangolo più piccolo che contiene completamente l'oggetto - e memorizzarlo come nodo foglia.

2. Raggruppare in riquadri più grandi: Raggruppare i nodi foglia vicini e avvolgere ogni gruppo in un nuovo MBR, producendo nodi interni.

3. Aggiungere il nodo radice: Creare un nodo radice il cui MBR copre tutti i gruppi interni, formando una struttura ad albero bilanciata in altezza.

Fase 2: accelerazione delle query

1. Formare l'MBR della query: calcolare l'MBR per la geometria utilizzata nella query.

2. Potare i rami: Partendo dalla radice, confrontare l'MBR della query con ogni nodo interno. Saltare i rami il cui MBR non si interseca con l'MBR della query.

3. Raccogliere i candidati: Scendere nei rami che si intersecano e raccogliere i nodi foglia candidati.

4. Eseguire la corrispondenza esatta: per ogni candidato, eseguire il predicato spaziale per ottenere risultati precisi.

Perché RTREE è veloce

RTREE offre prestazioni elevate nel filtraggio spaziale grazie a diverse caratteristiche progettuali fondamentali:

• Ogni nodo memorizza un MBR: ogni nodo approssima l'area di tutte le geometrie nel suo sottoalbero. In questo modo è facile decidere se un ramo deve essere esplorato durante un'interrogazione.

• Potatura veloce: Vengono esplorati solo i sottoalberi il cui MBR interseca la regione dell'interrogazione. Le aree irrilevanti vengono completamente ignorate.

• Scala con la dimensione dei dati: RTREE supporta ricerche spaziali in tempo O(log N), consentendo interrogazioni veloci anche quando il set di dati si espande.

• Implementazione di Boost.Geometry: Milvus costruisce il suo indice RTREE utilizzando Boost.Geometry, una libreria C++ ampiamente utilizzata che fornisce algoritmi geometrici ottimizzati e un'implementazione RTREE thread-safe adatta a carichi di lavoro concomitanti.

Operatori geometrici supportati

Milvus offre una serie di operatori spaziali che consentono di filtrare e recuperare entità in base a relazioni geometriche. Questi operatori sono essenziali per i carichi di lavoro che devono capire come gli oggetti si relazionano tra loro nello spazio.

La tabella seguente elenca gli operatori geometrici attualmente disponibili in Milvus.

Operatore	Descrizione
st_intersects(A, B)	Restituisce VERO se le geometrie A e B hanno almeno un punto in comune.
st_contiene(A, B)	Restituisce VERO se la geometria A contiene completamente la geometria B (escluso il confine).
st_within(A, B)	Restituisce VERO se la geometria A è completamente contenuta nella geometria B. È l'inverso di st_contains(A, B).
st_covers(A, B)	Restituisce VERO se la geometria A copre la geometria B (compresi i confini).
st_tocca(A, B)	Restituisce VERO se le geometrie A e B si toccano ai loro confini ma non si intersecano internamente.
st_equals(A, B)	Restituisce VERO se le geometrie A e B sono spazialmente identiche.
st_overlaps(A, B)	Restituisce VERO se le geometrie A e B si sovrappongono parzialmente e nessuna contiene completamente l'altra.
st_dwithin(A, B, d)	Restituisce VERO se la distanza tra A e B è inferiore a d.

Come combinare l'indice di geolocalizzazione e l'indice vettoriale

Grazie al supporto della geometria e all'indice RTREE, Milvus può combinare il filtraggio geospaziale con la ricerca di similarità vettoriale in un unico flusso di lavoro. Il processo funziona in due fasi:

1. Filtrare in base alla posizione utilizzando RTREE: Milvus utilizza innanzitutto l'indice RTREE per restringere la ricerca alle entità all'interno dell'intervallo geografico specificato (ad esempio, "entro 2 km").

2. Classifica per semantica utilizzando la ricerca vettoriale: Tra i candidati rimanenti, l'indice vettoriale seleziona la Top-N dei risultati più simili in base alla similarità di incorporazione.

Casi d'uso nel mondo reale della ricerca geo-vettoriale

1. Servizi di consegna: Raccomandazioni più intelligenti e consapevoli della posizione

Piattaforme come DoorDash o Uber Eats gestiscono centinaia di milioni di richieste ogni giorno. Nel momento in cui un utente apre l'applicazione, il sistema deve determinare, in base alla posizione dell'utente, all'ora del giorno, alle preferenze di gusto, ai tempi di consegna stimati, al traffico in tempo reale e alla disponibilità del corriere, quali sono i ristoranti o i corrieri più adatti in questo momento.

Tradizionalmente, questo richiede l'interrogazione di un database geospaziale e di un motore di raccomandazione separato, seguito da molteplici cicli di filtraggio e ri-classificazione. Con il Geolocation Index, Milvus semplifica notevolmente questo flusso di lavoro:

• Archiviazione unificata - Le coordinate dei ristoranti, le posizioni dei corrieri e le incorporazioni delle preferenze degli utenti si trovano tutte in un unico sistema.

• Recupero congiunto - Applicare prima un filtro spaziale (ad esempio, ristoranti entro 3 km), quindi utilizzare la ricerca vettoriale per classificare in base alla somiglianza, alle preferenze di gusto o alla qualità.

• Processo decisionale dinamico - Combinare la distribuzione dei corrieri in tempo reale e i segnali stradali per assegnare rapidamente il corriere più vicino e più adatto.

Questo approccio unificato consente alla piattaforma di eseguire ragionamenti spaziali e semantici in un'unica interrogazione. Ad esempio, quando un utente cerca "riso al curry", Milvus recupera i ristoranti semanticamente rilevanti e dà la priorità a quelli che si trovano nelle vicinanze, che consegnano rapidamente e che corrispondono al profilo storico dei gusti dell'utente.

2. Guida autonoma: Decisioni più intelligenti

Nella guida autonoma, l'indicizzazione geospaziale è fondamentale per la percezione, la localizzazione e il processo decisionale. I veicoli devono allinearsi continuamente a mappe ad alta definizione, rilevare gli ostacoli e pianificare traiettorie sicure, il tutto in pochi millisecondi.

Con Milvus, il tipo Geometry e l'indice RTREE possono memorizzare e interrogare strutture spaziali ricche come:

• Confini stradali (LineString)

• Zone di regolazione del traffico (poligono)

• Ostacoli rilevati (Point)

Queste strutture possono essere indicizzate in modo efficiente, consentendo ai dati geospaziali di partecipare direttamente al ciclo decisionale dell'intelligenza artificiale. Ad esempio, un veicolo autonomo può determinare rapidamente se le sue coordinate attuali rientrano in una corsia specifica o se intersecano un'area limitata, semplicemente attraverso un predicato spaziale RTREE.

Se combinato con le incorporazioni vettoriali generate dal sistema di percezione, come le incorporazioni della scena che catturano l'ambiente di guida corrente, Milvus può supportare query più avanzate, come il recupero di scenari di guida storici simili a quello attuale in un raggio di 50 metri. Questo aiuta i modelli a interpretare l'ambiente più velocemente e a prendere decisioni migliori.

Conclusioni

La geolocalizzazione è molto più che latitudine e longitudine. Nelle applicazioni sensibili alla localizzazione, fornisce un contesto essenziale sul luogo in cui si verificano gli eventi, sul modo in cui le entità si relazionano spazialmente e sul modo in cui queste relazioni modellano il comportamento del sistema. Se combinati con i segnali semantici dei modelli di apprendimento automatico, i dati geospaziali consentono una classe più ricca di interrogazioni che sono difficili da esprimere o inefficienti da eseguire quando i dati spaziali e vettoriali sono gestiti separatamente.

Con l'introduzione del campo geometrico e dell'indice RTREE, Milvus riunisce la ricerca di similarità vettoriale e il filtraggio spaziale in un unico motore di interrogazione. Ciò consente alle applicazioni di eseguire il reperimento congiunto di vettori, dati geospaziali e tempo, supportando casi d'uso come i sistemi di raccomandazione spaziali, la ricerca multimodale basata sulla posizione e l'analisi di regioni o percorsi limitati. Inoltre, riduce la complessità architettonica eliminando le pipeline a più stadi che spostano i dati tra sistemi specializzati.

Mentre i sistemi di intelligenza artificiale continuano ad avvicinarsi al processo decisionale del mondo reale, la comprensione dei contenuti rilevanti dovrà essere sempre più associata a dove si applicano e quando sono importanti. Milvus fornisce gli elementi costitutivi per questa classe di carichi di lavoro spaziali-semantici in un modo che è sia espressivo che pratico per operare su scala.

Per ulteriori informazioni sul campo geometrico e sull'indice RTREE, consultare la documentazione qui sotto:

• Campo geometrico | Documentazione Milvus

• RTREE | Documentazione Milvus

Avete domande o volete un approfondimento su una qualsiasi caratteristica dell'ultima versione di Milvus? Unitevi al nostro canale Discord o inviate problemi su GitHub. È anche possibile prenotare una sessione individuale di 20 minuti per ottenere approfondimenti, indicazioni e risposte alle vostre domande tramite Milvus Office Hours.

Per saperne di più sulle caratteristiche di Milvus 2.6

• Presentazione di Milvus 2.6: ricerca vettoriale accessibile su scala miliardaria

• Introduzione alla funzione Embedding: Come Milvus 2.6 semplifica la vettorializzazione e la ricerca semantica

• Triturazione JSON in Milvus: filtraggio JSON 88,9 volte più veloce e flessibile

• Il vero recupero a livello di entità: Nuove funzionalità Array-of-Structs e MAX_SIM in Milvus

• MinHash LSH in Milvus: l'arma segreta per combattere i duplicati nei dati di addestramento LLM

• Portare la compressione vettoriale all'estremo: come Milvus serve 3 volte di più le query con RaBitQ

• I benchmark mentono: i DB vettoriali meritano un test reale

• Abbiamo sostituito Kafka/Pulsar con un picchio per Milvus

• Ricerca vettoriale nel mondo reale: come filtrare in modo efficiente senza uccidere il richiamo