En un sector donde la escalabilidad y la trazabilidad son esenciales, Tilores ha dado un paso significativo al abordar uno de los mayores retos de los sistemas de resolución de entidades (Entity Resolution, ER): el almacenamiento eficiente de relaciones entre registros. En un artículo técnico publicado por Stefan Berkner, Tilores detalla cómo ha implementado un innovador modelo de compresión de grafos basada en cliques (CBGC) que permite reducir hasta un 99,7 % el volumen de datos de relaciones almacenadas, sin perder información relevante.
Entidades como grafos: flexibilidad y trazabilidad, pero con costes
Tilores modela las entidades como grafos, donde cada nodo representa un registro y cada arista indica que dos registros coinciden según una regla definida. Este enfoque garantiza trazabilidad completa, ya que se pueden conservar todas las reglas aplicadas a cada emparejamiento.
Este nivel de detalle ofrece ventajas cruciales:
- Auditoría y explicabilidad: se puede rastrear cómo se formó una entidad.
- Analítica de calidad de datos: permite evaluar la efectividad de reglas de emparejamiento.
- Reprocesamiento ágil: facilita el recalculo si se eliminan registros o modifican reglas.
Sin embargo, este modelo conlleva un problema: el número de aristas crece de forma cuadrática con el número de registros por entidad. Para una entidad de 1.000 registros, se podrían generar hasta 499.500 conexiones, lo que supone una carga crítica de almacenamiento y procesamiento.
La solución: compresión de grafos mediante cliques (CBGC)
Para reducir este impacto, Tilores ha adoptado un método inspirado en la teoría de grafos: detectar cliques —subgrafos completamente conectados— y almacenarlos como una sola estructura compacta.
Un clique de tamaño n contiene todas las conexiones posibles entre sus nodos, representadas por la fórmula n(n-1)/2. En lugar de guardar cada una de esas conexiones, CBGC permite almacenar simplemente los nodos que forman la clique y el identificador de la regla que los une.
En ejemplos reales, Tilores ha podido reemplazar decenas de miles de aristas con solo unas pocas centenas de cliques y aristas sueltas. Esto ha resultado en reducciones del 99,7 % en el almacenamiento de relaciones en uno de sus clientes.
Ventajas adicionales de CBGC
Más allá de la compresión, el uso de cliques mejora el rendimiento en operaciones comunes de ER:
- Eliminación eficiente de registros: en caso de cumplir con normativas como el derecho al olvido, el sistema puede dividir entidades rápidamente si detecta subgrafos desconectados.
- Reprocesamiento optimizado: con menos aristas que revisar, los algoritmos de componentes conectados trabajan con mayor velocidad.
- Escalabilidad real: permite trabajar con millones de registros sin que el sistema se vea comprometido por la densidad de las relaciones.
¿Cuál es el truco? La detección de cliques
Encontrar cliques máximos en un grafo es un problema NP-hard, es decir, computacionalmente complejo. Sin embargo, Tilores evita esta barrera mediante:
- Heurísticas aproximadas: algoritmos greedy que identifican cliques grandes sin ser óptimos.
- Compresión selectiva: CBGC solo se recalcula si una entidad supera un umbral de aristas.
Este enfoque híbrido equilibra eficiencia de compresión con coste de cálculo aceptable, permitiendo aplicarlo a gran escala sin comprometer la estabilidad.
Más allá de los cliques: otras formas de compresión
Aunque el patrón más frecuente en ER es el subgrafo completo, Tilores también estudia otras estructuras repetitivas que podrían representar relaciones de forma más compacta:
- Estrellas: todos los nodos conectados a un nodo central.
- Caminos: listas ordenadas de nodos conectados secuencialmente.
- Comunidades: cliques incompletas donde se marcan las aristas ausentes.
Estos patrones adicionales podrían mejorar aún más la eficiencia y abrir nuevas posibilidades para modelar relaciones complejas.
Conclusión
La compresión de grafos basada en cliques representa un cambio de paradigma en la resolución de entidades. Frente a un enfoque tradicional que almacena cada relación de forma explícita, Tilores demuestra que es posible mantener trazabilidad total, mejorar el rendimiento y reducir radicalmente el uso de almacenamiento.
Este avance es especialmente relevante en un contexto de exigencias crecientes sobre el control de datos, la privacidad y la capacidad de escalar sistemas de gestión de identidades, datos maestros y conocimiento de clientes. Gracias a CBGC, la resolución de entidades se vuelve más ligera, rápida y transparente.
🧠 Artículo técnico por Stefan Berkner: Efficient Graph Storage for Entity Resolution Using Clique-Based Compression (Tilores Blog, 2025)
Fuente: tilores.io
