What is the cost of performing sequential search for kNN queries. Or the average number of comparisons to obtain the kNN records.
1 Answer
If you seek the best optimal top-k scores, then you should scan all candidate items. In other words, perform a full scan. If you are willing to retrieve "nearly" the best scores, you can apply an approximated kNN search. There are several approximated kNN indexing algorithms: LSH, HNSW, PQ, IVF, etc. You can use open-source code libraries such as Faiss, NMSLib, Annoy; Open-source cloud tools such as Jina; Or managed services such as AWS elastic-search and Pinecone.io.