Tecniche per l’Integrazione di Sorgenti Big Data in Ambienti di Calcolo Distribuito

Data sources that provide a huge amount of semi-structured data are available on Web as tables, annotated contents (e.g. RDF) and Linked Open Data. These sources can constitute a valuable source of information for companies, researchers and government agencies, if properly manipulated and integrated with each other or with proprietary data. One of the main problems is that typically these sources are heterogeneous and do not come with keys to perform join operations, and effortlessly linking their records. Thus, finding a way to join data sources without keys is a fundamental and critical process of data integration. Moreover, for many applications, the execution time is a critical component (e.g., in finance of national security context) and distributed computing can be employed to significantly it. In this dissertation, I present distributed data integration techniques that allow to scale to large volumes of data (i.e., Big Data), in particular: SparkER and GraphJoin. SparkER is an Entity Resolution tool that aims to exploit the distributed computing to identify records in data sources that refer to the same real-world entity—thus enabling the integration of the records. This tool introduces a novel algorithm to parallelize the indexing techniques that are currently state-of-the-art. SparkER is a working software prototype that I developed and employed to perform experiments over real data sets; the results show that the parallelization techniques that I have developed are more efficient in terms of execution time and memory usage than those in literature. GraphJoin is a novel technique that allows to find similar records by applying joining rules on one or more attributes. This technique combines similarity join techniques designed to work on a single rule, optimizing their execution with multiple joining rules, combining different similarity measures both token- and character- based (e.g., Jaccard Similarity and Edit Distance). For GraphJoin I developed a working software prototype and I employed it to experimentally demonstrate that the proposed technique is effective and outperforms the existing ones in terms of execution time.

Sorgenti che forniscono grandi quantitativi di dati semi-strutturati sono disponibili sul Web in forma di tabelle, contenuti annotati (e.s. RDF) e Linked Open Data. Questi dati se debitamente manipolati e integrati tra loro o con dati proprietari, possono costituire una preziosa fonte di informazione per aziende, ricercatori e agenzie governative. Il problema principale in fase di integrazione è dato dal fatto che queste sorgenti dati sono tipicamente eterogenee e non presentano chiavi su cui poter eseguire operazioni di join per unire facilmente i record. Trovare un modo per effettuare il join senza avere le chiavi è un processo fondamentale e critico dell’integrazione dei dati. Inoltre, per molte applicazioni, il tempo di esecuzione è una componente fondamentale (e.s. nel contesto della sicurezza nazionale) e il calcolo distribuito può essere utilizzato per ridurlo sensibilmente. In questa dissertazione presento delle tecniche distribuite per l’integrazione dati che consentono di scalare su grandi volumi di dati (Big Data), in particolare: SparkER e GraphJoin. SparkER è un tool per Entity Resolution che mira ad utilizzare il calcolo distribuito per identificare record che si riferiscono alla stessa entità del mondo reale, consentendo così l’integrazione di questi record. Questo tool introduce un nuovo algoritmo per parallelizzare le tecniche di indicizzazione che sono attualmente lo stato dell’arte. SparkER è un prototipo software funzionante che ho sviluppato e utilizzato per eseguire degli esperimenti su dati reali; i risultati ottenuti mostrano che le tecniche di parallelizzazione che ho sviluppato sono più efficienti in termini di tempo di esecuzione e utilizzo di memoria rispetto a quelle già esistenti in letteratura. GraphJoin è una nuova tecnica che consente di trovare record simili applicando delle regole di join su uno o più attributi. Questa tecnica combina tecniche di join similarity pensate per lavorare su una singola regola, ottimizzandone l’esecuzione con più regole, combinando diverse misure di similarità basate sia su token che su caratteri (e.s. Jaccard Similarity e Edit Distance). Per il GraphJoin ho sviluppato un prototipo software funzionante e l’ho utilizzato per eseguire esperimenti che dimostrano che la tecnica proposta è efficace ed è più efficiente di quelle già esistenti in termini di tempo di esecuzione.