IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Requêtes PostgreSQL Discussion :

Point d'intérêt : recherche du plus proche voisin


Sujet :

Requêtes PostgreSQL

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut Point d'intérêt : recherche du plus proche voisin
    Bonjour,
    Je pense que j'ai mal placé mon message donc je le déplace au bon endroit voici mon problème :

    Je souhaiterai 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 ceux 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 ou 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 ou là requête prendrai 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

  2. #2
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    Bonjour,

    Effectivement il faut faire une requête "ensembliste" qui retournera chaque POINT et son POI le plus proche.

    L'idée est donc de calculer la distance entre POINTet POI pour chaque couple POINT-POI.

    La requête qui donne tous les couples POINT-POI avec distance associée :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    	SELECT 
    		POINT.POINT_ID,
    		POI.POI_ID ,
    		((POINT_X - POI_X) * (POINT_X - POI_X)) + ((POINT_Y - POI_Y) * (POINT_Y - POI_Y)) as Distance
    	FROM POINT
    		 CROSS JOIN POI
    Problème, on ne veut conserver que les couples dont la distance est minimale par POINT. Vous pouvez utiliser les fonctions de fenêtrage pour donner un classement par point ordonné selon la distance. Avec un filtre sur ce rang, on obtient le résultat :


    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    SELECT 
    	T1.POINT_ID, 
    	T1.POI_ID
     FROM (
    	SELECT 
    		POINT.POINT_ID,
    		POI.POI_ID ,
    		rank() OVER (	PARTITION BY POINT_ID 
    						ORDER BY ((POINT_X - POI_X) * (POINT_X - POI_X)) + ((POINT_Y - POI_Y) * (POINT_Y - POI_Y))  ASC) as Rang
    	FROM POINT
    		 CROSS JOIN POI 
    ) T1
    WHERE T1.Rang = 1 ;
    J'ai renommé vos tables en POINT (pour table_courante) et POI (pour table_ref) pour ce jeu d'essai sous SQL Server. Postgre propose les fonctions de fenêtrage donc vous devriez pouvoir produire la même requête.

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    CREATE TABLE POINT
    	(
    	POINT_ID int NOT NULL IDENTITY (1, 1),
    	POINT_X float(53) NOT NULL,
    	POINT_Y float(53) NOT NULL
    	)  ; 
     
    ALTER TABLE POINT ADD CONSTRAINT
    	PK_POINT PRIMARY KEY CLUSTERED 
    	(
    	POINT_ID
    	) ;
     
     
    CREATE TABLE POI
    	(
    	POI_ID int NOT NULL IDENTITY (1, 1),
    	POI_X float(53) NOT NULL,
    	POI_Y float(53) NOT NULL
    	)  ;
     
    ALTER TABLE POI ADD CONSTRAINT
    	PK_POI PRIMARY KEY CLUSTERED 
    	(
    	POI_ID
    	) ;
     
     
     
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.818582670617058, 0.985556772908735) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.713269401399025, 0.81097887205108) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.194535521335627, 0.0124077410312911) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.281937570484938, 0.890160077576039) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.650780078302762, 0.191317610360638) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.0739395509374265, 0.642377348468936) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.401943336164485, 0.708331173034934) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.918973993130198, 0.433642713381434) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.495538496879556, 0.348179912721617) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.345337753427621, 0.851305667201027) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.280108301736595, 0.723436416105253) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.378025936880004, 0.631662934538973) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.275106507213111, 0.719331138163388) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.477358759008437, 0.652521354663928) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.836899393393324, 0.757030029813829) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.379272598750997, 0.264497204375532) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.518435429804046, 0.61987999842367) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.404580630239183, 0.475780263095911) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.299996615929302, 0.0289548956889414) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.597808665550776, 0.62421252059612) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.0824863881499067, 0.617127300005919) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.795573410656195, 0.750726439888149) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.218209832655694, 0.215586131395841) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.356673284682968, 0.996717542701622) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.010561249477826, 0.892809921317062) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.303974245822957, 0.158234673314947) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.585069021531497, 0.325364737374638) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.396544181412241, 0.719660892517354) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.702604908561914, 0.940737598536585) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.780137911853013, 0.0648651624568277) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.65573013576289, 0.762890137243437) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.759380620815709, 0.119872037752179) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.295393774435239, 0.972513845309749) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.617175342125027, 0.437483670048466) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.412156391846973, 0.885318717868316) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.32029186833197, 0.974621642549017) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.952539397281789, 0.206466987875008) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.323427863424759, 0.295114665021911) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.0103716782911807, 0.0235953555543498) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.642784404176997, 0.454567118689553) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.913934540381516, 0.443860613890101) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.137774518251596, 0.568652338963264) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.43354874843968, 0.614665694489118) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.776591098439964, 0.124223021848062) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.638615096097886, 0.965327759212727) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.473263128181409, 0.998366553945839) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.939331017526304, 0.437574550651322) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.0901183996039432, 0.927137834253151) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.760681945856034, 0.381004917303767) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.665515041155488, 0.964143587744259) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.661972671803645, 0.609878966717733) ;
    INSERT INTO POINT (POINT_X,POINT_Y) values (0.14069654398478, 0.420648171332581) ;
     
    INSERT INTO POI (POI_X,POI_Y) values (0.836918968581705, 0.230316517122635) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.233487615722736, 0.0632046546083163) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.302121389036649, 0.0943385407217685) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.282042353170161, 0.314511812756899) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.261757241534069, 0.430522634202843) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.74695406561731, 0.257173237766772) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.0751587469630914, 0.119406569904903) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.066797638251225, 0.602213492833933) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.983229638309628, 0.341124710851094) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.897105173899553, 0.0406423067350787) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.903423780758424, 0.154958098698963) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.810294209547822, 0.731991348310767) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.212122122317062, 0.431354655545379) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.342022606700926, 0.101581384952916) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.38628108497448, 0.630766462938606) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.99791878516418, 0.359665688517391) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.217820516904739, 0.374647511237832) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.302931705533707, 0.945980200927524) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.251975886303743, 0.746712378201901) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.279884576730504, 0.0143419359113965) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.806763963118469, 0.488610633638716) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.0377105438180498, 0.933290269962104) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.540596329924859, 0.0241871846044894) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.811370581584759, 0.413491023956223) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.746231025875145, 0.668769929567581) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.576693687884039, 0.558456106620532) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.752239338117783, 0.742715305706587) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.477560509444533, 0.418796423930713) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.272391194219551, 0.67921453286289) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.133719334101453, 0.664918314905708) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.548404811360943, 0.0490952658348913) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.810448083421498, 0.00197681530135974) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.345938763302369, 0.891189020332768) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.422260423910426, 0.634441894317258) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.0665473940234769, 0.455378297437818) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.461324620138421, 0.277931326542238) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.933364346074433, 0.240927048909786) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.0915775691062137, 0.749052478770752) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.482344184839701, 0.883160425515589) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.723689338726255, 0.9846905195133) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.601811927683792, 0.709611823662558) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.988690926837466, 0.468339292970609) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.711494638027556, 0.0815508342115718) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.511438534459953, 0.158942564297963) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.09011509993781, 0.297084436708184) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.285338948086004, 0.953383774065311) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.759835885829603, 0.65791733439588) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.205253381116685, 0.846589869789518) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.864401148828737, 0.525531226698574) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.173395009892339, 0.265667701903721) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.1859368630908, 0.990323715688128) ;
    INSERT INTO POI (POI_X,POI_Y) values (0.52622389480383, 0.506639360096308) ;

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut
    Merci pour l'aide que vous souhaitez m'apporter.

    je viens d'implémenter votre algo.
    Certes il fonctionne mais comme je vous l'ai dit chaque point n'a pas 2 coordonnées x et y mais 64 descripteurs..

    Par conséquent, le temps de calcul avec votre algo ( comparaison de 300 points courant à 300 points de ref prend 9000 ms ... or mon algo avec une boucle prend 2850 ms

    Et à l'avenir table_point-ref que vous appelez POI aura plus de 10 000 points..

    Merci pour votre aide !

  4. #4
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    Il y a peut être des pistes d'amélioration pour ces requêtes qui donnent le même résultat. Cependant, les algorithmes utilisés restent gloutons et les optimisations offertes par Postgre (indexes spatiaux) pour le calcul de distances euclidiennes se limitent à la 2D si je ne dis pas de bêtises.

    Il doit y avoir des pistes algorithmiques plus adaptées dans votre cas. Je ne suis pas du tout connaisseur, aussi je vous conseille de demander sur le forum algorithmie pour tenter une meilleure approche.

  5. #5
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut NON résolu ..
    OK merci quand même pour ton aide..

    J'ai du mal à croire que personne d'autre ne s'est intéressé à la recherche du plus proche voisin dans un espace à N dimensions..

    C'est pourtant courant maintenant les KD-tree et compagnie... Impossible de trouver une implémentation en tout cas ..

    PS : ou est ce que je peux trouver ton forum algorithmie ?

  6. #6
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    Des personnes s'y sont penchées mais il n'y a pas une implémentation native dans Postgre. Vous pouvez vous baser sur les solutions algorithmiques et faire une implémentation sous Postgre si besoin.

  7. #7
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 736
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 736
    Points : 52 447
    Points
    52 447
    Billets dans le blog
    5
    Par défaut
    Utilisez PostGIS et mettez un index sur votre colonne géometry cela ira beaucoup plus vite. utilisez ST_Distance et faite le MIN.

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

  8. #8
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    Le problème étant que ça n'est pas implémenté pour des géométries à plus de 2 dimensions comme je le disais.

  9. #9
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut
    Utilisez PostGIS et mettez un index sur votre colonne géometry cela ira beaucoup plus vite. utilisez ST_Distance et faite le MIN.

    A +
    J'ai déjà fait beaucoup de recherches et j'avais en effet trouver quelques informations parlant de postGIS et de ST distance, mais selon moi, ce n'est pas adapter à des vecteurs à N dimensions ou N = 64 ou 128 ..

    ce n'est pas la recherche d'un point en terme de distance (dans un plan 2D) mais bien la recherche d'un point d'intérêt avec son plus proche voisin en terme de descripteurs.

    Est ce que vous avez (ou quelqu'un a) déjà implémenté un tel algo ? ça me parait bizarre que non ...

  10. #10
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 736
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 736
    Points : 52 447
    Points
    52 447
    Billets dans le blog
    5
    Par défaut
    Citation Envoyé par Yannok Voir le message
    ce n'est pas la recherche d'un point en terme de distance (dans un plan 2D) mais bien la recherche d'un point d'intérêt avec son plus proche voisin en terme de descripteurs.
    Mais la couche GIS est justement faite pour cela. Lisez l'article que j'ai écrit à ce sujet : http://blog.developpez.com/sqlpro/p9...n-geographiqu/

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

  11. #11
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut
    je vais lire votre article mais vous parlez de st_distance or
    COMMENT ON FUNCTION public.st_distance(geometry, geometry) IS 'args: g1, g2 - For geometry type Returns the 2-dimensional cartesian minimum distance
    on est bien dans un espace 2D et je travaille dans un espace 64 D...
    De plus les données traitées par gist sont des points avec des coordonnées x et y. A la limite Z .. Or moi au lieu d'un vecteur (x,y) j'ai un vecteur(d1,d2,..,dN)

  12. #12
    Membre émérite
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    1 874
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Octobre 2008
    Messages : 1 874
    Points : 2 890
    Points
    2 890
    Par défaut
    Citation Envoyé par Yannok Voir le message
    J'ai du mal à croire que personne d'autre ne s'est intéressé à la recherche du plus proche voisin dans un espace à N dimensions..
    Postgresql 9.2 actuellement en beta aura des index SP-Gist mais tout reste à faire pour les mettre en pratique dans un kd-tree. En plus 64 dimensions c'est notoirement trop élevé pour une recherche efficace dans un kd-tree, ça reviendrait certainement à une recherche "brute-force".

    Il y a plein d'articles au sujet de la recherche de voisins dans un espace à N dimensions, mais ce sont des articles de niveau recherche et pas des tutoriels sur comment faire avec un SGBD. De plus ces articles sont incompréhensibles pour qui n'a pas déjà des connaissances avancées dans ce domaine.
    Or tu te dis débutant, il y a à mon sens une contradiction avec le niveau de difficulté du problème auquel tu t'es attaqué.

  13. #13
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut
    1 : Votre article ne m'a pas aidé pour moi il s'agit que d'espace limités à 3D
    2 :
    Or tu te dis débutant, il y a à mon sens une contradiction avec le niveau de difficulté du problème auquel tu t'es attaqué
    Heureusement que tout le monde ne pense pas comme ça.. on avancerait pas bcp !

    Je pense qu'on s'éloigne pttr du problème et qu'optmiser ma 1ère requête est pttr plus simple..

  14. #14
    Membre émérite
    Profil pro
    Inscrit en
    Octobre 2008
    Messages
    1 874
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Octobre 2008
    Messages : 1 874
    Points : 2 890
    Points
    2 890
    Par défaut
    Citation Envoyé par Yannok Voir le message
    Je pense qu'on s'éloigne pttr du problème et qu'optmiser ma 1ère requête est pttr plus simple..
    Ta 1ere requête est en 2 dimensions.
    Ceux qui essaient de t'aider avec 2 dimensions, tu leur rétorques que ça ne t'intéresse pas parce que tu veux 64 dimensions.
    Et tu en conclus qu'il faut optimiser ta requête à 2 dimensions.
    Bon courage pour continuer à tourner en rond.

  15. #15
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut
    Ta 1ere requête est en 2 dimensions.
    Ceux qui essaient de t'aider avec 2 dimensions, tu leur rétorques que ça ne t'intéresse pas parce que tu veux 64 dimensions.
    Et tu en conclus qu'il faut optimiser ta requête à 2 dimensions.
    Bon courage pour continuer à tourner en rond.
    Mais non ... la requête est en 64 dimensions :cette phrase est plutôt claire
    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... )


    l'EXEMPLE de la requête à 2D c'est juste pour comprendre le principe de l'algo que j'essaye d'implémenter

  16. #16
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    J'ai proposé une autre formulation de requête pour voir si elle pouvait s'avérer plus rapide en l'état (qu'on soit en 2 ou x dimensions). On vous a dit que postgre n'implémentait pas de solution native pour votre problème (à travers des opérateurs et des index spécifiques).

    Estofilo a fait remarquer que la littérature sur le sujet indique qu'avec beaucoup de dimensions, il n'y a pas de recherche de solution exacte qui soit rapide. C'est aussi ce que j'ai cru lire (vu mes faibles connaissances) car ils évoquaient systématiquement des approximations pour optimiser ça.

    Qu'avez vous cherché/trouvé concernant votre problème si ce n'est penser que postgre disposait en son sein d'une solution toute prête ?

  17. #17
    Nouveau Candidat au Club
    Homme Profil pro
    Inscrit en
    Juillet 2012
    Messages
    14
    Détails du profil
    Informations personnelles :
    Sexe : Homme

    Informations forums :
    Inscription : Juillet 2012
    Messages : 14
    Points : 1
    Points
    1
    Par défaut
    je travaille sous openCV en C++, donc actuellement je réalise l'appariement à l'aide d'une fonction propre à cette bibliothèque appelé cvFindFeatures qui me permet de trouver mes paires (id_courant et id_ref).

    En passant par la BDD (après chargement des images) je pensais que j'irais plus vite pour trouver mes paires. c'était une piste comme une autre..

  18. #18
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    Si vous avez les données en mémoire et que vous utilisez Postgre comme tampon pour y faire des requêtes de traitement d'image avec un algorithme glouton, il ne faut pas s'étonner que vous n'arriviez pas à faire du temps réel surtout vu vos contraintes.

    Je ne pense pas que vous utilisez la base de données à bon escient ici.

  19. #19
    Membre émérite

    Profil pro
    Inscrit en
    Mars 2005
    Messages
    1 683
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Haute Garonne (Midi Pyrénées)

    Informations forums :
    Inscription : Mars 2005
    Messages : 1 683
    Points : 2 576
    Points
    2 576
    Par défaut
    Avez vous fait des recherches sur votre problème d'un point de vue purement algorithmique pour améliorer les performances ?

  20. #20
    Rédacteur

    Avatar de SQLpro
    Homme Profil pro
    Expert bases de données / SQL / MS SQL Server / Postgresql
    Inscrit en
    Mai 2002
    Messages
    21 736
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Var (Provence Alpes Côte d'Azur)

    Informations professionnelles :
    Activité : Expert bases de données / SQL / MS SQL Server / Postgresql
    Secteur : Conseil

    Informations forums :
    Inscription : Mai 2002
    Messages : 21 736
    Points : 52 447
    Points
    52 447
    Billets dans le blog
    5
    Par défaut
    Il n'est pas possible de vous aider sans :
    1) le DDL de votre table
    2) un jeu d'essais
    3) un résultat

    Et pas des exemples bidons dont vous avez pollué le forum.

    A +
    Frédéric Brouard - SQLpro - ARCHITECTE DE DONNÉES - expert SGBDR et langage SQL
    Le site sur les SGBD relationnels et le langage SQL: http://sqlpro.developpez.com/
    Blog SQL, SQL Server, SGBDR : http://blog.developpez.com/sqlpro
    Expert Microsoft SQL Server - M.V.P. (Most valuable Professional) MS Corp.
    Entreprise SQL SPOT : modélisation, conseils, audit, optimisation, formation...
    * * * * * Expertise SQL Server : http://mssqlserver.fr/ * * * * *

Discussions similaires

  1. Algorithme KD-Tree de recherche du plus proche voisin .
    Par mobi_bil dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 11/05/2014, 12h54
  2. Tracking Recherche du plus proche voisin
    Par themadmax dans le forum Traitement d'images
    Réponses: 5
    Dernier message: 18/12/2013, 11h43
  3. Point d'intérêt :Recherche des plus proches voisins
    Par Yannok dans le forum Requêtes
    Réponses: 4
    Dernier message: 10/07/2012, 23h25
  4. Recherche des k plus proches voisins d'un point
    Par mobi_bil dans le forum Traitement d'images
    Réponses: 5
    Dernier message: 13/05/2009, 15h39
  5. Recherche des plus proches voisins dans un espace variable à K dimensions parmis N
    Par JeromeBcx dans le forum Algorithmes et structures de données
    Réponses: 34
    Dernier message: 26/06/2008, 18h46

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo