提出高效稀疏向量近邻搜索算法，单核CPU实现亚毫秒级响应。
Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets
- 设计理论支撑的稀疏向量压缩算法，保留内积排序关系。
- 在大规模数据集上实现每查询亚毫秒延迟，准确率高。
- 适合需要快速检索稀疏语义向量的场景，如文本搜索。
稀疏数据嵌入因其内在可解释性而备受青睐：每个维度对应词汇表中的一个词，便于直观理解潜在空间。然而，稀疏性给近似最近邻搜索（ANNS）带来独特挑战——从向量集合中找出与查询最接近的k个向量。为推动该未充分探索领域的研究，稀疏ANNS成为NeurIPS 2023 BigANN挑战的核心议题，评估标准包括吞吐量和准确率。本文提出一系列新型数据结构与算法方法，结合后形成优雅、高效且有效的稀疏ANNS解决方案。贡献包括：理论上合理的稀疏向量压缩算法，降低有效维度同时保留内积诱导的排序；倒排索引的几何化组织；以及融合局部与全局信息以提升搜索效率与效果。实验表明，最终算法Seismic在单个CPU上对大规模基准数据集实现每查询亚毫秒级延迟，同时保持高准确率。
原文摘要 · Abstract (English)
Sparse embeddings of data form an attractive class due to their inherent interpretability: Every dimension is tied to a term in some vocabulary, making it easy to visually decipher the latent space. Sparsity, however, poses unique challenges for Approximate Nearest Neighbor Search (ANNS) which finds, from a collection of vectors, the k vectors closest to a query. To encourage research on this underexplored topic, sparse ANNS featured prominently in a BigANN Challenge at NeurIPS 2023, where approximate algorithms were evaluated on large benchmark datasets by throughput and accuracy. In this work, we introduce a set of novel data structures and algorithmic methods, a combination of which leads to an elegant, effective, and highly efficient solution to sparse ANNS. Our contributions range from a theoretically-grounded sketching algorithm for sparse vectors to reduce their effective dimensionality while preserving inner product-induced ranks; a geometric organization of the inverted index; and the blending of local and global information to improve the efficiency and efficacy of ANNS. Empirically, our final algorithm, dubbed Seismic, reaches sub-millisecond per-query latency with high accuracy on a large-scale benchmark dataset using a single CPU.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。