Die Annähernde Nächste-Nachbarn-Suche (ANNS) spielt eine entscheidende Rolle in Anwendungen wie Suchmaschinen, Empfehlungssystemen und RAG für LLMs. Die Vektorquantisierung (VQ), eine entscheidende Technik für ANNS, wird häufig verwendet, um den Speicherbedarf zu reduzieren und die Abstandsberechnungen zu beschleunigen. Trotz erheblicher Forschungsfortschritte stehen moderne VQ-Methoden jedoch nach wie vor vor Herausforderungen, die Effizienz der Kodierung und die Genauigkeit der Quantisierung in Einklang zu bringen. Um diese Einschränkungen anzugehen, schlagen wir eine neuartige VQ-Methode namens SAQ vor. Zur Verbesserung der Genauigkeit verwendet SAQ eine neue Technik zur Dimensionssegmentierung, um PCA-projizierte Vektoren strategisch entlang ihrer Dimensionen in Segmente zu unterteilen. Indem führende Dimensionssegmente mit größeren Größen priorisiert werden, weist SAQ den Segmenten mit hoher Auswirkung mehr Bits zu und optimiert die Nutzung des verfügbaren Platzkontingents. Ein effizienter Algorithmus zur dynamischen Programmierung wird entwickelt, um die Dimensionssegmentierung und die Bitzuweisung zu optimieren und dabei den Quantisierungsfehler zu minimieren. Um die Vektorkodierung zu beschleunigen, entwickelt SAQ eine Technik zur Codeanpassung, um jede Dimension zunächst unabhängig zu quantisieren und dann die quantisierten Vektoren schrittweise mithilfe eines koordinatenabsteigenden Ansatzes zu verfeinern, um eine vollständige Enumeration zu vermeiden. Umfangreiche Experimente zeigen die Überlegenheit von SAQ im Vergleich zu klassischen Methoden (z.B. PQ, PCA) und aktuellen modernen Ansätzen (z.B. LVQ, Extended RabitQ). SAQ erzielt eine Reduktion des Quantisierungsfehlers um bis zu 80 % und beschleunigt die Kodierungsgeschwindigkeit um über das 80-fache im Vergleich zu Extended RabitQ.
Li et al. (Mon,) haben diese Frage untersucht.