indicizzazione e interrogazione elevate dati dimensionali in PostgreSQL

Question

voglio dati dell'indice in dimensioni di altezza (128 vettori dimensionali di interi nella gamma di [0254] Sono possibili):

| id |  vector  | 
| 1 | { 1, 0, ..., 254} | 
| 2 | { 2, 128, ...,1} | 
| . | { 1, 0, ..., 252} | 
| n | { 1, 2, ..., 251} | 

Ho visto che PostGIS attuato R-alberi . Quindi posso utilizzare questi alberi in PostGIS per indicizzare e interrogare vettori multidimensionali in Postgres?

Ho anche visto che c'è uno index implementation for int arrays.

Ora ho domande su come eseguire una query.
È possibile eseguire una ricerca knn e una ricerca raggio su un array intero? Forse dovrei anche definire la mia funzione di distanza. È possibile? Voglio usare il Manhattan distance (distanza di blocco) per le mie domande.

Posso anche rappresentare il mio vettore come una stringa binaria con il modello v1;v2;...;vn. Questo aiuta a eseguire la ricerca?

Per esempio, se ho avuto questi due stringa:

1;2;1;1 
1;3;2;2 

Il risultato/distanza tra queste due stringhe dovrebbe essere 3.

Answer 1

Forse una scelta migliore sarebbe la cube extension, dal momento che l'area di interesse non è un numero intero individuale, ma un vettore completo.

Il cubo supporta l'indicizzazione GiST e Postgres 9.6 porterà anche l'indicizzazione KNN ai cubi, supportando euclidean, taxicab (aka Manhattan) and chebishev distances.

È un po 'fastidioso che 9.6 sia ancora in fase di sviluppo, tuttavia non ci sono problemi di patch di backport per l'estensione del cubo a 9.5 e lo dico per esperienza.

Speriamo che 128 dimensioni siano ancora sufficienti per ottenere meaningful results.

Come fare?

prima avere una tabella di esempio: tavolo

create extension cube; 
create table vectors (id serial, vector cube); 

Popola con l'esempio dei dati:

insert into vectors select id, cube(ARRAY[round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000), round(random()*1000)]) from generate_series(1, 2000000) id; 

Poi provate a selezionare:

explain analyze SELECT * from vectors 
order by cube(ARRAY[966,82,765,343,600,718,338,505]) <#> vector asc limit 10; 
                  QUERY PLAN               
-------------------------------------------------------------------------------------------------------------------------------- 
Limit (cost=123352.07..123352.09 rows=10 width=76) (actual time=1705.499..1705.501 rows=10 loops=1) 
    -> Sort (cost=123352.07..129852.07 rows=2600000 width=76) (actual time=1705.496..1705.497 rows=10 loops=1) 
     Sort Key: (('(966, 82, 765, 343, 600, 718, 338, 505)'::cube <#> vector)) 
     Sort Method: top-N heapsort Memory: 26kB 
     -> Seq Scan on vectors (cost=0.00..67167.00 rows=2600000 width=76) (actual time=0.038..998.864 rows=2600000 loops=1) 
Planning time: 0.172 ms 
Execution time: 1705.541 ms 
(7 rows) 

Dovremmo creare un indice:

create index vectors_vector_idx on vectors (vector); 

Aiuta:

explain analyze SELECT * from vectors 
order by cube(ARRAY[966,82,765,343,600,718,338,505]) <#> vector asc limit 10; 

-------------------------------------------------------------------------------------------------------------------------------------------------- 
Limit (cost=0.41..1.93 rows=10 width=76) (actual time=41.339..143.915 rows=10 loops=1) 
    -> Index Scan using vectors_vector_idx on vectors (cost=0.41..393704.41 rows=2600000 width=76) (actual time=41.336..143.902 rows=10 loops=1) 
     Order By: (vector <#> '(966, 82, 765, 343, 600, 718, 338, 505)'::cube) 
Planning time: 0.146 ms 
Execution time: 145.474 ms 
(5 rows) 

A 8 dimensioni, aiuta.

Answer 2

(Addendum alla risposta selezionata)

Per le persone che vogliono più di 100 dimensioni, attenzione: c'è a 100 dimensions limit in cube extension.

La parte difficile è che postgres consente di creare cubi con più di 100 dimensioni. È quando si tenta di ripristinare un backup che viene rifiutato (il momento peggiore per rendersene conto).

Come consigliato nella documentazione, ho applicato un'estensione del cubo per supportare più dimensioni. Ho creato un'immagine docker per questo, e puoi guardare il Dockerfile per vedere come farlo da solo, dal github repos.