Vlákno názorů k článku Knihovna FAISS a embedding: základ jazykových modelů (3. část – role indexů) od atarist - Takze jestli to chapu dobre, tak vsechny ty...

Takze jestli to chapu dobre, tak vsechny ty indexy maji linearni slozitost a stahnout to nejde? (jasne, to je teorie, v praxi dava vyznam mit sice stejnou slozitost, ale prakticky o rad mensi casy,...)

Ne, ta složitost nemusí být lineární.

Třeba u toho IVF je to triviálně odmocnina -- člověk si vytvoří Θ(√n) regionů, takže v první fázi v čase Θ(√n) najde nejbližší region a ten pak prohledá v čase Θ(n/√n)=Θ(√n). (Většinou těch regionů chcete prohledávat víc, řekněme k, tak jich vytvoříte Θ(√kn) a opět vyjde složitost hledání jako Θ(√kn).)

Podle https://en.wikipedia.org/wiki/Hierarchical_navigable_small_world je složitost HNSW dokonce logaritmická (je to v základu prohledávání stromu logaritmické hloubky).

Ty indexy jsou aproximativní, takže je to vždy nějaký trade-off mezi rychlostí hledání a přesností hledání. Stáhnout složitost pod lineární samozřejmě jde, v extrémním případě můžu mít index, který bude vybírat výsledky náhodně se složitostí O(1). Ano, bude to prakticky k ničemu a přesnost hledání bude hodně špatná, ale bude to index se složitostí O(1).

Dobrý benchmark indexů je zde: https://github.com/erikbern/ann-benchmarks