Postgresql k-nearest neighbor (KNN) sul cubo multidimensionale

Question

Ho un cubo con 8 dimensioni. Voglio fare la corrispondenza del vicino più prossimo. Sono totalmente nuovo a postgresql. Ho letto che 9.1 supporta il prossimo più prossimo che corrisponde alle multidimensioni. Apprezzerei molto se qualcuno potesse fornire un esempio completo:

1. Come creare un tavolo con il cubo 8D?

2. Esempio Inserire

3. Lookup - corrispondenza esatta

4. Lookup - vicino più prossimo corrispondenza

dati di esempio:

Per semplicità, si può supporre che tutte le i valori vanno da 0 a 100.

Point1: (1,1,1,1, 1,1,1,1)

Point2: (2,2,2,2, 2,2,2,2)

Valore di ricerca: (1,1,1,1, 1,1,1,2)

Questo deve corrispondere a Punto1 e non a Punto2.

Refs:

What's_new_in_PostgreSQL_9.1

https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search

Answer 1

PostgreSQL supporta operatore distanza <-> e se ho capito bene, questo può essere utilizzato per l'analisi del testo (con modulo pg_trgrm) e geometry tipo di dati.

Non so come si può usare con più di 1 dimensione. Forse dovrai definire la tua funzione di distanza o in qualche modo convertire i tuoi dati in una colonna con testo o tipo di geometria.Per esempio, se si dispone di tavolo con 8 colonne (cubo 8-dimensionale):

c1 c2 c3 c4 c5 c6 c7 c8 
1 0 1 0 1 0 1 2 

È possibile convertirlo in:

c1 c2 c3 c4 c5 c6 c7 c8 
a b a b a b a c 

E poi a tavola con una colonna:

c1 
abababac 

Quindi è possibile utilizzare (dopo aver creato gistindex):

SELECT c1, c1 <-> 'ababab' 
FROM test_trgm 
ORDER BY c1 <-> 'ababab'; 

Esempio

Creare dati campione

-- Create some temporary data 
-- ! Note that table are created in tmp schema (change sql to your scheme) and deleted if exists ! 
drop table if exists tmp.test_data; 

-- Random integer matrix 100*8 
create table tmp.test_data as (
    select 
     trunc(random()*100)::int as input_variable_1, 
     trunc(random()*100)::int as input_variable_2, 
     trunc(random()*100)::int as input_variable_3, 
     trunc(random()*100)::int as input_variable_4, 
     trunc(random()*100)::int as input_variable_5, 
     trunc(random()*100)::int as input_variable_6, 
     trunc(random()*100)::int as input_variable_7, 
     trunc(random()*100)::int as input_variable_8 
    from 
     generate_series(1,100,1) 
); 

trasformare i dati di input in testo

drop table if exists tmp.test_data_trans; 

create table tmp.test_data_trans as (
select 
    input_variable_1 || ';' || 
    input_variable_2 || ';' || 
    input_variable_3 || ';' || 
    input_variable_4 || ';' || 
    input_variable_5 || ';' || 
    input_variable_6 || ';' || 
    input_variable_7 || ';' || 
    input_variable_8 as trans_variable 
from 
    tmp.test_data 
); 

Questo vi darà una variabile trans_variable cui sono memorizzati tutti i 8 dimensioni:

trans_variable 
40;88;68;29;19;54;40;90 
80;49;56;57;42;36;50;68 
29;13;63;33;0;18;52;77 
44;68;18;81;28;24;20;89 
80;62;20;49;4;87;54;18 
35;37;32;25;8;13;42;54 
8;58;3;42;37;1;41;49 
70;1;28;18;47;78;8;17 

.210

Invece di || dell'operatore è anche possibile utilizzare la seguente sintassi (più breve, ma più criptico):

select 
    array_to_string(string_to_array(t.*::text,''),'') as trans_variable 
from 
    tmp.test_data t 

Aggiungi indice

create index test_data_gist_index on tmp.test_data_trans using gist(trans_variable); 

distanza di prova Nota: ho selezionato una riga da tabella - 52;42;18;50;68;29;8;55 - e ha utilizzato un valore leggermente modificato (42;42;18;52;98;29;8;55) per verificare la distanza. Ovviamente, i valori dei test avranno valori completamente diversi, poiché si tratta di una matrice RANDOM.

select 
    *, 
    trans_variable <-> '42;42;18;52;98;29;8;55' as distance, 
    similarity(trans_variable, '42;42;18;52;98;29;8;55') as similarity, 
from 
    tmp.test_data_trans 
order by 
    trans_variable <-> '52;42;18;50;68;29;8;55'; 

È possibile utilizzare l'operatore di distanza < -> o la funzione di similitudine. Distanza = 1 - Somiglianza

Answer 2

Un "patch that introduces kNN search for cubes with euclidean, taxicab and chebyshev distances" è stato recentemente offerto nell'elenco pgsql-hackers. Potrebbe funzionare per il tuo scopo, se puoi personalizzare la build di PostgreSQL.

Si noti che il tipo , un'estensione PostgreSQL, può essere utilizzato per rappresentare punti o cubi in n-dimensioni. (Il valore di n può salire fino a 100 per impostazione predefinita, di più se viene sollevato un limite in cubedata.h.) Quindi questa patch dovrebbe, tra le altre cose, abilitare la ricerca multidimensionale point/vector/cube next-neighbor.

(Senza questa patch, il tipo cube non ha un operatore <-> distanza, e una funzione di supporto (# 8) manca dal OPERATOR CLASS gist_cube_ops che è necessario per dare sostanza la capacità di fare un indice di distanza correlata on questi valori.)

Non ho ancora provato la patch e noto che una delle risposte dell'elenco di discussione suggerisce che al momento potrebbe interrompere alcuni test di regressione.