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

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216275%3A25530%2F25%3A39922812" target="_blank" >RIV/00216275:25530/25:39922812 - isvavai.cz</a>

Výsledek na webu

<a href="https://www.mdpi.com/1999-4893/18/3/150" target="_blank" >https://www.mdpi.com/1999-4893/18/3/150</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3390/a18030150" target="_blank" >10.3390/a18030150</a>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Algorithms

ISSN

—

e-ISSN

1999-4893

Svazek periodika

18

Číslo periodika v rámci svazku

3

Stát vydavatele periodika

CH - Švýcarská konfederace

Počet stran výsledku

32

Strana od-do

1-32

Kód UT WoS článku

001453394600001

EID výsledku v databázi Scopus

2-s2.0-105001107106