EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Ondřej Rozinek, Jaroslav Marek, Jan Panuš, Jan Mareš

Algorithms · 06.03.2025 · 18 (3) · 150

DOI: 10.3390/a18030150 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Algorithms, online erschienen am 06.03.2025. Verfasst von Ondřej Rozinek und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 61 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 ≈O(1). In the second stage, FRMS runs for a polynomial time of approximately ≈O(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.

Zitieren

APA

Rozinek, O., Marek, J., Panuš, J., & Mareš, J. (2025). Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter. Algorithms, 18(3), 150. https://doi.org/10.3390/a18030150

Vancouver

Rozinek O, Marek J, Panuš J, Mareš J. Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter. Algorithms. 2025;18(3):150. doi:10.3390/a18030150

BibTeX
@article{Rozinek2025,
  author = {Rozinek, Ondřej and Marek, Jaroslav and Panuš, Jan and Mareš, Jan},
  title = {Real-Time Fuzzy Record-Matching Similarity Metric and Optimal Q-Gram Filter},
  journal = {Algorithms},
  year = {2025},
  volume = {18},
  number = {3},
  pages = {150},
  doi = {10.3390/a18030150}
}
Kostenlos starten →