Progettazione di una base di dati per il calcolo della similarità tra documenti

The exponential growth of textual content on the Web has made the detection of duplicate and near-duplicate documents a central problem for search engines, indexing systems, and content management platforms. This work presents the design and implementation of a database application for the automatic computation of similarity in large collections of documents, based on dimensionality reduction techniques using MinHash signatures and Locality-Sensitive Hashing (LSH). The system was tested on a real dataset extracted from Common Crawl and compared with an equivalent implementation based on the File System. The project covers the entire development cycle of an information system: from requirements analysis, to conceptual design (Entity-Relationship schema) and logical database design, up to the selection of indexes and physical implementation using SQLite. The application, developed in Python, uses parallel processing for data acquisition and signature computation, and supports operations such as the insertion of new documents, the generation of MinHash signatures, indexing through LSH bands, and the efficient retrieval of pairs of similar documents. The direct performance comparison between the DBMS-based architecture and the equivalent File System implementation quantifies the benefits of relational indexes for query operations, with performance improvements of up to three orders of magnitude.

La crescita esponenziale dei contenuti testuali sul Web ha reso il rilevamento di documenti duplicati e quasi duplicati un problema centrale per i motori di ricerca, i sistemi di indicizzazione e le piattaforme di gestione dei contenuti. Questo lavoro presenta la progettazione e l'implementazione di un'applicazione di base di dati per il calcolo automatico della similarità in grandi collezioni di documenti, basata su tecniche di riduzione della dimensionalità che utilizzano le firme MinHash e la Locality-Sensitive Hashing (LSH). Il tutto è stato testato su un dataset reale estratto da Common Crawl e comparato con un'elaborazione equivalente eseguita sul File System. Il progetto copre l'intero ciclo di sviluppo di un sistema informativo: dall'analisi dei requisiti, alla progettazione concettuale (schema Entità-Associazioni) e logica della base di dati, fino alla scelta degli indici e all'implementazione fisica in SQLite. L'applicazione, sviluppata in Python, utilizza l'elaborazione parallela per l'acquisizione dei dati ed il calcolo delle firme, e gestisce operazioni quali l'inserimento di nuovi documenti, la generazione delle firme MinHash, l'indicizzazione tramite bande LSH ed il recupero efficiente delle coppie di documenti simili. Il confronto diretto delle prestazioni tra l'architettura basata sul SGBD e l'implementazione equivalente basata solo su File System, quantifica il vantaggio degli indici relazionali nelle operazioni di interrogazione, osservando dei miglioramenti pari a fino a tre ordini di grandezza.