HNSW avec garanties de précision utilisant des spanneurs de graphes

Ce rapport technique présente un cadre « Certify-then-Rectify » qui combine la vitesse des graphes HNSW (Hierarchical Navigable Small World) avec des garanties de correction théoriques. La méthode évalue dynamiquement la qualité de la recherche et passe à un algorithme de récupération exact si nécessaire, garantissant une précision dans le pire des cas.

• Utilise un vérificateur statistique indépendant de la distribution pour évaluer la qualité de la recherche HNSW avec un surcoût minimal.
• Réinterprète le graphe HNSW comme un spanneur géométrique pour borner la distance maximale des plus proches voisins réels.
• Applique la théorie des valeurs extrêmes pour estimer stochastiquement le facteur d'étirement empirique maximal.
• Offre la vitesse en moyenne de HNSW tout en maintenant la correction dans le pire des cas de la recherche exacte.

Cette approche comble l'écart entre la recherche heuristique et la récupération rigoureuse, surpassant les autres approches applicables sur les ensembles de données de référence.