UNIVERSIDAD COMPLUTENSE DE MADRID
FACULTAD DE CIENCIAS MATEM ´
ATICAS
DEPARTAMENTO DE SISTEMAS INFORM´
ATICOS Y COMPUTACI ´
ON
TRABAJO DE FIN DE GRADO
En i y Resolu ion y Deduplica ion con Blocking pa alelo en Spa k
En i y Resolu ion and Deduplica ion wi h pa allel blocking using Spa k
Ca los G ego io Rod ´ıguez
Guille mo He anz ´
Al a ez
Doble G ado en Ma em´a icas y F´ısica
Cu so acad´emico 2019-2020
Con oca o ia de Junio
Resumen:
En es e abajo plan eamos un algo i mo que pe mi e iden i ica qu´e egis os de un da ase , a´un
no siendo id´en icos, se co esponden con la misma en idad eal (En i y Resolu ion). El algo i mo
cl´asico pa a es e p oceso consis e en la compa aci´on di ec a de odos los egis os dos a dos y,
po an o, iene po lo menos complejidad cuad ´a ica. Nues a soluci´on mejo a el algo i mo cl´asico
u ilizando pa alelizaci´on y, po consiguien e, ga an izando la escalabilidad del mismo. Adem´as, el
dise˜no del algo i mo es gen´e ico. Pe mi e la de inici´on de unos pa ´ame os de con igu aci´on pa a
adap a lo al da ase conc e o que se desee es udia . Las ejecuciones ealizadas pa a analiza el
compo amien o de es e algo i mo han esul ado muy sa is ac o ias, ob eniendo esul ados muy
simila es al caso cl´asico en unos iempos de ejecuci´on signi ica i amen e meno es. Es a di e encia
empo al es a´un mayo con o me aumen emos el ama˜no de los da ase s sob e la que se abajen.
Abs ac :
In his wo k we p esen and algo i hm ha allows he use o iden i y which egis e s om a
da ase , while no being iden ical, ep esen he same eal-wo ld en i y (En i y Resolu ion). The
classical algo i hm o his p ocess consis s o di ec compa isons be ween all egis e s and, as a
esul , has a leas quad a ic complexi y. Ou solu ion imp o es upon his classical algo i hm by
using pa alleliza ion, g an ing i s scalabili y. In addi ion, i s design is gene ic. I allows o some
con igu a ion pa ame e s o be de ined depending on he conc e e da ase ha wan s o be s udied.
The execu ions pe o med o analyse i s beha iou ha e been e y success ul, ob aining e y simila
esul s o he classical algo i hm using signi ican ly less execu ion ime. This ime di e ence is e en
bigge as he da ase ’s size inc eases.
1
´
Indice
1. In oducci´on 3
2. Ma co e´o ico 5
2.1. Funcionesma chyme ge ................................. 5
2.2. Union Class ......................................... 7
3. P incipios undamen ales del algo i mo 9
3.1. Escalabilidad ........................................ 9
3.2. P ecisi´on........................................... 10
3.3. Adap abilidad........................................ 10
3.3.1. Dis ancias...................................... 11
3.3.2. Fac o es....................................... 12
3.3.3. O den........................................ 13
4. La l´ogica del algo i mo 13
5. Aplicaci´on sob e da ase s conc e os 21
5.1. FEBRL ........................................... 21
5.2. Da ase m´edico....................................... 22
5.2.1. Escalado en el iempo de ejecuci´on . . . . . . . . . . . . . . . . . . . . . . . . 26
6. Conclusiones 30
7. Bibliog a ´ıa 32
2
1. In oducci´on
Es e p oyec o su ge a a´ız de un p oblema que apa ece du an e el a amien o y an´alisis de
da os en el ´ambi o de la salud. Habi ualmen e, los p o esionales de la salud in oducen los da os
de sus pacien es de o ma manual en sus bases de da os. Al se es e p oceso manual, apa ecen
p incipalmen e dos e ec os que di icul an su pos e io a amien o y an´alisis. Son los siguien es:
1. Uso de diminu i os, aco aciones, guiones ...
2. In oducci´on de e o es ipog ´a icos a iados.
Es os e ec os p o ocan que los pacien es puedan ene los da os asociados a sus p uebas m´edicas
dispe sos en a ios egis os, lo que di icul a el acceso de los m´edicos a su his o ial. M´as que una le e
incon eniencia, es o puede con e i se en un hecho pelig oso cuando un m´edico no puede accede
a in o maci´on i al sob e su pacien e, necesa ia pa a oma una decisi´on sob e un a amien o que
es e deba segui .
Es e p oblema no solo su ge en el ´ambi o m´edico. En oda si uaci´on donde una emp esa, un
gobie no o cualquie ipo de o ganizaci´on quie a uni ica los egis os que ep esen an in o maci´on
sob e una misma pe sona o en idad eal, pe o que hayan sido ecogidos de o ma dis in a o gene a-
dos po dis in os medios (p.e. dis in os empleados esc ibiendo los da os de sus clien es), debemos
se capaces de de e mina si dos egis os, que a p io i son di e en es, ealmen e ep esen an a la
misma pe sona o en idad.
Pa a a a de soluciona es a cues i´on, buscamos la o ma de iden i ica y uni los egis os
que p oceden de una misma pe sona. A pesa de que la in o maci´on que con o ma los egis os no
sea la misma, debemos de e mina si es su icien emen e simila pa a conside a que e ec i amen e
los egis os compa ados son de la misma pe sona. La soluci´on plan eada es cons ui un algo i mo
de En i y Resolu ion (concep o que de ini emos de o ma p ecisa en el ma co e´o ico, en la secci´on 2).
El concep o de En i y Resolu ion (ER) ha sido aplicado a dis in os p oblemas y con dis in as
me odolog´ıas y hoy en d´ıa con inua siendo un campo de es udio ac i o [1, 2]. Podemos encon a -
nos soluciones pa a ER que hacen uso de ecnolog´ıas an ac uales hoy en d´ıa como deep lea ning
[3], sis emas de ER in eligen es, que ap enden qu´e no mas debe usa pa a ealiza el p oceso de
o ma co ec a [4], o ans o mando los da os en una es uc u a de g a os pa a usa sis emas de
e ex-ma ching [5]. Las o mas de hace ER han sido y con inuan siendo muy a iadas. En nues o
caso, que emos desa olla un algo i mo de ER que sea aplicable a da ase s simila es al que o igina
nues o p oblema. Nos e e imos a da ase s o mados po un cie o n´ume o de ilas, cada una de
ellas ep esen ando un egis o, y o o cie o n´ume o de columnas, cada una de ellas ep esen ando
un ozo de in o maci´on que posee cada egis o. Adem´as, que emos se capaces de es ablece de
o ma cla a y anspa en e cuando dos egis os p oceden de la misma en idad eal.
Inicialmen e, disponemos un da ase de 35284 elemen os. Un algo i mo cl´asico pa a es e p o-
blema es ´a basado en la compa aci´on de egis os de cada uno de los egis os con odos los dem´as.
Pod ´ıamos hace uso de es e algo i mo cl´asico pa a esol e es e p oblema. Es una soluci´on bas an e
len a pe o e mina uncionando. Sin emba go nos plan eamos, ¿y si el da ase uese m´as g ande?
¿Y si uese lo su icien emen e g ande pa a que no podamos usa algo i mos cl´asicos en un iempo
azonable? ¿Y si el da ase que que emos es udia no iene los mismos campos que nues o da ase
inicial?
3
T a ando de esponde es as p egun as hemos ideado un algo i mo escalable que se ap oxime
lo m´aximo posible a una soluci´on ´op ima. Adem´as, que emos que sea e s´a il, con capacidad de
adap a se a modi icaciones del ipo de da os que enemos pa a que no sea ´unicamen e ´alido pa a
nues o p oblema o iginal.
El algo i mo m´as di ec o que pod ´ıamos cons ui pa a hace En i y Resolu ion, como hemos
comen ado, se ´ıa la compa aci´on di ec a una a una de los N egis os que p esen a un da ase pa a
decidi si ep esen an o no la misma en idad. Sin emba go es a opci´on es complicada compu acio-
nalmen e hablando, pues un algo i mo con es as ca ac e ´ıs icas es, al menos, de o den cuad ´a ico,
O(n2). Habi ualmen e el cos e es a´un mayo debido a ene que se exhaus i o a la ho a de busca
odos las posibles anexiones, lo cual di icul a su escalabilidad. Adem´as, no es pa alelizable, es deci ,
debe ejecu a se en una ´unica m´aquina simul ´aneamen e. Cuando los clus e de o denado es son
cada ez m´as comunes, un algo i mo no pa alelizable pie de mucho alo . Po es e mo i o hemos
desa ollado un algo i mo pa alelizable pa a busca la escalabilidad.
El abajo sigue la siguien e es uc u a. En la secci´on 2, amos a in oduci el ma co e´o ico
sob e el que se asien a la cons ucci´on del algo i mo. Fo maliza emos el p oceso de En i y Resolu-
ion in oduciendo los concep os y las de iniciones igu osas que pe mi en de ini con p opiedad el
p oblema. Sob e es e o malismo se es ablecen unas p opiedades que nos ga an izan la exis encia
de un esul ado ´op imo y o mas ( ela i amen e abs ac as) de ob ene lo.
Con inua emos en la secci´on 3 in oduciendo los p incipios undamen ales con los que se han
desa ollado el algo i mo, de allando bene icios e incon enien es que su gen de su uso. En la secci´on
4, inclui emos y comen a emos el p opio c´odigo del algo i mo pa a en ende c´omo unciona paso a
paso.
Finalmen e, en la secci´on 5, analiza emos los esul ados que ob iene en e a dos ipos de da a-
se s. El p ime ipo se ´a un conjun o de da ase s de los cuales conocemos su soluci´on, pa a pode
obse a qu´e an bien ealiza su unci´on. El segundo se ´a el da ase del cual su ge es e abajo y
p ocede de p uebas m´edicas. De es e da ase no se iene la soluci´on, po lo que nos cen a emos en
analiza dis in as ejecuciones pa a e alua el iempo de compu aci´on y los esul ados ob enidos.
4

