Approximate Nearest Neighbor Search in Recommender Systems

In February 2024, Yury Malkov discussed Approximate Nearest Neighbor (ANN) and its key role in recommender systems at the SF Unstructured Data Meetup. ANN search is already integrated into the production stacks of popular tools worldwide. The talk covered the key concepts and background that have driven ANN's adoption in large-scale recommender systems. Yuri Malkov, a genius physicist, laser researcher, and inventor of HNSW (a graph-based indexing algorithm), now works as a Research Scientist for OpenAI. ANN search algorithms use various indexing techniques to return approximate nearest neighbors, making them core to many applications and technologies that are customer facing today. From search engines like Google to social media sites, ANN and recommender systems are already integrated through the stack in production. Yuri notes that many mature ANN solutions exist, including LSH, graph-based indexes like HNSW and SCANN, quantization-based indices like IVF_PQ and IVF_HSNW, DiskANN, and ANNOY. ANN benchmarking is done through platforms like ANNBenchmarks, which evaluate various approximate nearest neighbor search algorithms and provide results split by distance measure and dataset on their website. The performance metrics include recall rate and queries per second (QPS). More QPS indicates better performance. The Milvus team built Knowhere, an open-source vector execution engine that incorporates several vector similarity search libraries like Faiss, Hnswlib, and Annoy. It controls on which hardware (CPU or GPU) to execute index building and search requests. Cardinal is Zilliz's core vector search engine, offering a threefold increase in performance compared to the previous version. Recommender systems have large market potential due to their ability to generate consumer behavior. Typical challenges at scale include generability, handling huge corpuses, and efficiency. Traditional recommender systems use a multi-staged funnel approach with candidate generation, lightweight ranking, and full ranking stages. Novel solutions for item-query incompatibility include L2 distance on data vectors, bipartite graph ranking, text-focused graph re-ranking, and cascaded graph search. ANN algorithms have seen extensive implementation due to their good enough matching, flexibility, and maturity. Further resources are available through Yury Malkov's talk on YouTube.