Spärliches Skalarprodukt in SQL

Question

Stellen Sie sich vor, ich habe eine Tabelle, die eine Reihe von spärlichen Vektoren speichert. Ein Sparse-Vektor bedeutet, dass er nur die Nicht-Null-Werte explizit in der Datenstruktur speichert. Ich könnte einen 1 Million dimensionalen Vektor haben, aber ich speichere nur die Werte für die Dimensionen, die nicht Null sind. Die Größe ist also proportional zur Anzahl der Nicht-Null-Einträge und nicht zur Dimensionalität des Vektors.

Tabellendefinition würde wie folgt sein: vector_id: Dimension int: int Wert: float

nun in normaler Programmierung Land kann ich das innere Produkt oder Skalarprodukt von zwei Vektoren in O berechnen (| v1 | + | v2 |) Zeit. Grundsätzlich besteht der Algorithmus darin, die dünn besetzten Vektoren nach Dimension sortiert zu speichern und die Dimensionen in jedem zu durchlaufen, bis Sie Kollisionen zwischen Dimensionen finden und die Werte der geteilten Dimension multiplizieren und diese bis zum Ende eines der Vektoren addieren .

Was ist der schnellste Weg, um dies in SQL abzuziehen?

Answer 1

sollten Sie in der Lage sein, diesen Algorithmus in einer Abfrage zu replizieren:

select sum(v1.value * v2.value) 
from vectors v1 
inner join vectors v2 
on v1.dimension = v2.dimension 
where v1.vector_id = ... 
and v2.vector_id = ...