2. Ma co e´o ico
En i y Resolu ion, Resolucion de En idades o, como nos e e i emos desde aho a, ER, es un
p oceso median e el cual iden i icamos y uni icamos los egis os de un da ase que ep esen an a
la misma en idad eal. Es os egis os asociados a una misma en idad pueden es a inicialmen e
desligados po mul i ud de ac o es, que incluyen la epe ici´on de egis os, la in oducci´on manual
de in o maci´on e ´onea, la co upci´on de los da os al ans o ma los, e c.
En es e ma co e´o ico amos a comenza po in oduci una se ie de cues iones sob e algo i mos
de ER pa a de alla despu´es como es el ma co es uc u al que amos a u iliza [6].
2.1. Funciones ma ch y me ge
Cuando hablamos de ER, es amos conside ando impl´ıci amen e dos p ocesos: selecci´on de cuan-
do dos egis os son de la misma en idad y el modo en que, una ez decidido que son de la misma
en idad, jun amos los dos egis os. Es os dos p ocesos es ´an egidos po dos unciones, la unci´on
ma ch y la unci´on de me ge.
Sea E el conjun o de los posibles egis os, que podemos conside a in ini o. Decimos que M es
la unci´on de ma ch del p oceso ER si es ´a de inida sob e E×Ey iene como imagen dos posibles
alo es, que llama emos ue y alse. Sean 1y 2 egis os ( 1, 2∈E), en onces M( 1, 2) = ue
si 1y 2 ep esen an la misma en idad eal. En caso con a io, M( 1, 2) = alse. Con es as
p opiedades lo que es amos pidiendo es que el ma ching depende ´unicamen e de los dos egis os
compa ados y se decide si hacen ma ch o no de o ma inequ´ı oca, sin ning´un ipo de ni el de
con ianza.
La unci´on de me ge, que llama emos N, ambi´en debe sa is ace dos p opiedades. Debe es a
de inida sob e (E×E)|{ 1, 2∈E|M( 1, 2)= ue}y ene como imagen E. Pa a alige a la no aci´on u u-
a, M( 1, 2) = ue lo deno amos po 1≈ 2(en caso con a io, 16≈ 2). Tambi´en deno a emos
N( 1, 2) po h 1, 2i, que se ´ıa el egis o ob enido al aplica la unci´on de me ge.
Es as p opiedades que acabamos de de ini son las es ic amen e necesa ias pa a pode lle a a
cabo un p oceso de ER. Dados dos egis os decidimos si hacen ma ch y gene amos un egis o que
aglu ine la in o maci´on de ambos. Es a ´ul ima p opiedad no la hemos enunciado, pe o es e iden e
que es necesa ia pa a de ini una buena unci´on de me ge. Si no nues o esul ado no a a se un
buen esul ado.
Sin emba go, pa a ealiza un p oceso de ER de o ma e icien e, hay cie as p opiedades adicio-
nales que que ´ıamos pedi pa a hace nues o p oceso m´as e icien e. Son las siguien es:
1. Idempo encia: ∀ , ≈ yh , i= . Es a p opiedad nos dice que un egis o hace ma ch
consigo mismo y el egis o ob enido de jun a lo consigo mismo es ´el mismo.
2. Conmu a i idad: ∀ 1, 2, 1≈ 2si y solo si 2≈ 1. Adem´as, si 1≈ 2,h 1, 2i=h 2, 1i.
3. Asocia i idad: ∀ 1, 2, 3de o ma que exis an an o h 1,h 2, 3ii como hh 1, 2i, 3i, en onces
enemos que h 1,h 2, 3ii =hh 1, 2i, 3i.
4. Rep esen a i idad: Si 3=h 1, 2i, en onces ∀ 4 al que 1≈ 4, se iene ambi´en que 3≈ 4.
5
Es as 4 p opiedades las llama emos las p opiedades ICAR, po sus iniciales. Son p opiedades
bas an e na u ales y deseables en un p oceso de ER. Especialmen e impo an e es la asocia i idad,
pues de ella depende el hecho de que el o den en el que se ealiza las ope aciones sea ele an e o
no. Tambi´en no emos que es as p opiedades no implican la ansi i idad (si 1≈ 2y 2≈ 3no
necesa iamen e se iene que 1≈ 3).
La p incipal o aleza de las p opiedades ICAR en un p oceso ER es que cuando se sa is acen
enemos ga an izado que nues o p oceso ER a a ob ene el esul ado m´as ´op imo posible, es
deci , amos a consegui anexiona la mayo can idad de egis os posibles. Pa a e es o, debemos
da una se ie de de iniciones p e ias. Sea I una ins ancia de E, es deci , un subconjun o ini o del
conjun o de odos los posibles egis os.
De inicion 1 Dada I, de inimos el cie e de I, deno ado po ¯
Icomo el meno conjun o que e i-
ique:
1. I⊆¯
I.
2. ∀ 1, 2∈¯
I, si 1≈ 2, en onces h 1, 2i ∈ ¯
I.
Esencialmen e el cie e de I es un conjun o m´as g ande donde a˜nadimos de o ma ei e a i a
odos los posibles esul ados de jun a egis os. De es e modo, si dos egis os hacen ma ch, el
egis o esul an e de la ope aci´on de me ge siemp e se encuen a en es e conjun o. No emos que
es e conjun o ¯
Icla amen e exis e y es ´unico, pues o que se puede ob ene como el pun o ijo del
p oceso de a˜nadi a I odos los posibles me ges.
De inicion 2 Sean dos ins ancias de E, I1eI2. Decimos que I1es ´a dominada po I2(y lo
deno amos po I1I2) si ∀ 1∈I1,∃ 2∈I2de o ma que 1≈ 2y adem´as 2almacena m´as
in o maci´on que 1(deno ado po 1 2)
Es a de inici´on en esencia a a de es ablece una especie de elaci´on de o den en e ins ancias.
Una ins ancia se ´a meno en es e sen ido si pa a odo egis o que enga hay o o en la mayo que
hace ma ch con ´el y iene m´as in o maci´on. Un ejemplo se ´ıa que dado un egis o como [{’a’}]
u i´esemos o o egis o como [{’a’,’b’}] en la mayo (y suponemos que hacen ma ch, seg´un la l´ogica
del algo i mo que hemos desa ollado). Hacen ma ch y el segundo gua da m´as in o maci´on que el
p ime o.
Con es as dos nociones, podemos ya de ini lo que buscamos en un p oceso ER, la esoluci´on
de I.
De inicion 3 Dada una ins ancia I, deno amos po I0a un conjun o que e i ica las siguien es 3
p opiedades:
1. I0⊆¯
I.
2. ¯
II0.
3. No exis e ning´un subconjun o es ic o de I’ que e i ique 1 y 2
Es e conjun o I’ es lo que llama emos la esoluci´on de I, o ER(I). Esencialmen e es la m´ınima
ins ancia incluida en el cie e de I y que con iene oda la in o maci´on que con iene el cie e de I. Es o
es lo que espe a ´ıamos in ui i amen e que uese la esoluci´on de I, el m´ınimo conjun o de egis os
con la m´axima in o maci´on. Cada uno de es os egis os ep esen a ´ıa una en idad dis in a. Pa a
ga an iza nos que es ´unico enemos la siguien e p oposici´on.
6
P oposici´on 1 Dada una ins ancia I, la esoluci´on de I exis e, es ´unica, y la deno a emos po
ER(I)
Una ez ya hemos in oducido el concep o o mal de la esoluci´on de una ins ancia, amos a
de ini o malmen e el p oceso de ob ene ER(I).
De inicion 4 Dada una ins ancia I, una de i aci´on es una ans o maci´on de I en o a ins ancia
I’ median e dos posibles ope aciones:
Me ge: Dados dos egis os 1y 2de I, si se iene que 1≈ 2yh 1, 2i 6∈ I, en onces
I0=I∪ {h 1, 2i}.
Pu ga: Dados dos egis os 1y 2de I, si se iene que 1 2, en onces I0=I− { 1}
En base a es a de inici´on, una de i aci´on es cada uno de los p ocesos indi iduales que nos pe -
mi en ace ca nos a la soluci´on del p oblema. Solamen e hay dos opciones, o a˜nadimos un elemen o
nue o que no en´ıamos, p oceden e de hace me ge de dos egis os, o eliminamos un egis o que
e a edundan e. A pa i de una de i aci´on, podemos de ini una cadena de de i aciones, In, que
no es m´as que encadena de i aciones pa a ace ca nos a la soluci´on. Decimos que una cadena es
maximal si no exis e ninguna posible de i aci´on en el ´ul imo elemen o de la cadena.
Finalmen e, podemos enuncia el eo ema po el cual las p opiedades ICAR esul an undamen-
ales pa a hace un ER e icien e.
Teo ema 1 Supongamos que un p oceso ER iene unas unciones ma ch y me ge que e i ican
las p opiedades ICAR. En onces, pa a oda ins ancia I, ER(I) es ini a y cualquie secuencia de
de i aci´on maximal ob ene ER(I).
En base a es e eo ema que emos a a de de ini pa a nues o algo i mo unciones ma ch y
me ge que posean las p opiedades ICAR pa a mejo a nues a e iciencia. Pa a ello nos basa emos
en la Union Class.
2.2. Union Class
La Union Class es una clase de unciones ma ch y me ge que cumplen las p opiedades ICAR.
La idea p incipal que la cons uye es que no se pie da nada de in o maci´on en las ope aciones. Pa a
ello, cuando dos egis os hacen ma ch, el nue o egis o esul an e se ob iene combinando los alo-
es que de in´ıan indi idualmen e a cada uno de los dos egis os. De es e modo, los nue os egis os
gene ados con ienen oda la in o maci´on de sus p edeceso es. Un ejemplo se ´ıa el siguien e. Supon-
gamos que enemos dos egis os que se an a jun a , M. Te esa yMa ´ıa Te esa. Gene a ´ıamos
un nue o egis o que se ´a {M. Te esa, Ma ´ıa Te esa}. No emos que en es e caso pod ´ıamos ha-
be jun ado ambos egis os en ´unico alo : Ma ´ıa Te esa. De es e modo ampoco pe de ´ıamos
ninguna in o maci´on. No obs an e, ema camos la opci´on conjun is a pues es en la que amos a
basa nues a algo i mo, pues su gene alizaci´on es m´as sencilla. Pos e io men e, cuando que amos
compa a nue os egis os con el conjun o ob enido, ha emos compa aciones con cada uno de los
elemen os del conjun o, pues odos ellos se ´an dis in as o mas de ep esen a a una misma en idad.
Impo an e no a que en es a desc ipci´on de la Union Class no hemos hecho menci´on a c´omo
debe se la unci´on ma ch, sal o que debe se capaz de compa a egis os o mados po conjun os
una ez empiece a habe egis os que, gene ados seg´un es a l´ogica, aglu inan da os en conjun os.
E iden emen e debemos a˜nadi algo m´as a es a unci´on ma ch pa a que se sa is agan las p opieda-
des ICAR, y po ello enemos la siguien e p oposici´on.
7
P oposici´on 2 Dadas unciones ma ch y me ge en la Union Class, si la unci´on ma ch es adem´as
e lexi a y conmu a i a, en onces se sa is acen las p opiedades ICAR.
La impo ancia de ene unciones ma ch y me ge que cumplan las p opiedades ICAR es muy
ele an e pa a mejo a la e iciencia de un algo i mo de ER. No solo exis en unciones que e i iquen
es as p opiedades en la Union Class. Sin emba go, la o ma de cons ui es as unciones esul a una
o ma muy na u al de abo da nume osos p oblemas de ER. Adem´as, las p opiedades exigidas son
p opiedades ´aciles de consegui al dise˜na unciones de ma ch. O as p opiedades ambi´en deseables
y/o in ui i as, como la ansi i idad, no son an sencillas de ob ene . De hecho, el algo i mo dise˜nado
no posee la p opiedad de ansi i idad.
8
de ma ch_and_me ge(x, ac o s,dis ances, excluyen es = 1):
h eshold = 1
e u n_lis =[]
key, i e ado =x
da a =lis (i e ado )
da a.so (key=lambda x: len(x[3]), e e se=T ue)
comp obados =[]
con ado = 0
esul =dic ()
i=0
o elemen in da a[:]:
seguimos =T ue
i ino in comp obados:
esul [con ado ] =(elemen )
while seguimos:
j=0
seguimos =False
o elemen 2 in da a[:]:
i jno in comp obados and dis ancia( esul [con ado ],elemen 2, ac o s,
dis ances, excluyen es) <= h eshold:
comp obados.append(j)
seguimos =T ue
emp = esul [con ado ]
o con in ange(len(elemen 2)):
emp[con ] = emp[con ].union(elemen 2[con ])
esul [con ado ] =( emp)
j+=1
con ado +=1
i+=1
o iin ange(len( esul )):
e u n_lis .append((key, esul [i]))
e u n e u n_lis
Figu a 2: Funci´on de ma ch y me ge.
15

