多次元キューブ上のPostgresql k-nearest neighbor（KNN）

Question

私は8次元のキューブを持っています。私は最近隣のマッチングをしたい。私はpostgresqlに全く新しいです。私は、9.1がマルチディメンションで最も近いネイバーマッチングをサポートしていることを読んでいます。

1. 8Dキューブでテーブルを作成するにはどうすればいいですか？正確な

2. 検索に一致 - -

3. サンプルが

4. ルック挿入

サンプルデータを照合最近傍：簡単のため

を、私たちはそのすべての前提とすることができます値の範囲は0〜100です。

にPoint1：（1,1,1,1、1,1,1,1）

ポイント2：（2,2,2,2、2,2,2,2）

ルックアップ値：（1,1,1,1,1,1,2）

これは、Point1ではなくPoint2と一致する必要があります。

参考文献：

What's_new_in_PostgreSQL_9.1

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

Answer 1

PostgreSQLは距離オペレータ<->をサポートし、私はそれを理解するように、これは（pg_trgrmモジュールと）テキストとgeometryデータ型を分析するために使用することができます。

1次元以上でどのように使用できるかわかりません。たぶん、独自の距離関数を定義するか、何らかの形でデータをテキストまたはジオメトリタイプの1つの列に変換する必要があります。たとえば、あなたが8列（8次元立方体）を持つテーブルがある場合：1列を持つ表に、その後

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

そして：

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

をあなたはそれを変換することができます

c1 
abababac 

は、その後、（gistindexを作成した後に）使用することができます。

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

全8つの寸法が保存されているの

例

作成したサンプルデータ

-- 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) 
); 

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 
); 

をテキストに入力されたデータを変換する。これは、あなたに1つの変数trans_variableを与える：

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 

代わりに、あなたはまた、次の構文（短いが、より多くの不可解な）を使用することができます||オペレータの：私はから1行を選択した：

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

インデックス

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

テスト距離 メモの追加テーブル52;42;18;50;68;29;8;55 - を使用し、わずかに変更された値（42;42;18;52;98;29;8;55）を使用して距離をテストしました。もちろん、ランダム・マトリックスなので、テスト・データにはまったく異なる値があります。

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'; 

距離演算子< - >または類似関数を使用できます。距離= 1 - 類似性

Answer 2

"patch that introduces kNN search for cubes with euclidean, taxicab and chebyshev distances"は、最近、pgsql-hackersリストで提供されました。 PostgreSQLのビルドをカスタマイズすることができれば、あなたの目的に合うかもしれません。

PostgreSQLの拡張であるcubeタイプを使用して、n次元の点または立方体を表すことができます。 （デフォルトではnの値は100まで増やすことができますが、cubedata.hの場合はさらに多くなります）。このパッチは、インデックスアシスト多次元ポイント/ベクトル/キューブ最近傍探索を有効にする必要があります。

（このパッチがないと、cubeタイプは<->距離演算子を持っていない、とサポート機能（＃8）が主旨に距離関連の指標のを作る能力を与えるために必要とされるOPERATOR CLASS gist_cube_opsから欠落していますこれらの値。

私はまだパッチを試していないし、ディスカッションリストの回答の1つでは、現在、いくつかの回帰テストが中断されている可能性があることに注意してください。