Produit scalaire fragmenté dans SQL

Question

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

définition de la table 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 |) heure. Fondamentalement, l'algorithme consiste à stocker les vecteurs clairsemés triés par dimension et à parcourir les dimensions de chacun jusqu'à ce que vous trouviez des collisions entre les dimensions et multipliez les valeurs de la dimension partagée et continuez à les ajouter jusqu'à la fin de l'un des vecteurs .

Quel est le moyen le plus rapide 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 = ...