om Le ensh ein impo dis ance as L_dis ance
######Dis ancias de inidas
de L_dis ance_ acios(elemen 1,elemen 2):
i elemen 1 == '' o elemen 2 == '':
e u n 1
else:
e u n L_dis ance(elemen 1,elemen 2)
de dis ancia_le ens ein_sepa ando_ acios(elemen 1,elemen 2):
se 1=se (elemen 1.spli (' '))
se 2=se (elemen 2.spli (' '))
dis ancia_ emp =[1000]
i '' in se 1 o '' in se 2:
dis ancia_ emp.append(1)
o elemen in lis (se 1):
o elemen _2 in lis (se 2):
dis ancia_ emp.append(L_dis ance_ acios(elemen ,elemen _2))
e u n min(dis ancia_ emp)
Figu a 3: Ejemplos de dis ancias que podemos de ini .
lo igno amos. En caso con a io, lo a˜nadimos a nues o dicciona io de esul ados. A con inuaci´on,
buscamos en odos los egis os que no han sido anexionados a o os si hay ma ch con alguno.
De habe lo, modi icamos la en ada del dicciona io de esul ados con el me ge de ambos egis os.
Po la al a de ansi i idad de nues a unci´on, puede habe egis os que inicialmen e no hiciesen
ma ch, pe o que as habe con e ido nues o egis o en uno que almacena m´as in o maci´on si
que lo haga. Pa a ello, in oducimos un bucle while que hace que es e p oceso se epi a mien as
ob engamos al menos un ma ch nue o. Po la ini ud del bucke es e p oceso e mina necesa ia-
men e. Una ez no encon amos m´as posibles ma ches, pasamos al siguien e elemen o del bucke y
epe imos el p oceso has a e mina lo.
La o a unci´on de es e a chi o que me ece la pena comen a es la unci´on que p opiamen e
ejecu a el algo i mo. No obs an e, c eemos que es mejo pa a en ende po comple o su unciona-
mien o comen a an es los o os dos a chi os que componen el algo i mo.
El a chi o dis ancias.py es un a chi o donde se ca gan las dis ancias que se an a que e
usa en la ejecuci´on del algo i mo. En nues o caso, se encuen a ca gada la dis ancia Le ensh ein
en dos e siones. La p ime a de ellas es la dis ancia de Le ensh ein p opiamen e dicha a˜nadiendo
la condici´on de que la dis ancia de un inde inido a cualquie o o elemen o sea 1. La segunda se
a a de una modi icaci´on hecha sob e es a dis ancia pa a medi mejo la dis ancia en e nomb es
compues os, sepa ando los nomb es como Jose Ca los en {Jose, Ca los}y aplicando el m´ınimo de
las dis ancias de es e conjun o con o o elemen o. El c´odigo se ´ıa el obse ado en la igu a 3.
En cuan o a Algo i mo.py, se a a de un a chi o donde se de inen los de alles espec´ı icos de
la ejecuci´on a ealiza y se ealiza esa ejecuci´on. En p ime luga , ca gamos las unciones que es ´an
de inidas en los o os 2 a chi os mencionados y de inimos los pa ´ame os a ados en la secci´on
3.3, as´ı como los p epa amos pa a que engan una o ma adecuada pa a la ejecuci´on. El c´odigo
comple o se encuen a en la igu a 4.
16
impo numpy as np
om es uc u a impo *
om dis ancias impo *
#######Espacio de pa ame os
a chi o ='*****************'
o den =[1,3,0,2]
ac o es_o igen =[1,0.25,0.25,0.5]
dis ancias_o igen =[L_dis ance_ acios,L_dis ance_ acios,
dis ancia_le ens ein_sepa ando_ acios,L_dis ance_ acios]
mul iplicado = 2/3
#### P epa aci´on pa ´ame os
longi ud =len(o den)
ac o es=[0 o xin ange(len(o den))]
o iin ange(len(o den)):
ac o es[i] = ac o es_o igen[:o den[i]]+ ac o es_o igen[o den[i]+1:]
dis ancias=[0 o xin ange(len(o den))]
o iin ange(len(o den)):
dis ancias[i] =dis ancias_o igen[:o den[i]]+dis ancias_o igen[o den[i]+1:]
o iin ange(len( ac o es)):
ac o es[i] =[mul iplicado *x o xin ac o es[i]]
lis _o _maps =[selecciona _map(o den[0])]
lis _o _ma chs =[]
o iin ange(len(o den)-1):
lis _o _maps.append(selecciona _map_in e medio(o den[i+1],o den[i]))
o iin ange(len(o den)):
lis _o _ma chs.append(selecciona _ma ch( ac o es[i],dis ancias[i]))
las _ma ch =selecciona _ma ch( ac o es[0],dis ancias[0], excluyen es = 2)
Figu a 4: De inici´on y p epa aci´on de pa ´ame os.
17
##### Funci´on de p epa aci´on del da ase
de mapeo_desde_a chi o(x, l = 5):
da os =x.spli (';')
o iin ange(len(da os)):
i i== l-1:
da os[i] =se (e al(da os[i]))
else:
da os[i] =se ([da os[i]])
e u n da os
Figu a 5: Ejemplo de unci´on de p epa aci´on del da ase .
Comenzamos po el o den en que los campos an a se usados como cla e. Seguimos con la
gene aci´on de los ac o es y dis ancias a usa en cada i e aci´on del algo i mo. En el siguien e paso
in oducimos un mul iplicado . La unci´on de es e mul iplicado es eescala los ac o es. De es a
o ma podemos esc ibi inicialmen e cual el peso ela i o de cada campo, lo cual es m´as sencillo
de ealiza . Reduci es e mul iplicado iene el mismo e ec o que aumen a el l´ımi e que no puede
sob epasa la dis ancia en e dos egis os pa a jun a los, mien as que aumen a lo iene el e ec o
con a io. As´ı, educi lo es equi alen e a se m´as conse ado es a la ho a de jun a egis os y au-
men a lo es se menos conse ado .
A con inuaci´on, gua damos en lis as una se ie de unciones pa a pode ealiza de golpe a ias
i e aciones del algo i mo. Los maps co esponden a las ans o maciones que enemos que hace
en e i e aciones, que consis en en e o na el campo que es amos usando como cla e al es o del
egis o y sepa a el nue o campo cla e del egis o. Cla amen e es e p oceso es ´a de inido en un-
ci´on del o den escogido de campos. No emos que la p ime a unci´on de map es dis in a al es o,
pues solo iene como a gumen o el elemen o a se cla e, ya que no hab´ıa ninguno siendo cla e
an e io men e. Respec o a los ma ch que se obse an, lo que se hace es a˜nadi una unci´on conjun a
de ma ch y me ge, que en cada i e aci´on es dis in a al cambia los ac o es y las dis ancias usadas.
Queda po comen a la uncion las ma ch, pe o pa a en ende bien su ele ancia la comen a emos
en la p opia ejecuci´on.
Po ´ul imo, debemos de ini una unci´on que p epa e el da ase desde el a chi o a la o ma que
debe ene (a sabe , una lis a de lis as donde cada elemen o es un conjun o de alo es). Es a unci´on
depende ´a de c´omo es ´e gua dado el da ase inicialmen e. Un ejemplo de unci´on de p epa aci´on
se ´ıa la mos ada en la igu a 5.
La ejecuci´on del algo i mo se ealiza en la ´ul ima unci´on del a chi o es uc u a.py, y es eje-
cu ada como mos amos en la igu a 6.
T as ejecu a el algo i mo, mos amos el iempo de ejecuci´on y gua damos el esul ado en un
a chi o cs pa a su pos e io an´alisis.
An es de comen a c´omo se ealiza la ejecuci´on, amos a desc ibi una ope aci´on que se lle a
a cabo du an e la misma: el despliegue. Reco demos que odos los elemen os del da ase deben
se conjun os. Po ello, cuando usamos un elemen o como cla e, solo o ma ´a un bucke con o os
egis os con exac amen e el mismo conjun o como cla e. Es o en la p ime a i e aci´on no es p o-
18
#### Ejecuci´on
esul , iempo =
algo i mo(o den,lis _o _maps,lis _o _ma chs,las _ma ch,a chi o,mapeo_desde_a chi o),→
p in ('Fin: {} s'. o ma ( iempo))
wi h open(a chi o.spli ('.')[0]+'_ esul ado.cs ','w')as :
o i em in esul :
.w i e('%s n'%i em)
Figu a 6: Llamada de ejecuci´on del algo i mo.
0de algo i mo(o den,lis _o _maps,lis _o _ma chs,las _ma ch,a chi o,mapeo_p epa acion):
1s a = . ime()
2 dd_op =sc. ex File(a chi o).map(mapeo_p epa acion)
3 o iin ange(len(o den)):
4 dd_op =
dd_op.map(lis _o _maps[i]). la Map(sepa a _keys).g oupByKey(). la Map(lis _o _ma chs[i]),→
5 dd_op = dd_op.map(selecciona _map_in e medio(o den[0],o den[i]))
6 dd_op = dd_op.map(copia _leading_se ). la Map(sepa a _keys)
7 dd_op = dd_op.g oupByKey(). la Map(las _ma ch).map(o den_ inal)
8 dd_op = dd_op.map(map_ egis os).g oupByKey().map(me ge_ egis os)
9 esul = dd_op.collec ()
10 end= . ime()
11 e u n esul , end-s a
Figu a 7: Pasos del algo i mo.
blem´a ico, pe o en las sucesi as es desas oso, pues dos elemen os que ienen dis ancia 0 como son
{A, B}y{A}no acaba ´ıan en el mismo bucke . Esencialmen e son iguales, po lo que que emos
que sus egis os asociados acaben en el mismo bucke . Po ello, lo que ha emos se ´a desplega los
en a ios egis os iguales, donde la cla e de cada egis o se ´a un elemen o de dicho conjun o.
Como adelan ´abamos en la secci´on 3.1, es a ope aci´on de despliegue nos hace des ia nos de la
l´ogica de la Union Class. Es ine i able usa la si que emos gene a buenos bucke s donde compa a
elemen os, pe o a cambio nos emos o zados a gene a egis os donde se pie de in o maci´on al
ealiza la. Es o implica que el o den de ejecuci´on se ´a ele an e a la ho a de ob ene esul ados.
Como ambi´en mencion´abamos en dicha secci´on, al segui el es o del iempo la l´ogica de la Union
Class, espe amos que e nos o zados a es a ope aci´on no nos dis ancie demasiado de la soluci´on
´op ima.
Finalmen e, el c´odigo de la ejecuci´on se encuen a den o de la siguien e unci´on. Es impo an e
ema ca que es a secci´on de c´odigo es en la que ealmen e se usa Spa k como he amien a de pa-
alelizaci´on. El es o de unciones son pu o c´odigo en Py hon que se ejecu a ´a de o ma secuencial
en cada uno de las m´aquinas que compongan el clus e . Vamos a i comen ando es e c´odigo linea
po linea pa a acili a su comp ensi´on. El c´odigo se mues a en la igu a 7.
Linea 1: Iniciamos el eloj pa a lle a la cuen a del iempo de la ejecuci´on del algo i mo.
19
Linea 2: De inimos el RDD ca gando desde a chi o el da ase sob e el que ejecu amos. A la ez, usamos
la unci´on pa a ca ga desde el a chi o los da os en un o ma o ´u il pa a ejecu a (incluyendo
la ans o maci´on en conjun os). Reco damos en es e pun o que los da os deben eni con un
iden i icado ´unico de cada egis o como ´ul imo campo del espec i o egis o. De no ene lo
hab ´ıa que a˜nadi lo p e iamen e.
Lineas 3 y 4: En cada i e aci´on de es e bucle colocamos el elemen o que a a se cla e en la i e aci´on y lo
desplegamos. A con inuaci´on ag upamos los elemen os po su cla e pa a o ma los bucke s
y ejecu amos las unciones de ma ch y me ge. I e amos es e p oceso mien as el pa ´ame o
o den nos lo o dene.
Lineas 5 y 6: T as ealiza odas las ope aciones, colocamos el da ase de o ma que la nue a cla e uel a
a se el campo ue cla e en el p ime paso. En es e pun o enemos el p oblema de que as
desplega , hay campos cuyas alo es no son lo comple os que debe ´ıan se como consecuencia
de ese despliegue. Po ello ol emos a ejecu a usando como cla e la misma que en el p i-
me paso, pe o en es a ocasi´on gua dando qu´e conjun o es el que an es de desplega es aba
ac uando como cla e. Lo gua damos al inal de nues o egis o y desplegamos.
Linea 7: Ag upamos po la cla e, y ejecu amos las ma ch. Es a unci´on iene en cuen a que hemos
copiado el conjun o cla e an es del despliegue, y po ello iene como pa ´ame o excluyen es 2.
Adem´as, usa los ac o es y las dis ancias de la p ime a i e aci´on. El ´ul imo map obse ado, que
usa la unci´on o den inal, elimina la exis encia de una cla e y eo dena el egis o, dej´andolo
de la o ma [campo[o den[0]], es o de campos o denados seg´un su o den inicial, excluyendo el
o den[0]].
Linea 8: En es e pun o hay a ios egis os que no son copias unos de o os, pe o que han jun ado
exac amen e los mismos iden i icado es de egis o. Po es e pun o es impo an e ene es os
iden i icado es. Debido al uncionamien o del algo i mo, los elemen os del campo que es cla e
en ´ul imo luga no se ag upan co ec amen e, si no que se epa en en a ias copias del mismo
egis o pe o cambiando ese campo. Pa a uni ica lo, ha emos una ´ul ima ag upaci´on. En es e
caso, la cla e se ´a el conjun o de iden i icado es sin desplega . De es e modo solo se uni ´an
egis os que p ocedan de los mismos egis os iniciales. En es e caso, no hacemos ning´un
ma ch, unimos di ec amen e con me ge egis os, de inida en es uc u a.py .
Linea 9: Finalmen e, llamamos al m´e odo collec pa a ealiza las ope aciones de inidas sob e el RDD
y lle a a cabo la ejecuci´on.
Linea 10: Te minamos el eloj pa a ob ene el iempo de ejecuci´on.
Linea 11: De ol emos el esul ado ob enido y el iempo de ejecuci´on.
20

