Szybkie wyszukiwanie najbliższego sąsiada w 150-wymiarowej przestrzeni

13

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.

database-design performance nearest-neighbor don-prog
źródło
1
To są inne problemy. Wystarczy zadać kolejne pytanie @ don-prog
Evan Carroll,

Odpowiedzi:

17

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ę.

Evan Carroll
źródło
1
Z cubedata.hmojego doświadczenia wynika, że edycja do nie działa poza 130 wymiarami. Być może możesz również zmienić wszystkie doubles lub float8s rozszerzenia float4, ponieważ Postgres ma limit wielkości indeksu na wiersz, od którego możesz się trzymać, zmniejszając o połowę liczbę bajtów używanych na każdej liczbie. Przeprowadziłem testy i uzyskałem w ten sposób więcej wymiarów, a IIRC przekroczyłem 150, ale nie jestem do końca pewien.
sudo
Miałem ten sam problem z ograniczeniem wymiarów i utworzyłem obraz dokera
ekspert
2

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.

Robin Chauhan
źródło
0

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.

a_ മ്മ
źródło