Verlustfreie Komprimierung von Vektor-IDs verbessert die approximative Nearest-Neighbor-Suche
2025-01-23
Forscher stellen ein verlustfreies Komprimierungsschema für Vektor-IDs vor, um die hohen Speicherkosten von Indizes bei der approximativen Nearest-Neighbor-Suche zu adressieren. Sie nutzen die Tatsache aus, dass die Reihenfolge der IDs in vielen Indexstrukturen irrelevant ist, und verwenden asymmetrische Zahlensysteme oder Wavelet-Bäume. Die Methode erreicht eine bis zu 7-fache Komprimierung der Vektor-IDs ohne Beeinträchtigung der Genauigkeit oder der Suchlaufzeit. Dies führt zu einer Reduzierung der Indexgröße um 30 % bei Datensätzen im Milliardenbereich. Darüber hinaus kann der Ansatz auch quantisierte Vektorcodes verlustfrei komprimieren, indem er Suboptimalitäten im ursprünglichen Quantisierungsalgorithmus ausnutzt.