5. Aplicaci´on sob e da ase s conc e os
En es a secci´on p e endemos analiza los esul ados que se ob ienen al ejecu a el algo i mo
en e a los dos ipos de da ase s mencionados en la in oducci´on. Comenza emos en p ime luga
con los da ase s de los cuales disponemos la soluci´on y con inua emos con el da ase de nues o
p oblema o iginal.
5.1. FEBRL
Es os da ase s es ´an gene ados a pa i de paque e F eely Ex ensible Biomedical Reco d Linkage
(FEBRL). Los 4 da ase s asociados los hemos ob enido del paque e de Py hon eco dlinkage. De
es os 4 da ase s, el n´ume o 4 (del cual ob enemos ealmen e 2 da ase s) iene odos sus egis os
co espondien es a en idades dis in as, po lo que lo usa emos pa a comp oba que el algo i mo
no es ´e esol iendo mal algunas en idades. Como pa ´ame os al algo i mo, usa emos como ac o es
0.5 si el campo es num´e ico y 0.25 si el ac o es un s ing. Adem´as, usa emos un mul iplicado
de 0.2 pa a se poco conse ado es a la ho a de hace ma ch. Como unci´on dis ancia usa emos
en odos la dis ancia Le ens ein, conside ando que la dis ancia a cualquie s ing ac´ıo es 1. Con
espec o al o den, ha emos 3 i e aciones sob e los campos 5, 6 y 3, en o den de enume aci´on. Es a
elecci´on no es ´a ealizada al aza . Se ha obse ado c´omo es la dis ibuci´on de ecuencias de odos
los campos pa a busca cuales son los m´as ap opiados. Un an´alisis de c´omo a ec a es a dis ibuci´on
a la ejecuci´on del algo i mo lo e emos en la secci´on 5.2. Los esul ados ob enidos los p esen amos
en la abla 1.
Nºelemen os Tiempo (s) Duplicados De ec ados De ec ados ( %)
b l1 1000 0.76 500 456 91.2
b l2 5000 2.28 1000 934 93.4
b l3 5000 2.10 3000 2783 92.8
b l4a 5000 2.73 0 0 -
b l4b 5000 3.24 0 0 -
Tabla 1: Ejecuci´on de nues o algo i mo sob e los da ase ob enidos de FEBRL
Como podemos obse a de la abla 1, el algo i mo no pa ece habe come ido el e o de jun a
egis os que no deben jun a se, lo cual puede se (dependiendo del con ex o) una p opiedad muy
impo an e que debe posee . Adem´as, ha ob enido muy buenos esul ados de de ecci´on, po encima
del 90 % en los 3 da ase s que en´ıan duplicidades.
En cuan o al iempo de la ejecuci´on, es ema cable que el iempo se iplica ap oximadamen e
en un da ase que mul iplica el n´ume o N de egis os po 5 ( b l1 s b l 2 y 3). Es e c ecimien o
peque˜no en iempo de ejecuci´on se debe a la elecci´on de un buen o den de ejecuci´on del algo i mo,
pues los campos elegidos ienen una buena dis ibuci´on pa a no gene a bucke s muy g andes (lo
que aumen a ´ıa la complejidad) ni muy peque˜nos (lo que ha ´ıa di ´ıcil ealiza la ope aci´on de me ge).
Pa a pode pone en con ex o es os esul ados ob enidos pa a nues o algo i mo se ´ıa in e e-
san e pode compa a lo con un algo i mo cl´asico de ER que use las mismas unciones de ma ch y
me ge. Es e algo i mo end ´ıa a su a o que no sepa a en bucke s, po lo que a p io i no puede
habe dos egis os que no lleguen a jun a se si el ma ch lo pe mi e y que sigue la Union Class
21
al y como se de ini´o inicialmen e. Po es e mo i o iene ga an izado alcanza el mejo esul ado
que puede alcanza se con dicha unci´on de ma ch. Los esul ados de ejecu a es e algo i mo cl´asico
sob e los da ase s an e io es quedan e lejados en la abla 2.
Nºelemen os Tiempo (s) Duplicados De ec ados De ec ados ( %)
b l1 1000 17.72 500 461 92.2
b l2 5000 1475 1000 947 94.7
b l3 5000 880 3000 2808 93.6
b l4a 5000 1669 0 0 0
b l4b 5000 1603 0 0 0
Tabla 2: Ejecuci´on del algo i mo cl´asico sob e los da ase ob enidos de FEBRL.
Como podemos obse a con una simple compa aci´on en e ambas ablas, el algo i mo cl´asico
ob iene una mayo p ecisi´on. De hecho, al segui la l´ogica de la Union Class, es e es en eo ´ıa el
mejo esul ado que podemos ob ene con es a unci´on ma ch. No obs an e esul a muy llama i o
el aumen o en el iempo de ejecuci´on. Los iempos pasan de unos 2 segundos a alo es del o den
de 1000 segundos. En nues a opini´on, es e aumen o del cos e compu acional no es jus i icable
pa a ob ene la poca p ecisi´on adicional que se ob iene, incluso en el caso de da ase s peque˜nos.
Reco demos que el da ase b l1 iene 1000 elemen os mien as que los o os 4 da ase s ienen 5000
elemen os. Cuando conside amos ejecu a lo sob e el da ase sob e el cual plan eamos inicialmen e
es e TFG, de 35284 elemen os, el uso de un algo i mo cl´asico pod ´ıa hace uso de mucho iempo
de ejecuci´on.
As´ı pues obse amos que nues o algo i mo p esen a muy buenos esul ados en un n´ume o bajo
de elemen os en el da ase . Su iempo de ejecuci´on es muy ´apido en compa aci´on al algo i mo
cl´asico y la p ecisi´on ob enida es muy simila a la mejo que puede ob ene se. Es de espe a que
cuando aumen emos el n´ume o de elemen os en el da ase nues o algo i mo uncione a´un mejo que
el cl´asico, pues su c ecimien o debe se meno , si hacemos una buena elecci´on de los pa ´ame os,
al hace uso del blocking.
A con inuaci´on pues, es udia emos como se compo a nues o algo i mo sob e nues o da ase
p oblema. Comencemos po desc ibi el da ase y los pa ´ame os usados pa a con igu a el algo i -
mo.
5.2. Da ase m´edico
El da ase se compone de 5 columnas: ID, apellidos, nomb e, echa de nacimien o y egis os
de p uebas. De es os 5 campos, el de egis os de p uebas ac ´ua como iden i icado de egis o,
pues cada elemen o es ´unico en el da ase . Sob e la elecci´on de pa ´ame os, sob e ID, apellidos
y echa de nacimien o usamos la misma dis ancia que en los da ase s an e io es. No obs an e,
en los nomb es usamos es a dis ancia lige amen e modi icada. Debido a la p esencia de nomb es
compues os, decidimos que la dis ancia en e dos nomb es e a el m´ınimo de la dis ancia en e los
cons i uyen es de ese nomb e. As´ı, la dis ancia en e, po ejemplo, Ma ´ıa Te esa yMa ´ıa se ´ıa el
m´ınimo en e las dis ancias Ma ´ıa aMa ´ıa yTe esa aMa ´ıa, 0 en es e caso. La elecci´on de los
ac o es ue: 0.25 pa a nomb e y apellido, 0.5 pa a echa y 1 pa a ID. Como en es e caso es amos
a ando con un da ase eal, no disponemos de un da ase simila pa a sabe si es amos haciendo
22
ma ch de egis os que no que emos que hagan ma ch. Po ello, usa emos un mul iplicado bas-
an e m´as conse ado que en el caso de los da ase s FEBRL pa a a a de e i a es a si uaci´on: 2
3.
Pa a a a el o den, como el iempo de ejecuci´on del algo i mo en es e da ase no e a dema-
siado ele ado, pudimos ejecu a lo con odas las posibles pe mu aciones de los 4 campos. Adem´as,
pa a odas es as pe mu aciones hicimos el algo i mo usando los 2,3 y 4 p ime os elemen os de
o den pa a obse a como e olucionaba el cos e y la p ecisi´on al i e a m´as sob e ´el. Usa emos
la siguien e no aci´on pa a los campos de es e da ase : el campo 0 co esponde a ID, el campo 1
a apellido, el 2 a nomb e y el 3 a echa de nacimien o. Todos es os da os ob enidos los amos a
p esen a en las ablas 5, 4 y 3 . Es os da os ue on ob enidos usando como p ocesado un i7-10510U.
O den Tiempo (s) De ecciones De ecciones/ o al ( %)
[0,1,2,3] 53.10 11984 33.96
[0,1,3,2] 53.86 11984 33.96
[0,2,1,3] 50.34 11984 33.96
[0,2,3,1] 48.30 11984 33.96
[0,3,1,2] 53.15 11984 33.96
[0,3,2,1] 49.64 11984 33.96
[1,0,2,3] 30.39 11985 33.97
[1,0,3,2] 31.45 11985 33.97
[1,2,0,3] 36.63 11986 33.97
[1,2,3,0] 35.92 11986 33.97
[1,3,0,2] 35.51 11986 33.97
[1,3,2,0] 39.21 11986 33.97
[2,0,1,3] 41.12 11982 33.96
[2,0,3,1] 41.55 11985 33.97
[2,1,0,3] 45.76 11985 33.97
[2,1,3,0] 48.09 11985 33.97
[2,3,0,1] 46.23 11986 33.97
[2,3,1,0] 45.93 11985 33.97
[3,0,1,2] 29.75 11985 33.97
[3,0,2,1] 29.68 11985 33.97
[3,1,0,2] 33.42 11986 33.97
[3,1,2,0] 38.16 11986 33.97
[3,2,0,1] 37.12 11986 33.97
[3,2,1,0] 34.79 11986 33.97
Tabla 3: Ejecuci´on de nues o algo i mo con 4 i e aciones pa a odas las combinaciones de o den
posibles. Rema camos en neg i a los mejo es esul ados en iempo de ejecuci´on.
Pa a comen a es os da os, debemos p ime o menciona que el iempo de ejecuci´on no e a el
mismo siemp e, si no que depend´ıa de los p ocesos del o denado , a iando al ededo de un 20 %
de los alo es p opo cionados. Obse ando el algo i mo con 4 i e aciones, obse amos que, inde-
pendien emen e del o den, siemp e llegamos a una si uaci´on simila , con un n´ume o casi igual de
elemen os anexionados. Lo que si a ´ıa son los iempos de ejecuci´on, a iando desde 29 segundos
en las i e aciones m´as ´apidas a 53 segundos en las m´as len as. Es a di e encia no se debe a la a-
iabilidad que hemos comen ado, de al ededo del 20 %, si no que se debe al ama˜no de los bucke s
23
O den Tiempo (s) De ecciones De ecciones/ o al ( %)
[0,1,2] 54.12 11973 33.93
[0,1,3] 40.18 11984 33.96
[0,2,1] 46.42 11973 33.93
[0,2,3] 47.73 11977 33.94
[0,3,1] 37.15 11984 33.96
[0,3,2] 52.13 11977 33.94
[1,0,2] 29.45 11973 33.93
[1,0,3] 20.10 11985 33.97
[1,2,0] 36.10 11973 33.93
[1,2,3] 13.79 11955 33.88
[1,3,0] 24.96 11985 33.97
[1,3,2] 15.84 11955 33.88
[2,0,1] 39.43 11971 33.93
[2,0,3] 40.15 11975 33.94
[2,1,0] 43.82 11971 33.93
[2,1,3] 26.85 11954 33.88
[2,3,0] 45.77 11976 33.94
[2,3,1] 25.86 11955 33.88
[3,0,1] 19.15 11985 33.97
[3,0,2] 28.99 11978 33.95
[3,1,0] 23.03 11986 33.97
[3,1,2] 13.91 11955 33.88
[3,2,0] 36.23 11974 33.94
[3,2,1] 14.51 11955 33.88
Tabla 4: Ejecuci´on de nues o algo i mo con 3 i e aciones pa a odas las combinaciones de o den
posibles. Rema camos en neg i a los mejo es esul ados en iempo de ejecuci´on.
gene ados du an e el algo i mo. Po ello hemos insis ido en lo ele an e de una buena elecci´on de
o den de ejecuci´on.
Es a ele ancia queda a´un m´as palpable en el caso de ejecuciones con 3 i e aciones. En es e caso,
obse amos que la di e encia en las ejecuciones m´as ´apida y m´as len a es mayo , unos 14 segundos
en e a 54 segundos. Adem´as, ambi´en obse amos que las ejecuciones m´as ´apidas se p oducen
cuando el p ime elemen o del o den es o bien 1 o bien 3, lo que nos indica que son mejo es campos
pa a abaja es e algo i mo. Tambi´en obse amos que con 3 i e aciones, los n´ume os de egis os
anexionados, si bien muy simila es, ya no son an homog´eneos. Hay a ias di e encias que nos hacen
e que el o den es ele an e siemp e y cuando no es emos i e ando sob e odos los campos, donde
su e ec o es p ´ac icamen e desp eciable.
Finalmen e si obse amos las ejecuciones con 2 i e aciones, emos ampli icada la a iabilidad en
iempo de ejecuci´on y esul ado ob enido. Nue amen e los m´as ´apidos son aquellos con los campos
1 y 3, que son adem´as los que ob ienen mejo es esul ados en 2 i e aciones.
Pa a e po qu´e un campo esul a mejo que o o pa a ealiza las ejecuciones del algo i mo
podemos analiza la dis ibuci´on de las en adas de dichos campos. Tomando como dis ibuci´on a
24
ejecu a lo. Buscamos usa como cla e campos que engan una dis ibuci´on con poca des iaci´on con
espec o a su alo medio, de o ma que gene en bucke s no muy g andes pe o lo su icien emen e
g andes pa a que puedan ealiza se compa aciones y se consigan ealiza anexiones de egis os.
Adem´as, el cos e compu acional ob enido pa a 3 y 4 i e aciones no es su icien emen e escalable
cuando ejecu amos en una ´unica m´aquina, al ene un exponen e de c ecimien o al ededo de 2.
´
Unicamen e esul a e dade amen e escalable en el caso de 2 i e aciones, donde se hace uso p ecisa-
men e de es e ipo de campos, log ando un exponen e al ededo de 1. As´ı, la e icacia del algo i mo
queda subo dinada a la exis encia de es e ipo de campos en el da ase .
Pese a que en una ´unica m´aquina el algo i mo no sea escalable sal o haciendo uso de los campos
con buenas p opiedades, cuando lo ejecu amos en el en o no pa a el cual es ´a dise˜nado, un clus e
de o denado es, el exponen e de c ecimien o ce cano a 1 hace que se uel a escalable incluso cuando
usamos 4 i e aciones. Es o nos indica que si hacemos un uso comple o de una de las ca ac e ´ıs icas
undamen ales del algo i mo como es la pa alelizaci´on, el obje i o de escalabilidad se cumple.
Como posibles mejo as al algo i mo p esen ado, hay una muy cla a. El algo i mo no pa ale-
lizado se espe a que enga un cos e compu acional ce cano a un exponen e 2. En cambio, el que
hemos ob enido noso os es ap oximadamen e 3. Es o nos indica que la unci´on que ealiza las
ope aciones de ma ch y me ge a´un iene cabida a se op imizado pa a educi el cos e global del
algo i mo. Espe amos que as ealiza una mejo a de es e ipo, el cos e del algo i mo desa olla-
do se e ´a educido igualmen e, aunque en meno p opo ci´on que lo haga la e si´on no pa alelizada.
O a posible mejo a que pod ´ıa ealiza se es a a de au oma iza la selecci´on de los pa ´ame os
usados, en especial del o den. Median e el an´alisis es ad´ıs ico del da ase , po ejemplo, pod ´ıamos
se capaces de hace esa selecci´on de o ma ´op ima. Al se an sensible a una co ec a elecci´on del
pa ´ame o de o den, da la opci´on de basa es a elecci´on en una se ie de da os obje i os pe mi e
que el usua io inal que quie a hace uso del algo i mo no enga po qu´e ene un conocimien o an
p o undo del da ase . El es ablecimien o de las eglas es ad´ıs icas conc e as que deben egi esa
elecci´on de pa ´ame os queda ue a de los obje i os de es e abajo, pe o puede esul a un es udio
e´o ico in e esan e pa a op imiza el uncionamien o del algo i mo.
31

