Hay algunos problemas que hacen que sus requisitos sean complejos, por lo que los abordaré uno a la vez:
Primero, aunque los árboles kd son el algoritmo canónico para la indexación de alta dimensionalidad, no se pueden fragmentar de manera eficiente en una gran cantidad de máquinas. Para un clúster pequeño, puede hacer que funcione si la tasa de actualización es muy baja.
En segundo lugar, si el conjunto de datos es muy grande y está fragmentado en muchas máquinas, necesitará usar una estructura de datos de descomposición espacial, que no es un árbol kd. Todas las estructuras de descomposición espacial en la literatura, como el árbol cuádruple, solo son útiles en espacios con buena distribución sobre los bits más significativos de las dimensiones individuales. Las estructuras de descomposición espacial no tienen dimensionalidad intrínseca, la dimensionalidad es una interpretación (ver: números de Morton), por lo que podría almacenar un modelo de 1000 dimensiones en un árbol cuádruple en principio, aunque un árbol cuádruple tenga un árbol de decisión de baja dimensionalidad.
- Cómo construir robots enjambre
- ¿Cómo uso vectores para una matriz 2D en C ++?
- ¿Cuál es el mejor enfoque para resolver el problema que CRYPTO preguntó en el concurso de codificación PRAVEGA 2014 celebrado en Codechef el 9 de noviembre?
- ¿Se puede usar la GPU para optimizar los algoritmos gráficos?
- ¿Qué es la compresión de datos en la base de datos?
El mayor problema es que pocos modelos de datos con miles de dimensiones tienen una buena distribución de valores en sus dimensiones. Una propiedad de las estructuras de descomposición espacial es que existe una relación profunda entre la similitud de la estructura de registros y el árbol de decisión que le permite direccionar el contenido de la ubicación de almacenamiento de registros. Si la mayoría de sus miles de dimensiones tienen una distribución de valor deficiente, de modo que existe una gran similitud récord en algunas dimensiones, la estructura distribuida tendrá una forma fea e ineficiente. He visto (y he usado) estructuras de datos de descomposición espacial hiperdimensionales que son asimétricas adaptativas, pero actualmente no hay ninguna en la literatura que sepa que pueda señalar.
Dada la forma en que ha descrito su caso problemático, e ignorando los algoritmos que no están actualmente en la literatura, sugeriría diseñar un algoritmo híbrido que se base en la descomposición del espacio en las primeras partes del método de acceso y cambiar a una estructura de árbol kd localmente. Hay muchos detalles y advertencias sobre cómo funcionaría, pero debería ser capaz de adaptarse a su caso de uso, requisitos de rendimiento y modelo de datos.
