В данном техническом отчете представлена методология «Сертификация-затем-корректировка» (Certify-then-Rectify), которая объединяет скорость графов иерархического навигационного малого мира (HNSW) с теоретическими гарантиями корректности. Метод динамически оценивает качество поиска и при необходимости переходит к алгоритму точного восстановления, обеспечивая наихудшую точность.
- Испольбуется статистический сертифицир, не зависящий от распределения, для оценки качества поиска HNSW с минимальными накладными расходами.
- Переосмысливает граф HNSW как геометрический спаннер для ограничения максимального расстояния до истинных ближайших соседей.
- Применяет теорию экстремальных значений для стохастической оценки максимального эмпирического коэффициента растяжения.
- Обеспечивает среднюю скорость работы HNSW, сохраняя корректность в наихудшем случае, характерную для точного поиска.
Этот подход сокращает разрыв между эвристическим поиском и строгим извлечением данных, превосходя другие применимые подходы на тестовых наборах данных.