7. Bibliog a ´ıa
[1] Vassilis Ch is ophides y col. “End- o-end en i y esolu ion o big da a: A su ey”. En: a Xi
p ep in a Xi :1905.06397 (2019).
[2] Dimas Cassimi o do Nascimen o, Ca los Edua do San os Pi es y Deme io Gomes Mes e.
“Exploi ing block co-occu ence o con ol block sizes o en i y esolu ion”. En: Knowl. In .
Sys . 62.1 (2020), p´ags. 359-400. doi:10.1007/s10115-019-01347-0.u l:h ps://doi.
o g/10.1007/s10115-019-01347-0.
[3] Luciano Ba bosa. “Lea ning ep esen a ions o Web en i ies o en i y esolu ion”. En: IJWIS
15.3 (2019), p´ags. 346-358. doi:10.1108/IJWIS-07-2018-0059.u l:h ps://doi.o g/10.
1108/IJWIS-07-2018-0059.
[4] Chenchen Sun y col. “A gene ic algo i hm based en i y esolu ion app oach wi h ac i e lea -
ning”. En: F on ie s Compu . Sci. 11.1 (2017), p´ags. 147-159. doi:10.1007/s11704-015-
5276-6.u l:h ps://doi.o g/10.1007/s11704-015-5276-6.
[5] Muhammad Sadiq y col. “A Ve ex Ma che o En i y Resolu ion on G aphs”. En: 14 h
In e na ional Con e ence on Ubiqui ous In o ma ion Managemen and Communica ion, IM-
COM 2020, Taichung, Taiwan, Janua y 3-5, 2020. IEEE, 2020, p´ags. 1-4. doi:10.1109/
IMCOM48794.2020.9001799.u l:h ps://doi.o g/10.1109/IMCOM48794.2020.9001799.
[6] Oma Benjelloun y col. “Swoosh: a gene ic app oach o en i y esolu ion”. En: VLDB J. 18.1
(2009), p´ags. 255-276. doi:10.1007/s00778-008-0098-x.u l:h ps://doi.o g/10.1007/
s00778-008-0098-x.
[7] Pe e Ch is en. “A Compa ison o Pe sonal Name Ma ching: Techniques and P ac ical Issues”.
En: Wo kshops P oceedings o he 6 h IEEE In e na ional Con e ence on Da a Mining (ICDM
2006), 18-22 Decembe 2006, Hong Kong, China. IEEE Compu e Socie y, 2006, p´ags. 290-294.
doi:10.1109/ICDMW.2006.2.u l:h ps://doi.o g/10.1109/ICDMW.2006.2.
32