6.4 Indexación

Las tablas de datos limpias y estandarizadas están listas para ser emparejadas. Inicialmente, cada registro de la tabla del censo necesita compararse con todos los registros de la tabla de la encuesta. Esto conduce a un número total de comparaciones de pares de registros que es cuadrático respecto al tamaño de las tablas de datos a emparejar. Por ejemplo, en nuestro ejercicio la tabla del censo tiene 97 registros y la tabla de la encuesta tiene 54 registros, así que sería necesario un total de 5238 comparaciones.

Por supuesto, esta comparación ingenua de todos los pares de registros no es escalable para datos muy grandes. Por ejemplo, el censo de Colombia en el año 2018 tuvo una enumeración de más de 44 millones de personas y usó una encuesta de cobertura de 283 mil personas, lo que originaría más de 12 billones de comparaciones de pares de registros. Incluso si se pudieran realizar 100 mil comparaciones por segundo, el proceso de comparación tomaría más de 33 mil horas, más de mil días, que equivale a casi 4 años.

Por lo anterior es necesario realizar una optimización del proceso usando técnicas de indexación (blocking) combinado con un proceso de procesamiento en paralelo y de ser posible sistemas distribuidos (como Apache Spark).

En las muestras de cobertura se usan segmentos muestrales equivalentes a los del censo, es decir, el código del segmento se refiere a la misma área geográfica, y en consecuencia es más probable que una persona que vive en el segmento 1 de la muestra de cobertura, también se encuentre en el segmento 1 del censo; así que comparar los pares de registros dentro del mismo segmento será la primera alternativa. Sin embargo, cuando el tiempo entre el censo y la encuesta de cobertura empieza a ser mayor, la probabilidad de que las personas se encuentren en el mismo segmento se reduce, esto debido a que las familias se pueden mudar y en ese caso el enfoque de bloqueo pierde el par porque están en segmentos diferentes, esto también ocurre con los moovers o personas que el día del censo no están en su lugar de residencia habitual. Otros ejemplos más complejos pueden darse cuando una mujer se ha casado y cambia su apellido y dirección, y por lo tanto no es detectada por los criterios de bloqueo y tampoco se detectaría en la comparación completa.

En este sentido, del censo se extrae la muestra de enumeración (muestra E) que corresponde a todos los hogares que están en los mismos segmentos de la encuesta de cobertura (muestra P), y de esta forma iniciar el proceso de emparejamiento con estos dos conjuntos de datos.

Sea \(n_0\) el tamaño de la muestra de la encuesta de cobertura, \(N_{+1}\) la cantidad de personas enumeradas en el censo y \(n_E\) la cantidad de personas enumeradas en la muestra E. Los pasos de la indexación son:

Realizar el emparejamiento entre la muestra E y la muestra P. Suponga que \(C^{(1)}\) es el conjunto de personas emparejadas en este paso, donde \(n_1<n_0\) es la cantidad de personas emparejadas, entonces \(P^{(1)}\) es el conjunto de personas de la muestra P que no fueron emparejadas y \(m_1 = n_0 - n_1\) es la cantidad de personas que no fueron emparejadas en este paso.
Sea \(M^{(2)}\) la muestra de segmentos en un área más grande alrededor de cada segmento de la muestra \(P\), esto para generar los nuevos bloques de indexación, es decir, si el segmento de la muestra \(P\) es una manzana cartográfica entonces el bloque podría ampliarse a una sección cartográfica o barrio para generar una búsqueda en un área mayor pero sin que se desborde la cantidad de comparaciones.
Sea \(E_2 = M^{(2)} - C^{(1)}\) la muestra de enumeración en un área más grande luego de retirar los elementos que ya fueron emparejados.
Realizar el emparejamiento entre la muestra \(E_2\) y la muestra \(P^{(1)}\). Suponga que \(C^{(2)}\) es el conjunto de personas emparejadas en este paso, donde \(n_2<m_1\) es la cantidad de personas emparejadas, entonces \(P^{(2)}\) es el conjunto de personas de la muestra \(P^{(1)}\) que no fueron emparejadas y \(m_2 = m_1 - n_2\) es la cantidad de personas que no fueron emparejadas en este paso.
Sea \(M^{(3)}\) la muestra de segmentos en un área más grande alrededor de cada bloque usado en \(M^{(2)}\), es decir, si en el paso anterior el bloque se amplió a una sección cartográfica entonces ahora se puede ampliar a un sector censal o si era el barrio entonces ampliarlo a una zona catastral más grande, y así generar una búsqueda en un área mayor pero sin que se desborde la cantidad de comparaciones.
Sea \(E_3 = M^{(3)} - \bigcup_{i=1}^2C^{(i)}\) la muestra de enumeración en un área más grande luego de retirar los elementos que ya fueron emparejados.
Realizar el emparejamiento entre la muestra \(E_3\) y la muestra \(P^{(2)}\). Ahora \(C^{(3)}\) es el conjunto de personas emparejadas en este paso, donde \(n_3<m_2\) es la cantidad de personas emparejadas, entonces \(P^{(3)}\) es el conjunto de personas de la muestra \(P^{(2)}\) que no fueron emparejadas y \(m_3 = m_2 - n_3\) es la cantidad de personas que no fueron emparejadas en este paso.
Continuar el procedimiento hasta que \(M^{(j)}\) sea igual al censo o hasta que \(m_j=0\), es decir, que no hay elementos sin emparejar.