Evaluierung und Erweiterung von MapReduce-Algorithmen zur Berechnung der transitiven Hülle ungerichteter Graphen für Entity Resolution Workflows

Authors: 
Sehili, Ziad
Year: 
2013
Language: 
German
Abstract: 
Im Bereich von Entity-Resolution oder deduplication werden aufgrund fehlen- der global eindeutiger Identifikatoren Match-Techniken verwendet, um zu bestimmen, ob verschiedene Datensätze dasselbe Realweltobjekt darstellen. Die inhärente quadratische Komplexität führt zu sehr langen Laufzeiten für große Datenmengen, was eine Parallelisierung dieses Prozesses erfordert. MapReduce ist wegen seiner Skalierbarkeit und Einsetzbarkeit in Cloud- Infrastrukturen eine gute Lösung zur Verbesserung der Laufzeit. Außerdem kann unter bestimmten Voraussetzungen die Qualität des Match-Ergebnisses durch die Berechnung der transitiven Hülle verbessert werden. Die Berech- nung der transitiven Hülle eines Graphen ist von Natur aus ein iterativer Prozess. Ein naiver Ansatz berechnet sie linear, i.e. nach d Iterationen, wobei d die Tiefe des Graphen ist. In dieser Arbeit wird am Beispiel der Entity Resolution die Verwendung von MapReduce für die iterative und verteilte Berechnung der transitiven Hülle untersucht. Der vorgeschlagene Algorithmus Smart-MR operiert nur auf azyklischen Graphen und konvergiert nach genau log d Iterationen. Die drei weiteren Algorithmen Cyc-Smart-MR , Full-TC-MR und CC-MR arbeiten alle auf beliebigen ungerichteten Graphen und weisen ebenso ein logarithmisches Verhalten auf.
AttachmentSize
trasitive_closure_with_mapreduce.pdf2.65 MB