Sparse produit scalaire dans SQL

Question

Imaginez que j'ai une table qui stocke une série de vecteurs rares. Un vecteur creux signifie qu'il ne stocke que les valeurs non nulles explicitement dans la structure de données. Je pourrais avoir un 1 million vectoriel de dimension, mais je ne stocker que les valeurs pour les dimensions qui sont non nulle. Ainsi, la taille est proportionnelle au nombre d'entrées non nulles, pas la dimensionnalité du vecteur.

Tableau définition serait quelque chose comme ceci: vector_id: int dimension: int Valeur: float

Maintenant, dans la terre de programmation normale, je peux calculer le produit intérieur ou d'un produit scalaire de deux vecteurs en O (| v1 | + | v2 |) temps. Fondamentalement, l'algorithme est de stocker les vecteurs rares triées par dimension et itérer les dimensions de chaque jusqu'à trouver les collisions entre les dimensions et multiplier les valeurs de la dimension partagée et continuer à ajouter les jusqu'à ce que vous arrivez à la fin de l'un des vecteurs .

Quel est le meilleur moyen de retirer ceci dans SQL?

Answer 1

Vous devriez être en mesure de reproduire cet algorithme dans une requête:

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 = ...