Login for students

Login for employees

Publication detail

Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter
Authors: Rozinek Ondřej | Marek Jaroslav | Panuš Jan | Mareš Jan
Year: 2025
Type of publication: článek v odborném periodiku
Name of source: Algorithms
Page from-to: 1-32
Titles:
Language Name Abstract Keywords
cze Metrika podobnosti v reálném čase pro fuzzy porovnávání záznamů a optimální filtr Q-gramů V tomto článku představujeme pokročilou metriku podobnosti záznamů Fuzzy Record Similarity Metric (FRMS), která zlepšuje přibližné porovnávání záznamů a modeluje lidské vnímání podobnosti záznamů. FRMS využívá nově vyvinutý prostor podobnosti s příznivými vlastnostmi v kombinaci s metrickým prostorem a využívá model bag-of-words s obecnými aplikacemi v textovém dolování a klastrové analýze. Pro optimalizaci FRMS navrhujeme dvoustupňovou metodu pro přibližné porovnávání řetězců a vyhledávání, která překonává základní metody z hlediska průměrné časové složitosti a F-měry na různých datových sadách. V první fázi konstruujeme optimální filtr počtu Q-gramů jako optimální dolní hranici pro fuzzy podobnosti tokenů, jako je FRMS. Aproximovaný filtr počtu Q-gramů dosahuje vysoké přesnosti, filtruje přes 99 % odlišných záznamů, s konstantní časovou složitostí ~0(1). Ve druhé fázi běží FRMS po polynomiální dobu přibližně ~0(n4) a modeluje lidské vnímání podobnosti záznamů pomocí maximální váhové shody v bipartitním grafu. Architektura FRMS má široké uplatnění v ukládání strukturovaných dokumentů, jako jsou databáze, a již byla komercializována jednou z největších IT společností. Jako vedlejší výsledek vysvětlujeme chování singularity filtru Q-gramů a výhody rozšíření o doplnění. Celkově naše metoda poskytuje přesnější a efektivnější přístup k aproximativnímu porovnávání řetězců a vyhledávání v reálném čase. fuzzy shoda; Q-gramový filtr; přibližná shoda řetězců; propojení záznamů; rozlišení entit; prostor podobnosti
eng Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter In this paper, we introduce an advanced Fuzzy Record Similarity Metric (FRMS) that improves approximate record matching and models human perception of record similarity. The FRMS utilizes a newly developed similarity space with favorable properties combined with a metric space, employing a bag-of-words model with general applications in text mining and cluster analysis. To optimize the FRMS, we propose a two-stage method for approximate string matching and search that outperforms baseline methods in terms of average time complexity and F measure on various datasets. In the first stage, we construct an optimal Q-gram count filter as an optimal lower bound for fuzzy token similarities such as FRMS. The approximated Q-gram count filter achieves a high accuracy rate, filtering over 99% of dissimilar records, with a constant time complexity of aproximate to 0(1). In the second stage, FRMS runs for a polynomial time of approximately approximate to 0(n4) and models human perception of record similarity by maximum weight matching in a bipartite graph. The FRMS architecture has widespread applications in structured document storage such as databases and has already been commercialized by one of the largest IT companies. As a side result, we explain the behavior of the singularity of the Q-gram filter and the advantages of a padding extension. Overall, our method provides a more accurate and efficient approach to approximate string matching and search with real-time runtime. fuzzy matching; Q-gram filter; approximate string matching; record linkage; entity resolution; similarity space

Department

Map

en.mapy.cz

Services

Popular Links

© 2023 University of Pardubice, Studentská 95, 532 10 Pardubice 2
Phone: +420 466 036 111, 466 036 112, 466 036 113
Webmaster, RSS
Data box ID: f5vj9hu
Accessibility Statement
CC BY-NC-ND 4.0Creative CommonsAttributionNonCommercialNoDerivatives