Pencarian tetangga terdekat yang cepat di ruang 150 dimensi

13

Saya ingin membuat database menggunakan RDBMS yang ada. Ini akan memiliki tabel dengan sekitar 150 kolom. Tujuannya adalah untuk melakukan pencarian tetangga terdekat dari beberapa objek lain. Jadi itu adalah NNS dalam ruang 150 dimensi.

Saya sudah mencoba menggunakan beberapa metode yang jelas seperti jarak L1 atau L2 tapi tentu saja butuh banyak waktu untuk tabel dengan banyak baris. Saya juga mencoba melihat pada KD-tree (perhatikan saya tidak mengujinya) dan PG-Strom tetapi mereka bukan solusi yang baik untuk data dengan banyak dimensi.

Bisakah saya meningkatkan kecepatan pencarian yang dijelaskan menggunakan metode matematika (seperti KD-tree) atau metode teknologi (seperti PG-Strom)?

Saya akan mencoba menggunakan RDBMS yang memungkinkan untuk meningkatkan kecepatan NNS. Tetapi MySQL dan PostgreSQL adalah DBMS yang paling tepat untuk saya.

database-design performance nearest-neighbor don-prog
sumber
1
Ini adalah masalah lain. Cukup ajukan pertanyaan lain @ don-prog
Evan Carroll

Jawaban:

17

PostgreSQL 9.6 menggunakan cube

Pertama instal ekstensi kubus

CREATE EXTENSION cube;

Sekarang kita akan membuat beberapa ruang n-dimensi dengan 100.000 poin dalam 50 dimensi. Selain itu kami akan menambahkan indeks GIST.

CREATE TEMP TABLE space_nd
AS
  SELECT i, cube(array_agg(random()::float)) AS c
  FROM generate_series(1,1e5) AS i
  CROSS JOIN LATERAL generate_series(1,50)
    AS x
  GROUP BY i;

CREATE INDEX ON space_nd USING gist ( c );
ANALYZE space_nd;

Sekarang kita akan menghasilkan satu titik dan menggunakan <->operater untuk menemukan titik terdekat menggunakan jarak Eucledian.

WITH points AS (
  SELECT cube(array_agg(random()::float)) AS c
  FROM generate_series(1,50)
    AS x
)
SELECT i,
  pg_typeof(space_nd.c),
  pg_typeof(points.c),
  cube_distance(space_nd.c, points.c)
FROM space_nd
CROSS JOIN points
ORDER BY space_nd.c <-> points.c
LIMIT 5;

PostgreSQL 9.6+ mendukung operator jarak jauh lainnya cube. Semuanya dapat menggunakan indeks GIST yang kami buat. Yaitu,

a <-> b float8  Euclidean distance between a and b.
a <#> b float8  Taxicab (L-1 metric) distance between a and b.
a <=> b float8  Chebyshev (L-inf metric) distance between a and b.

Yang mengatakan ada satu peringatan,

Untuk mempersulit orang memecahkan barang, ada batas 100 pada jumlah dimensi kubus. Ini diatur dalam cubedata.h jika Anda membutuhkan sesuatu yang lebih besar.

Anda meminta 150 dimensi. Itu mungkin menimbulkan komplikasi kecil.

Evan Carroll
sumber
1
Hasil edit untuk cubedata.htidak berfungsi melebihi 130 dimensi dalam pengalaman saya. Mungkin Anda juga dapat mengubah semua doubles atau float8s di ekstensi float4, karena Postgres memiliki batasan ukuran indeks per baris yang dapat Anda hindari dengan membagi dua byte yang Anda gunakan pada setiap angka. Saya melakukan beberapa pengujian dan mendapatkan lebih banyak dimensi dengan cara itu, dan IIRC saya melewati 150, tapi saya tidak sepenuhnya yakin.
sudo
Saya memiliki masalah yang sama dengan batas dimensi dan membuat gambar buruh pelabuhan dengan batas 2048: hub.docker.com/r/expert/postgresql-large-cube
expert
2

Pertimbangkan untuk melakukan pengurangan dimensi terlebih dahulu (mis. Analisis Komponen Utama).

Maka Anda melakukan NN dalam sejumlah kecil dimensi dengan kinerja yang lebih tinggi.

Anda dapat menggunakan Pl / R untuk melakukan PCA di dalam postgres jika perlu.

Robin Chauhan
sumber
0

Lihatlah https://github.com/a-mma/AquilaDB, ini adalah basis data vektor untuk menyimpan Vektor Fitur bersama dengan JSON Metadata. Tetap ikuti RDBMS Anda dan gunakan metadata untuk mempertahankan referensi silang antara data.

a_ മ്മ
sumber