Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 Optimisation » Optimisation requête répétée » 12/07/2012 17:06:50
- yannok
- Réponses : 2
Bonjour,
J'ai 2 tables : table_ref et table_courante
chacune de ces tables à 64 colonnes desc_0, desc_1 desc ... desc_63
Lors d'une requête j'ai besoin de calculer une distance " euclidienne " de la façon suivante
table_ref.desc_0 - table_courante.desc_0) * (table_ref.desc_0 - table_courante.desc_0) + (table_ref.desc_1 - table_courante.desc_1) * (table_ref.desc_1 - table_courante.desc_1) +... + (table_ref.desc_63 - table_courante.desc_63) * (table_ref.desc_63 - table_courante.desc_63)
J'ai remarqué que plus je rajoute de colonnes, plus ma requête prend du temps (normal) :
ainsi faire select (table_ref.desc_0 - table_courante.desc_0) * (table_ref.desc_0 - table_courante.desc_0) from table_ref , table_courante prend par ex 100 ms
le fait de rajouter (table_ref.desc_1 - table_courante.desc_1) * (table_ref.desc_1 - table_courante.desc_1) prend 50 ms de plus etc...
ma question est la suivante : est ce que ce serait possible d'optimiser cette requête puisqu'il s'agit toujours du mm type de calcul seul l'appel des colonnes change.
Merci !
#2 Re : Optimisation » SP -gist : knn search dans KD-tree » 12/07/2012 16:27:05
oui je stock des points d'intérêts qui ont chacun 64 descripteurs. on peut donc faire l'analogie avec un point et ses coordonnées x et y.
la distance " euclidienne " entre 2 points se basera sur le mm principe qu'une distance euclidienne en 2 D
" Si oui, le plus simple que vous ayez à faire, c'est de reprendre l'implémentation du type point de postgresql (tout est dans le source de postgresql), et de l'adapter à 64 dimensions. Ça devrait marcher, même si ça risque d'être pénible. " => 0o
#4 Re : Optimisation » SP -gist : knn search dans KD-tree » 12/07/2012 14:51:33
" Je n'ai pas vu passer d'implémentation pour un vecteur à 2D (ce qui ne prouve rien évidemment smile ) "
Y'en a la pelle pourtant, mais que pour la recherche du plus proche voisin pour un point en 2D.
#5 Re : Optimisation » SP -gist : knn search dans KD-tree » 12/07/2012 12:07:03
Il me semble que gist permet de calculer le plus proche voisin sur des vecteurs à 2D. or ce que je souhaiterai c'est faire la même chose pour des vecteurs à 64 dimensions.
J'espère que je suis plus clair
#6 Optimisation » SP -gist : knn search dans KD-tree » 11/07/2012 11:37:20
- yannok
- Réponses : 10
Bonjour,
Est ce que quelqu'un a déjà implémenté la recherche du plus proche voisin à l'aide de SP gist ?
Je souhaiterais trouver, pour un point donné de la table courante, son plus proche voisin dans la table de référence.
CREATE TABLE table_courante(id_point serial PRIMARY KEY,id_image INTEGER,x_image FLOAT,y_image FLOAT)
CREATE TABLE table_ref(id_point serial PRIMARY KEY,id_image INTEGER,x_image FLOAT,y_image FLOAT).
Pour cela je recherche le plus proche voisin en terme de distance euclidienne (x-y) * (x-y).
Dans cet exemple, le vecteur est à 2 dimensions (x et y) mais dans ma vraie table il s'agit d'un vecteur à 64 dimensions (c'est un point d'intérêt avec 64 descripteurs
ex :table_ref.desc_0 - table_courante.desc_0) * (table_ref.desc_0 - table_courante.desc_0) + (table_ref.desc_1 - table_courante.desc_1) + etc... )
j'aimerais que ma requête retourne l'id du point de l'image courant et l'id du point de l'image de référence pour laquelle la distance est la plus petite, et ce pour l'ensemble de mes points courants.
Actuellement je suis capable de faire ça :
SELECT table_courante.id_point,table_ref.id_point
,((table_ref.x-table_courante.x)*(table_ref.x-table_courante.x) + (table_ref.y-table_courante.y)*(table_ref.y-table_courante.y)) AS distance
FROM table_ref, table_courante
WHERE table_courante.id_point=XXX
ORDER BY distance
LIMIT 1
et je fais une boucle où XXX prend toutes les valeurs de mon id du point courant (0, 1, 2 ...N)
Mais cette requête prend 3 secondes pour comparer 2 images.. or j'ai 25 images à la sec.. et je dois être capable de faire du temps réel..
Je souhaiterais donc trouver un moyen de ne pas faire de boucle, et /ou trouver une requête complètement différente où la requête prendrait quelques centaines de ms maximum. A terme la table de ref contiendra des milliers de points..
ATTENTION : ce n'est pas parce que l'id du point de l'image courante = l'id du point de ref qu'il s'agit du même point. Cela n'a rien à voir, ils sont chacun sur 2 images différentes
J'espère que j'ai été clair
Merci d'avance pour votre aide
PS : je travaille sous postgre 9.1. avec un XP et un processeur de 2.5 Ghz
PPS : je débute, Be nice
#7 Site PostgreSQL.fr » SP -gist : knn search dans KD-tree » 11/07/2012 11:12:13
- yannok
- Réponses : 1
Bonjour,
Est ce que quelqu'un a déjà implémenté la recherche du plus proche voisin à l'aide de SP gist ?
Je souhaiterais trouver, pour un point donné de la table courante, son plus proche voisin dans la table de référence.
CREATE TABLE table_courante(id_point serial PRIMARY KEY,id_image INTEGER,x_image FLOAT,y_image FLOAT)
CREATE TABLE table_ref(id_point serial PRIMARY KEY,id_image INTEGER,x_image FLOAT,y_image FLOAT).
Pour cela je recherche le plus proche voisin en terme de distance euclidienne (x-y) * (x-y).
Dans cet exemple, le vecteur est à 2 dimensions (x et y) mais dans ma vraie table il s'agit d'un vecteur à 64 dimensions (c'est un point d'intérêt avec 64 descripteurs
ex :table_ref.desc_0 - table_courante.desc_0) * (table_ref.desc_0 - table_courante.desc_0) + (table_ref.desc_1 - table_courante.desc_1) + etc... )
j'aimerais que ma requête retourne l'id du point de l'image courant et l'id du point de l'image de référence pour laquelle la distance est la plus petite, et ce pour l'ensemble de mes points courants.
Actuellement je suis capable de faire ça :
SELECT table_courante.id_point,table_ref.id_point
,((table_ref.x-table_courante.x)*(table_ref.x-table_courante.x) + (table_ref.y-table_courante.y)*(table_ref.y-table_courante.y)) AS distance
FROM table_ref, table_courante
WHERE table_courante.id_point=XXX
ORDER BY distance
LIMIT 1
et je fais une boucle où XXX prend toutes les valeurs de mon id du point courant (0, 1, 2 ...N)
Mais cette requête prend 3 secondes pour comparer 2 images.. or j'ai 25 images à la sec.. et je dois être capable de faire du temps réel..
Je souhaiterais donc trouver un moyen de ne pas faire de boucle, et /ou trouver une requête complètement différente où la requête prendrait quelques centaines de ms maximum. A terme la table de ref contiendra des milliers de points..
ATTENTION : ce n'est pas parce que l'id du point de l'image courante = l'id du point de ref qu'il s'agit du même point. Cela n'a rien à voir, ils sont chacun sur 2 images différentes
J'espère que j'ai été clair
Merci d'avance pour votre aide
PS : je travaille sous postgre 9.1. avec un XP et un processeur de 2.5 Ghz
PPS : je débute, Be nice
Pages : 1