Búsqueda rápida de vecinos más cercanos en el espacio de 150 dimensiones

13

Quiero crear una base de datos usando cualquiera de los posibles RDBMS. Tendrá una tabla con aproximadamente 150 columnas. El objetivo es realizar la búsqueda de vecinos más cercanos de algunos otros objetos. Entonces es un NNS en el espacio de 150 dimensiones.

Ya intenté usar algunos métodos obvios como las distancias L1 o L2, pero, por supuesto, lleva mucho tiempo para las tablas con muchas filas. También traté de mirar el árbol KD (tenga en cuenta que no lo probé) y PG-Strom, pero no son una buena solución para los datos con muchas dimensiones.

¿De alguna manera puedo mejorar la velocidad de la búsqueda descrita utilizando métodos matemáticos (como KD-tree) o métodos tecnológicos (como PG-Strom)?

Intentaré usar cualquier RDBMS que permita mejorar la velocidad del NNS. Pero MySQL y PostgreSQL son los DBMS más apropiados para mí.

database-design performance nearest-neighbor don-prog
fuente
1
Estos son otros problemas. Simplemente haga otra pregunta @ don-prog
Evan Carroll

Respuestas:

17

PostgreSQL 9.6 usando cube

Primero instale la extensión del cubo

CREATE EXTENSION cube;

Ahora crearemos un espacio n-dimensional con 100,000 puntos en 50 dimensiones. Además, agregaremos un índice 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;

Ahora generaremos un solo punto y usaremos el <->operador para encontrar el punto más cercano usando la distancia euclediana.

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+ es compatible con otros operadores de distancia cube. Todo lo cual puede usar el índice GIST que creamos. A saber,

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.

Dicho esto, hay una advertencia:

Para dificultar que las personas rompan cosas, hay un límite de 100 en el número de dimensiones de los cubos. Esto se establece en cubedata.h si necesita algo más grande.

Pides 150 dimensiones. Eso puede presentar una complicación menor.

Evan Carroll
fuente
1
La edición a cubedata.hno funciona más allá de 130 dimensiones en mi experiencia. Tal vez también pueda cambiar todos los doubles o float8s en la extensión float4, ya que Postgres tiene un límite en el tamaño del índice por fila del que puede alejarse reduciendo a la mitad la cantidad de bytes que usa en cada número. Hice algunas pruebas y obtuve más dimensiones de esa manera, y IIRC superé 150, pero no estoy totalmente seguro.
sudo
Tuve el mismo problema con el límite de dimensiones y creé la imagen de Docker
experto
2

Considere realizar primero la reducción de dimensiones (p. Ej., Análisis de componentes principales).

Entonces estás haciendo NN en un pequeño número de dimensiones con un mayor rendimiento.

Puede usar Pl / R para realizar PCA dentro de postgres si es necesario.

Robin Chauhan
fuente
0

Eche un vistazo a https://github.com/a-mma/AquilaDB , es una base de datos de vectores para almacenar vectores de características junto con metadatos JSON. Manténgalo junto con su RDBMS y use metadatos para mantener la referencia cruzada entre los datos.

a_ മ്മ
fuente