Large scale deduplication based on fingerprints
In fingerprint-based systems, the size of databases increases considerably with population growth. In developing countries, because of the difficulty in using a central system when enlisting voters, it often happens that several regional voter databases are created and then merged to form a central database. A process is used to remove duplicates and ensure uniqueness by voter. Until now, companies specializing in biometrics use several costly computing servers with algorithms to perform large-scale deduplication based on fingerprints. These algorithms take a considerable time because of their complexity in O (n2), where n is the size of the database. This article presents an algorithm that can perform this operation in O (2n), with just a computer. It is based on the development of an index obtained using a 5 * 5 matrix performed on each fingerprint. This index makes it possible to build clusters of O (1) in size in order to compare fingerprints. This approach has been evaluated using close to 11 4000 fingerprints, and the results obtained show that this approach allows a penetration rate of less than 1%, an almost O (1) identification, and an O (n) deduplication. A base of 10 000 000 fingerprints can be deduplicated with a just computer in less than two hours, contrary to several days and servers for the usual tools. Keywords: fingerprint, cluster, index, deduplication.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LSHBloom: Memory-efficient, Extreme-scale Document Deduplication
Deduplication is a major focus for assembling and curating training datasets for large language models (LLM) -- detecting and eliminating additional instances of the same content -- in large collections of technical docu…
MemorizationPrivacy-Preserving Data Deduplication for Enhancing Federated Learning of Language Models (Extended Version)
Deduplication is a vital preprocessing step that enhances machine learning model performance and saves training time and energy. However, enhancing federated learning through deduplication poses challenges, especially re…
Federated LearningPrivacy PreservingMLT-Dedup: Efficient Large-Scale Online Video Deduplication via Multi-Level Representations and Spatial-Temporal Matching
The explosive growth of user-generated video content on online platforms is accompanied by the emergence of numerous near-duplicate videos--videos that are identical or highly similar but differ by partial edits. These d…
A Robust and Efficient Pipeline for Enterprise-Level Large-Scale Entity Resolution
Entity resolution (ER) remains a significant challenge in data management, especially when dealing with large datasets. This paper introduces MERAI (Massive Entity Resolution using AI), a robust and efficient pipeline de…
Entity ResolutionMeasuring Bias of Web-filtered Text Datasets and Bias Propagation Through Training
We investigate biases in pretraining datasets for large language models (LLMs) through dataset classification experiments. Building on prior work demonstrating the existence of biases in popular computer vision datasets,…