Forums PostgreSQL.fr

yannok

Membre

SP -gist : knn search dans KD-tree

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

gleu

Administrateur

Re : SP -gist : knn search dans KD-tree

Est ce que quelqu'un a déjà implémenté la recherche du plus proche voisin à l'aide de SP gist ?

SP-GiST n'apparait qu'en 9.2, actuellement en beta. Donc ça m'étonnerait beaucoup

Pour le reste, je n'en ai aucune idée, mais peut-être que Marc saura y répondre.

---

Guillaume.

Marc Cousin

Membre

Re : SP -gist : knn search dans KD-tree

À priori, je dirais qu'il n'y a pas besoin de sp-gist pour ça, mais d'un simple gist, avec le KNN (comme dit dans le titre, d'ailleurs). en 9.1, grosso modo il faut être définir une distance entre deux objets indexés. Peut-être que tu peux t'inspirer de ce qui est fait pour le contrib pg_trgm? Dans son cas, la distance c'est facile, puisqu'on utilise un Levenshtein, mais c'est peut-être possible de faire quelque chose de similaire. Si j'ai bien suivi, l'idée de sp-gist c'est surtout d'améliorer la localité des données dans l'index, par rapport à leur proximité. J'avoue que je n'ai pas regardé le détail de l'implémentation de pg_trgm.

Bref, pour résumer, il faut que tu implémentes les différents opérateurs d'indexation, et surtout le 8ème (distance), si tu veux pouvoir récupérer les enregistrements ordonnés à partir de l'index. http://www.postgresql.org/docs/9.1/inte … ation.html

En espérant avoir aidé…

---

Marc.

yannok

Membre

Re : SP -gist : knn search dans KD-tree

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

Marc Cousin

Membre

Re : SP -gist : knn search dans KD-tree

Je n'ai pas vu passer d'implémentation pour un vecteur à 2D (ce qui ne prouve rien évidemment )

Mais pour ce que tu souhaites, il faut que tu définisses un nouveau type (vecteur à 64 dimensions) et que tu implémentes les fonctions demandées par l'indexation gist (il y en a 8 à faire).

C'est pas mal de boulot, mais en s'inspirant d'un module existant (comme pg_trgm), ça doit être réalisable.

---

Marc.

yannok

Membre

Re : SP -gist : knn search dans KD-tree

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

Marc Cousin

Membre

Re : SP -gist : knn search dans KD-tree

Sous Postgres ? Vous avez un exemple ?

---

Marc.

yannok

Membre

Re : SP -gist : knn search dans KD-tree

http://excoventures.com/talks/knn.pdf

http://archives.postgresql.org/pgsql-ha … g01547.php

http://www.sai.msu.su/~megera/postgres/ … 2010-1.pdf

Dernière modification par yannok (12/07/2012 16:06:21)

Marc Cousin

Membre

Re : SP -gist : knn search dans KD-tree

Le second et le troisième, ce sont des messages venant des développeurs de Gist et KNN directement (Oleg Bartunov et Teodor Sigaev). Et la première c'est juste une présentation sur le sujet.

Donc oui, le KNN est supporté par le type point (je n'ai pas fait attention, j'ai vu que vous avez écrit vecteurs, mais en fait si je comprends bien, c'est des points que vous stockez, même si dans un espace à 64 dimensions ?)

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.

Vous n'avez à mon avis aucune chance de trouver des extensions géométriques de PostgreSQL dans un espace à plus de 3 dimensions toutes faites.

---

Marc.

yannok

Membre

Re : SP -gist : knn search dans KD-tree

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

Dernière modification par yannok (12/07/2012 16:28:04)

Marc Cousin

Membre

Re : SP -gist : knn search dans KD-tree

Ben oui, les espaces vectoriels à 64 dimensions, c'est pas très fréquent dans la nature

---

Marc.