Schnelle Suche nach dem nächsten Nachbarn im 150-dimensionalen Raum

12

Ich möchte eine Datenbank mit einem der möglichen RDBMS erstellen. Es wird eine Tabelle mit ungefähr 150 Spalten haben. Das Ziel besteht darin, die Suche nach dem nächsten Nachbarn einiger anderer Objekte durchzuführen. Es ist also ein NNS im 150-dimensionalen Raum.

Ich habe bereits versucht, einige offensichtliche Methoden wie L1- oder L2-Abstände zu verwenden, aber für Tabellen mit vielen Zeilen dauert es natürlich viel Zeit. Ich habe auch versucht, den KD-Baum (beachten Sie, dass ich ihn nicht getestet habe) und PG-Strom zu betrachten, aber sie sind keine gute Lösung für Daten mit vielen Dimensionen.

Kann ich die Geschwindigkeit der beschriebenen Suche mithilfe von mathematischen Methoden (wie KD-Tree) oder technischen Methoden (wie PG-Strom) irgendwie verbessern?

Ich werde versuchen, jedes RDBMS zu verwenden, mit dem die Geschwindigkeit des NNS verbessert werden kann. Aber MySQL und PostgreSQL sind für mich das am besten geeignete DBMS.

database-design performance nearest-neighbor Don-Prog
quelle
1
Dies sind andere Probleme. Stellen Sie einfach eine andere Frage @ don-prog
Evan Carroll

Antworten:

15

PostgreSQL 9.6 mit cube

Installieren Sie zuerst die Cube-Erweiterung

CREATE EXTENSION cube;

Jetzt werden wir einen n-dimensionalen Raum mit 100.000 Punkten in 50 Dimensionen erstellen. Zusätzlich fügen wir einen GIST-Index hinzu.

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;

Jetzt werden wir einen einzelnen Punkt erzeugen und den <->Operator verwenden, um den nächsten Punkt unter Verwendung der eukledianischen Entfernung zu finden.

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+ unterstützt andere Entfernungsoperatoren über cube. Alle können den von uns erstellten GIST-Index verwenden. Nämlich,

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.

Das heißt, es gibt eine Einschränkung,

Um es den Menschen zu erschweren, Dinge zu zerbrechen, ist die Anzahl der Dimensionen von Würfeln auf 100 begrenzt. Dies wird in cubedata.h festgelegt, wenn Sie etwas Größeres benötigen.

Sie fragen nach 150 Dimensionen. Dies kann eine geringfügige Komplikation darstellen.

Evan Carroll
quelle
1
Die Bearbeitung cubedata.hfunktioniert nach meiner Erfahrung nicht über 130 Dimensionen hinaus. Möglicherweise können Sie auch alle doubles oder float8s in der Erweiterung in ändern float4, da Postgres eine Beschränkung für die Indexgröße pro Zeile hat, die Sie vermeiden können, indem Sie die Anzahl der für jede Zahl verwendeten Bytes halbieren. Ich habe einige Tests durchgeführt und auf diese Weise mehr Dimensionen erhalten, und IIRC habe ich über 150 erreicht, bin mir aber nicht ganz sicher.
Sudo
Ich hatte das gleiche Problem mit der Begrenzung der Abmessungen und erstellte ein Docker-Image mit der Begrenzung 2048: hub.docker.com/r/expert/postgresql-large-cube
Experte
2

Ziehen Sie zunächst eine Dimensionsreduzierung in Betracht (z. B. Prinzipielle Komponentenanalyse).

Dann machen Sie NN in einer kleinen Anzahl von Dimensionen mit höherer Leistung.

Sie können Pl / R verwenden, um bei Bedarf eine PCA in Postgres durchzuführen.

Robin Chauhan
quelle
0

Schauen Sie sich https://github.com/a-mma/AquilaDB an. Es handelt sich um eine Vektordatenbank zum Speichern von Feature-Vektoren zusammen mit JSON-Metadaten. Behalten Sie es zusammen mit Ihrem RDBMS bei und verwenden Sie Metadaten, um den Querverweis zwischen Daten aufrechtzuerhalten.

a_ മ്മ
quelle