Publikace detail

Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter

Autoři: Rozinek Ondřej | Marek Jaroslav | Panuš Jan | Mareš Jan

Rok: 2025

Druh publikace: článek v odborném periodiku

Název zdroje: Algorithms

Strana od-do: 1-32

Tituly:

Jazyk	Název	Abstrakt	Klíčová slova
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í ≈𝒪(1). Ve druhé fázi běží FRMS po polynomiální dobu přibližně ≈𝒪(𝑛4) 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 ≈𝒪(1). In the second stage, FRMS runs for a polynomial time of approximately ≈𝒪(𝑛4) 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

Vyhledávání

Přihlášení pro studenty

Přihlášení pro zaměstnance

Publikace detail

Katedry

Služby

Jak nás najdete?

Často hledáte