Комментарии 2
А теперь внимание: нам неважно в каком порядке обходить эти 
документов. И поэтому мы можем их обходить в порядке физического расположения.
Получается, при k<C, мы всегда будем получать одну и ту же выдачу, даже при добавлении новых и более актуальных документов? Просто потому что они будут записаны после более старых.
Когда добавляются новые документы и создается новый сегмент, информация о его neighbors set-ах становится доступной и если там есть более перспективные neighbors set-ы документов для данного запроса, то они будут просмотрены и попадут в этот C кандидатов. Ну и понятно, что C >= k всегда иначе же топ не набрать.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Дизайн встраиваемой базы данных для ANN запросов: MusyaDB