A tree-based blocking technique for record linkage in data integration

Entity Resolution (ER) is the task of identifying different entity profiles that describe the same real-world object. It is a core task for Data Integration, applicable to any kind of data, from structured sources like relational databases to semi-structured ones like the Linked Open Data Cloud and the unstructured ones like free text. From a high level perspective, ER consists of two parts: the search step, which determines the entities that will be compared the decision step, which compares the selected entities to determine whether they represent the same real-world object. The latter step is also called Entity Matching and involves time-consuming operations, called pairwise comparisons, which typically apply string similarity measures to pairs of entities, dominating the overall cost of ER. Blocking is a technique that takes care of the search step, which is the crucial part of the process with respect to efficiency and scalability. The block building process receives as input one or more entity collections and produces as output a block collection B; only the elements within the same block will be compared with each other. Without it, ER suffers from a quadratic time complexity, i.e.,O(n2), as every element has to be compared with all others. We found that a tree based approach was only used by a single filtering algorithm named Trie-Join. The starting point of this thesis was to investigate strengths and weaknesses of a tree based blocking algorithm, trying to boost its performance to a point where it could be used in a real world scenario. More in detail we first tried to use the Query Reverse Engineering framework to cope with the blocking step, to be able to discover the hidden relations behind each formed block, providing a data analysis tool for the end user. To reach good performances it revealed necessary to move away from a strict tree-based approach, adopting more relaxed constraints. The end result is TIS Scoring, a blocking algorithm with discrete performances, and with a working mechanism pretty different from a tree based approach.

Si definisce Entity Resolution (ER) il processo di identificazione delle diverse entità che si riferiscono allo stesso oggetto del mondo reale. È un compito fondamentale per l'integrazione dei dati, applicabile a qualsiasi tipo di dati, da fonti strutturate come database relazionali a quelle semi-strutturate come il Linked Open Data Cloud e quelle non strutturate come il testo libero. Da una prospettiva di alto livello, ER è costituito da due parti: il passaggio di ricerca, che determina quali entità verranno confrontate tra loro la fase decisionale, che confronta le entità selezionate per determinare se rappresentano lo stesso oggetto del mondo reale. Quest'ultimo passaggio è anche chiamato Entity Matching e comporta operazioni dispendiose in termini di tempo. Questo costo temporale è dominato dai numerosi confronti a coppie da operare, applicando misure di somiglianza che in larga scala possono essere computazionalmente costose. Il blocking è una tecnica che si occupa della prima fase, quella di ricerca, che è la parte cruciale del processo in termini di efficienza e scalabilità. Il processo di creazione del blocco riceve come input una o più collezioni di entità e produce come output una raccolta blocchi B; solo gli elementi all'interno dello stesso blocco verranno confrontati tra loro nella fase decisionale. Senza blocking, ER soffre di una complessità temporale quadratica, cioè O (n2), poiché ogni elemento deve essere confrontato con tutti gli altri. Abbiamo notato che nel panorama di algoritmi a disposizione, l'approccio ad alberi era utilizzato esclusivamente da una tecnica di Filtering, chiamato Trie-Join. Il punto di partenza di questa tesi è stato quello di indagare i punti di forza e di debolezza di un algoritmo ad alberi applicato al blocking, cercando successivamente di aumentare le sue prestazioni fino ad ottenere un algoritmo utilizzabile in uno scenario del mondo reale. Più in dettaglio, abbiamo prima cercato di utilizzare il framework Query Reverse Engineering per la creazione dei blocchi: questo permette di scoprire possibili relazioni nascoste dietro ogni blocco costruito, fornendo uno strumento di data analysis per l'utente finale. Dato un database D ed una tabella di risultati T, l'obiettivo di QRE è ricavare una o più query che eseguite su D ritornino T. Per fare questo QRE costruisce un albero decisionale, traducendo i vari split in predicati della query. Questa tecnica si è dimostrata abbastanza inefficace, e per raggiungere buone prestazioni si è rivelato necessario allontanarsi da un approccio ad alberi rigoroso, adottando vincoli più rilassati. L'algoritmo successivamente sviluppato è TIS (Tree Index Similarity, capitolo 4.2.2), che introduce una nuova metrica di somiglianza ad indici, rivelatasi molto efficace pur soffrendo di un costoso preprocessing. Mantenendo questa nuova metrica, il meccanismo di preprocessing è stato successivamente ampliato ed anche la parte di esecuzione è stata rivista di conseguenza: il risultato finale è TIS Scoring, un algoritmo di blocking con discrete prestazioni, e con un meccanismo di funzionamento abbastanza diverso da un approccio ad alberi.