Pronalaženje sličnih tekstualnih dokumenata primjenom algoritama sažimanja osjetljivih na bliskost

undergraduate thesis

• Title (english): Finding Similar Text Documents Using Locality Sensitive Hashing Algorithms
• Author: Luka Mandić
• Mentor: Marin Šilić (mentor)
• Committee member: Marin Šilić (predsjednik povjerenstva)
• Committee member: Petar Afrić (član povjerenstva)
• Committee member: Lucija Šikić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2020-07-03, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Pronalaženje sličnih tekstualnih dokumenata u velikim skupovima podataka kompleksan je problem zbog složenosti O(n2). Potrebno je puno operacija usporedbe parova dokumenata da bi se pronašli slični dokumenti. Algoritmima za sažimanje osjetljivim na bliskost operacija usporedbe dva dokumenta pojednostavljuje se i ubrzava ukupno vrijeme izvođenja programa. SimHash i MinHash algoritmi za sažimanje omogućuju izradu sažetaka osjetljivih na bliskost. SimHash sažetak stvara se na temelju distribucije riječi u dokumentu. MinHash sažetak gradi se na temelju vjerojatnosti pojavljivanja riječi u dokumentu. Umjesto uspoređivanja stavaka dokumenta uspoređuju se sažetci. Dodatno poboljšanju brzine izvođena doprinosi primjena LSH algoritma. LSH algoritmom određuju se kandidati za svaki dokument. Kandidati su dokumenti koji imaju sličnost barem s. Sličnost s manja je od sličnosti koje se kasnije pronalazi. Kod pronalaska sličnih dokumenata za određeni dokument uspoređuju se sažetci dokumenata koji su kandidati, a ne svi ostali sažetci dokumenata iz cijelog skupa podataka. Vrijeme izvođenja programa smanjuje se sa nekoliko sati na 1 minutu korištenjem algoritama sažimanja osjetljivih na bliskost MinHash i SimHash, te LSH algoritma za određivanje kandidata.

Abstract (english)

Finding of similar textual documents in very large amount of data is very complicated problem because of complexity O(n2). In order to find the similar documents, there are needed many comparison iterations of pairs of textual documents. Using proximity sensitive compression algorithms, the comparison of two documents is very simplified and in the same time, the comparison execution time is shorter. SimHash and MinHash algorithms for compression enable preparation of text data sets (summaries) which have proximity sensitive properties. SimHash data set (summary) is based on the distribution of words inside the text document. MinHash data set (summary) is based on probability of words occurrence inside the text document. Instead of text items comparison, the main idea in this kind of data mining in large number of text documents is comparison of data sets (summaries). In order to additionally decrease the execution time, in parallel with SimHash and MinHash, there is the third algorithm used, LSH algorithm. The base of LSH algorithm is the definition of candidates for each text document. The candidates are the text documents, which have similarity level, at least s. Similarity s is lower of similarity, which are identified later, in the process of text document comparison. Using such approach, only the text documents, which are defined as candidates, are used in further steps of comparison of data sets (summaries), instead of comparison of data sets (summaries) of all input text documents.
The execution time needed for finding similar text documents in very large amount of data is decreased from couple of hours to 1 minute using proximity sensitive compression algorithms, MinHash and SimHash in combination with LSH algorithm for definition of candidates.

• Keywords: SimHash; MinHash; LSH; sažetak; kandidati; sličnost; tekstualni dokumenti; veliki podatci; skup podataka; stavke; hammingova udaljenost
• Keywords (english): SimHash; MinHash; LSH; shingling; similarity; dataset; candidates; datamining; hammingDistance; similar_pairs; comparison; big data
• Language: croatian
• URN:NBN: urn:nbn:hr:168:690097
• Study programme: Title: Computing; Study programme type: university; Study level: undergraduate; Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-14 09:22:33