Graph-Based Indexing for Fingerprint Identification Systems

• João Contreras UNICAMP
• André Nóbrega UNICAMP
• Pascual Figueroa Griaule
• Alexandre Falcão UNICAMP

Resumo

Automated fingerprint identification systems traditionally compare a query against all stored records to identify a match, resulting in a computational burden that is impractical for large-scale fingerprint databases. To address this challenge, indexing techniques are crucial for reducing the search space and accelerating the identification process. This paper introduces a flexible fingerprint indexing framework based on Hierarchical Navigable Small World (HNSW) graphs, a state-of-the-art algorithm for approximate nearest neighbor search. The strength of HNSW relies on its ability to operate beyond metric spaces by supporting arbitrary similarity functions. We demonstrate such versatility through three distinct experimental setups: (1) indexing standard global feature vectors, (2) organizing an extensive collection of local, minutiae-based descriptors aggregated via majority voting, and (3) directly indexing proprietary biometric templates using the native, non-metric matching score of a Commercial-Off-The-Shelf (COTS) system. Our results show that HNSW significantly reduces similarity computations while maintaining high accuracy across all scenarios. Most notably, it minimizes the number of costly COTS matcher evaluations, establishing HNSW as a robust and adaptable solution for automated fingerprint identification systems.

Palavras-chave: Graphics, Accuracy, Databases, Fingerprint recognition, Nearest neighbor methods, Extraterrestrial measurements, Approximation algorithms, Vectors, Standards, Indexing