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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

—

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2025

Confidentiality

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

Name of the periodical

Algorithms

ISSN

—

e-ISSN

1999-4893

Volume of the periodical

18

Issue of the periodical within the volume

3

Country of publishing house

CH - SWITZERLAND

Number of pages

32

Pages from-to

1-32

UT code for WoS article

001453394600001

EID of the result in the Scopus database

2-s2.0-105001107106