Chcę utworzyć bazę danych przy użyciu dowolnego z możliwych RDBMS. Będzie miał tabelę z około 150 kolumnami. Celem jest przeszukanie najbliższych sąsiadów niektórych innych obiektów. Jest to więc NNS w 150-wymiarowej przestrzeni.

Próbowałem już użyć oczywistych metod, takich jak odległości L1 lub L2, ale oczywiście zajmuje dużo czasu dla tabel z wieloma wierszami. Próbowałem też spojrzeć na drzewo KD (uwaga, że ​​go nie testowałem) i PG-Strom, ale nie są one dobrym rozwiązaniem dla danych o wielu wymiarach.

Czy mogę w jakiś sposób poprawić szybkość opisywanego wyszukiwania za pomocą metod matematycznych (takich jak drzewo KD) lub metod technicznych (takich jak PG-Strom)?

Spróbuję użyć dowolnego RDBMS, który pozwoli poprawić prędkość NNS. Ale MySQL i PostgreSQL są dla mnie najbardziej odpowiednim DBMS.

Korzystanie z PostgreSQL 9.6 cube

Najpierw zainstaluj rozszerzenie kostki

CREATE EXTENSION cube;

Teraz stworzymy n-wymiarową przestrzeń z 100 000 punktów w 50 wymiarach. Dodatkowo dodamy 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;

Teraz wygenerujemy pojedynczy punkt i użyjemy <->operatora, aby znaleźć najbliższy punkt na podstawie odległości eukledowskiej.

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+ obsługuje innych operatorów odległości cube. Wszystkie z nich mogą korzystać z utworzonego przez nas indeksu GIST. Mianowicie,

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.

Powiedział, że jest jedno zastrzeżenie,

Aby utrudnić ludziom łamanie przedmiotów, obowiązuje limit 100 wymiarów kostek. Jest to ustawione w cubedata.h, jeśli potrzebujesz czegoś większego.

Pytasz o 150 wymiarów. Może to stanowić drobną komplikację.

Rozważ najpierw wykonanie redukcji wymiarów (np. Analiza zasad składowych).

Więc robisz NN w niewielkiej liczbie wymiarów z wyższą wydajnością.

W razie potrzeby można użyć Pl / R do wykonania PCA wewnątrz postgresu.

Spójrz na FLANN i OpenCV .

Niestety nie jestem świadom integracji tego systemu z systemem RDBMS. Ale istnieje na przykład integracja informacji o strukturze chemicznej z Posgres. Zasadniczo można to zrobić.

Spójrz na https://github.com/a-mma/AquilaDB jest to wektorowa baza danych do przechowywania wektorów cech wraz z metadanymi JSON. Zachowaj go wraz z RDBMS i używaj metadanych, aby zachować odniesienie między danymi.