FARGO: Schnelle Suche nach maximalem inneren Produkt mittels globalem Multi-Probing

01/01/2023

Maximum Inner Product Search verstehen: Von der Theorie zur Praxis

Da maschinelles Lernen und künstliche Intelligenz sich stetig weiterentwickeln, ist die Fähigkeit, hochdimensionale Vektorräume effizient zu durchsuchen, zunehmend entscheidend geworden. Eine grundlegende Herausforderung in diesem Bereich ist das Problem der Maximum Inner Product Search (MIPS), bei dem es darum geht, Vektoren in einem Datensatz zu finden, die ihr inneres Produkt mit einem gegebenen Abfragevektor maximieren. Diese Operation ist zentral für zahlreiche Anwendungen, darunter Empfehlungssysteme, Multi-Class-Label-Vorhersage, Similar-Item-Retrieval, Structural SVM und Deep Learning.

Traditionelle Ansätze für MIPS, die raumpartitionierende Bäume verwenden, werden mit zunehmender Dimensionalität exponentiell langsamer, wodurch sie für moderne Anwendungen, die häufig mit Hunderten oder Tausenden von Dimensionen arbeiten, unpraktikabel werden. Während Locality-Sensitive Hashing (LSH) sich für die approximative Suche nach nächsten Nachbarn als effektiv erwiesen hat, kann es aufgrund der einzigartigen Eigenschaften der Inner-Product-Ähnlichkeit nicht direkt auf MIPS angewendet werden. Der Bedarf an einer effizienten, skalierbaren Lösung für MIPS war noch nie dringlicher, da Unternehmen zunehmend großskalige, hochdimensionale Datensätze verarbeiten.

Dieses Paper stellt FARGO vor, ein neuartiges Framework, das unseren Umgang mit dem MIPS-Problem revolutioniert. Wir präsentieren eine umfassende Analyse aktueller MIPS-Lösungen, ihrer Einschränkungen und wie FARGO diese Herausforderungen durch innovative Techniken wie globales Multi-Probing und die random XBOX transformation überwindet. Unser Framework erreicht nicht nur eine höhere Genauigkeit und Effizienz im Vergleich zu bestehenden Methoden, sondern bietet auch praktische Lösungen für reale Anwendungen, die mit hochdimensionalen Daten in großem Maßstab arbeiten.

Whitepaper erhalten