Propuesta de Proyecto de Titulación
Una propuesta de investigación y desarrollo para evaluar Cola de Prioridad y Radio Incremental sobre una estructura compacta, con foco en rendimiento, memoria y viabilidad técnica.
Apoyo Visual
Estas imágenes vienen del material del informe y cubren tres ideas clave: la estructura espacial, la codificación compacta y la consulta de rango que sirve como antecedente para KNN.
%20and%20(11,5).jpg)
Conceptos Fundamentales
Definiciones de términos clave para entender la propuesta:
Algoritmo que dado un punto de consulta, encuentra los K puntos más cercanos en un conjunto de datos. Fundamental en aprendizaje automático, recomendaciones y clasificación. Ejemplo: "Encuentra los 5 clientes más similares a este perfil".
Estructura de árbol binario que particiona espacios multidimensionales recursivamente. Cada nodo divide un eje de coordenadas alternadamente (X, Y, Z...). Permite búsquedas rápidas en espacios de múltiples dimensiones, pero usa mucha memoria en punteros.
Versión compacta del Kd-tree que elimina punteros usando codificación implícita. Reduce memoria a ~30% del Kd-tree clásico manteniendo capacidad de consulta. Usa secuencias en espiral (curva de Hilbert) y códigos de acceso directo (DACs).
Algoritmo de búsqueda que mantiene una cola ordenada de candidatos. Explora primero las regiones más prometedoras (cercanas al punto de consulta). Rápido pero requiere memoria adicional para la cola. Mayor overhead pero menos iteraciones.
Algoritmo que comienza con un radio de búsqueda pequeño alrededor del punto de consulta y lo expande gradualmente hasta encontrar K vecinos. Bajo overhead de memoria pero potencialmente más computación. Demostró ser superior en k²-tree (2023).
Otra estructura compacta que almacena relaciones binarias en espacios 2D usando codificación bit-a-bit. Antecedente directo de cKd-tree. Sus resultados de investigación (2021, 2023) sirven como referencia comparativa.
Técnica de codificación que permite calcular la posición de un elemento sin almacenar punteros explícitos. Usado en cKd-tree para navegar implícitamente la estructura. Requiere cálculos pero economiza RAM exponencialmente.
Secuencia matemática que mapea espacios multidimensionales a 1D mientras preserva localidad (puntos cercanos en el espacio original quedan cercanos en la secuencia). Utilizada en cKd-tree para codificar posiciones de nodos.
Retorna todos los puntos dentro de un rectángulo (o hipercubo) delimitado. Diferente de KNN: donde KNN devuelve exactamente K vecinos, rango devuelve TODOS los puntos en el área. cKd-tree implementa esto pero no KNN.
Enfoque de desarrollo que construye versiones funcionales incrementalmente, integrando retroalimentación rápidamente. Ideal para proyectos donde no se conoce todos los requisitos o hay alta incertidumbre técnica. Minimiza riesgo mediante iteración temprana.
Resumen
El cKd-tree surge como una alternativa compacta al Kd-tree clásico, pero todavía necesita validarse con consultas KNN sobre escenarios más reales y comparaciones con algoritmos de búsqueda estándar.
Estudiante
Ingeniería en Ejecución en Computación e Informática
Área
Búsqueda espacial, eficiencia y uso de memoria
Problemática
El cKd-tree es una estructura recientemente desarrollada (2024) que logra comprimir índices Kd-tree con ratios de compresión cercanos al 70% respecto de otras estructuras compactas, manteniendo capacidad de consulta. Sin embargo, enfrenta limitaciones críticas que impiden su adopción operativa:
La estructura actual solo implementa almacenamiento y consultas de rango (búsquedas que retornan todos los puntos dentro de un rectángulo delimitado). Sin embargo, carece de una implementación operativa de K-Vecinos más Cercanos (KNN), una funcionalidad esencial para aplicaciones reales como:
Impacto: Una estructura que solo almacena pero no permite consultar de manera eficiente es incompleta funcionalmente.
El cKd-tree logra reducción de memoria dramática (70% aprovechamiento) mediante:
Sin embargo, existe incertidumbre crítica: ¿Navegar una estructura sin punteros anula el ahorro de memoria?
Preguntas sin respuesta: ¿Cuántos ciclos de CPU se gastan en reconstrucción? ¿Hay dispositivos con RAM limitada donde cKd-tree es viable?
Existen dos estrategias clásicas para búsqueda KNN. No hay datos empíricos sobre cuál es superior en cKd-tree:
En k²-tree (2023), Radio Incremental demostró ser superior. Pero cKd-tree tiene una arquitectura diferente (partición celular vs. basada en bits), así que no hay garantía.
Consecuencia: Ingenieros no pueden tomar decisiones informadas. ¿Cuál algoritmo elegir? Depende de datos desconocidos.
Propuesta
Se propone implementar y comparar dos variantes de búsqueda KNN sobre cKd-tree: Cola de Prioridad y Radio Incremental. El resultado esperado es identificar cuál se adapta mejor a la estructura y ofrece mejor balance entre tiempo y memoria.
Objetivo general
Evaluar el rendimiento y la eficacia de las técnicas KNN de Radio Incremental y Colas de Prioridad implementadas sobre la estructura compacta cKd-tree.
Objetivos específicos
Justificación
La investigación sobre KNN en cKd-tree se justifica por razones académicas, técnicas y prácticas:
El trabajo fundacional del cKd-tree (2024) completó dos funcionalidades: almacenamiento compacto y consultas de rango. Pero esto es solo parte de la utilidad. Este proyecto extiende la funcionalidad hacia búsquedas de proximidad (KNN), transformando la estructura de un modelo teórico de almacenamiento a una herramienta de consulta prácticamente viable.
Consecuencia: cKd-tree pasa de ser "interesante" a ser "operacionalmente completo".
Las estructuras compactas ofrecen un tradeoff (compromiso) fundamental entre:
Este proyecto cuantifica experimentalmente:
Importancia: Valida si el compromiso teórico es realmente beneficioso en práctica.
Dos algoritmos KNN estándar compiten en estructuras compactas. Investigaciones previas muestran tendencias contradictorias:
| Algoritmo | k²-tree (2023) | iBit-tree | cKd-tree (DESCONOCIDO) |
| Cola de Prioridad | ✓ Rápido | ✓ Rápido | ? |
| Radio Incremental | ✓✓ Muy rápido | ✓ Competitivo | ? |
El problema: cKd-tree tiene una arquitectura única (partición celular con DACs) que no se mapea directamente a k²-tree (navegación bit-a-bit). Extrapolar resultados es arriesgado.
Beneficio: Este proyecto cierra la brecha de conocimiento, permitiendo a futuros desarrolladores elegir el algoritmo correcto desde el inicio.
Las estructuras de datos compactas son un área emergente crítica para:
Este proyecto contribuye metodología reproducible para validar estructuras compactas futuras.
Alcance: Los resultados y técnicas de benchmarking servirán para investigaciones posteriores en compresión de índices espaciales.
Metodología
La propuesta usa una metodología evolutiva porque permite construir versiones funcionales, probar temprano la lógica de búsqueda y ajustar el diseño según los resultados de cada iteración.
Complemento IEEE
El artículo base presenta cKd-tree como una estructura compacta para representar índices Kd-tree en escenarios de Big Data con conjuntos estáticos extensos, donde el objetivo principal es reducir memoria sin perder capacidad de consulta.
Síntesis elaborada con metadatos y resumen público indexado (OpenAlex/DBLP), ya que IEEE bloquea la descarga directa en este entorno.
Complemento IEEE II
Este artículo evalúa la aplicación del algoritmo de Radio Incremental para búsquedas KNN sobre la estructura compacta k²-tree, demostrando que supera al enfoque de Cola de Prioridad en escenarios con datos sintéticos y restricciones de memoria.
Investigación sobre algoritmos KNN en k²-tree, comparable con la presente propuesta en cKd-tree.
Plan de trabajo
Referencias base
Ref. 1: Base técnica
Autores: G. Gutiérrez, R. Torres-Avilés, M. Caniupán | Publicación: IEEE Access, vol. 12, pp. 28666–28676, 2024
Aportación central: Propone cKd-tree como estructura compacta que elimina punteros mediante codificación en espiral (DACs), logrando 70% de compresión respecto de k²-tree.
Relevancia para la propuesta: Es el trabajo fundacional sobre el cual esta propuesta construye. Establece la arquitectura celular y demuestra viabilidad de almacenamiento. Esta propuesta completa el ciclo implementando búsqueda KNN sobre esa arquitectura.
Ref. 2: Algoritmo precedente
Autor: Rodrigo Torres-Avilés | Publicación: Proc. 42nd IEEE Int. Conf. Chilean Computer Science Society (SCCC), pp. 1–4, 2023
Aportación central: Evalúa la implementación de Radio Incremental para KNN sobre k²-tree, demostrando que supera a Cola de Prioridad en estructuras compactas con restricciones de memoria.
Relevancia para la propuesta: Proporciona el precedente directo de comparación entre algoritmos KNN en estructuras compactas. Esta propuesta extiende esa comparativa específicamente a cKd-tree, validando si Radio Incremental mantiene su efectividad en una arquitectura de partición celular diferente.
Ref. 3: Marco algorítmico
Autores: Fernando Santolaya, Mónica Caniupán, Luis Gajardo, Miguel Romero, Rodrigo Torres-Avilés | Publicación: Theoretical Computer Science, vol. 892, pp. 108–131, Nov. 2021
Aportación central: Describe algoritmos KNN y K-Closest Pair Queries (KCPQ) sobre k²-tree, demostrando escalabilidad en memoria principal donde métodos de almacenamiento secundario fallan.
Relevancia para la propuesta: Proporciona el marco algorítmico de referencia para búsquedas de proximidad en estructuras compactas. Aunque opera sobre k²-tree (navegación basada en bits), sus lógicas de poda y expansión informan el diseño de algoritmos para cKd-tree (navegación basada en celdas), validando el enfoque comparativo.