This paper presents a new approach to the continuous K nearest neighbors search (C-KNN) problem, in the context of road networks. Our approach is based on Formal Concepts Analysis (FCA) which has a mathematical foundation. FCA offers an abstraction of the network based on the neighborhoods. We build the concept lattice based on the binary relations between the target points as well as theirs properties. The latter are collected from various sensors on the road network. An indexing phase is also defined to speed up the search process and to reduce the processing time. Finally, a case study is presented to show the effectiveness of our FCA-based solution. MOTS-CLES : Analyse formelle de concepts, requêtes de plus proche voisin, CKNN, indexation, réseau spatial.
Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015.
Avec l'intégration des communications sans fils et les technologies de
positionnement (GPS-Global Positioning System), les applications et les services
basés sur la localisation (LBS Location-based services) émergent et gagnent
rapidement du progrès. Une classe importante de problème dans les LBSs consiste
en la recherche du plus proche voisin (NN). Jusqu'à présent, la recherche des k-NN
constituent un problème majeur dans les entrepôts de données notamment dans les
entrepôts de données des objets mobiles qui décrivent des environnements
dynamiques. Il existe plusieurs techniques de traitement efficaces des requêtes de
recherches des k-NN dans un espace de données statique. Récemment, la recherche
s’est focalisée sur les requêtes de recherche en continu des K-NN (C-KNN :
Continous K Nearest Neighber) qui s’intéresse aux objets mobiles sur un réseau
routier. Une requête continue est une requête qui, au lieu d’être évaluée une seule
fois à l’instant où elle est soumise au système, s’évalue de manière continue pour un
intervalle de temps donné
Le reste du papier est organisé comme suit : La section 2 synthétise l'état de l'art des méthodes de recherche des k-plus proches voisins dans un réseau routier. La section 3 donne une idée sur la solution adoptée. Dans la section 4 nous présentons notre approche à base de FCA pour la recherche des k-plus proches voisins dans un réseau routier. La section 5 présente une synthèse de notre approche. La section 6 est consacrée à la conclusion et aux travaux futurs.
La problématique de recherche des K plus proches voisins présente plusieurs axes où les chercheurs essayent de trouver des solutions. Le classement le plus fréquent de cette problématique se base sur la façon avec laquelle seront calculées les distances entre les points requêtes et les points d’intérêts, dont on distingue la distance euclidienne et la distance de plus court chemin. Pour chercher les K plus proches voisins on pourrait détecter plusieurs points de différences entre l'espace euclidien et le réseau routier. Ces différences touchent essentiellement la métrique utilisée (distance euclidienne entre deux points ou distance du plus court chemin dans le réseau routier), le type de recherche à appliquer (Par point (kNN) ou Par intervalle (kNN+CkNN)) et les techniques de recherches utilisées (Structure d’index ou Techniques géométriques+Structures d'index).
Les techniques d’indexation multidimensionnelles ont été largement étudiées. En
1984, Guttman propose le R-Tree
Plusieurs modèles et algorithmes ont été proposés pour faire face aux changements constamment des positions des objets en mouvement. Toutefois, ces travaux présentent encore énormément de limites : la majorité des travaux existants se basent sur la métrique de la distance euclidienne. Toutefois, dans un monde réel, les requêtes se déplacent sur un réseau routier. Etant donné un chemin d'un point Pr à un point Pi, on appelle longueur du chemin, la somme des longueurs des arcs qui le constituent qui s’oppose au calcul de la distance euclidienne entre Pr et Pi qui n’est que la longueur de la ligne directe qui sépare ces deux points. la plupart des techniques existantes pour la recherche des K-NN ignorent l'état du réseau routier et ne prennent pas en charge la requête en temps réel ; la plupart des algorithmes existants génèrent un surcoût de stockage considérable ; - les approches précédentes ne peuvent pas bien fonctionner s'il ya des mises à jour fréquentes du déplacement d’objets, qui se produisent généralement dans des applications réelles ; - les Travaux existant ne sont pas en mesure de faire face à la représentation dynamique des attributs des objets en mouvement ;
Même les tentatives récentes, telles que
La majorité des approches étudiées présentent des insuffisances surtout lors du passage à des dimensions élevées ou dans le cas où il s’agit d’un contexte dynamique. Pour en résumer le problème, actuellement pour connaître les plus proches voisins d'un point requête dans l'espace, on est obligé de parcourir tous les points déjà existants, ce qui implique beaucoup de comparaisons.
L'Analyse Formelle de Concepts (AFC) est un formalisme mathématique qui
permet d'obtenir des concepts structurés hiérarchiquement regroupant des objets
possédants les mêmes attributs. La hiérarchie résultant de l'AFC est appelée treillis
de Galois
L’AFC consiste à construire un treillis de concepts à partir d’un tableau binaire Objets × Attributs. Formellement, un contexte K est la donnée d’un triplet (O, A, I) où O est un ensemble d’objets, A est un ensemble d’attributs, et I ⊂ O × A une relation entre O et A.
Définition 1 (Contexte Formel) : Un Contexte Formel est un triplet K = (G, M, I) où G est un ensemble d'objets, M est un ensemble d'attributs et I une relation binaire entre G et M vérifiant: I ⊆ G × P ; (g,m) ∈ I avec g ∈ G et m ∈ M signifie que l'objet g possède l'attribut m ou que l'attribut m est possédé par l'objet g.
Définition 2 (Concept Formel) : Un Concept Formel d'un contexte K = (G,M,I) est une paire (A,B) avec : A ⊆ G, B ⊆ M , A′ = B et B′ = A, où A′ est l'ensemble de tous les attributs de B possédés par les objets de A et de façon duale B′ est l'ensemble de tous les objets possédant les attributs de B. Les ensembles A et B sont appelés respectivement extension et intension du concept formel C. B (G, M, I) dénote l'ensemble de tous les concepts du contexte K = (G, M, I).
Définition 3 (Objet Mobile) : Un Objet Mobile « Oi », avec 0< i ≤ n, est caractérisé par une Position (P), une Vitesse (V) et une Direction (D). « Oi » pourrait être soit un point requête (Pr) soit un point d’intérêt (Pi). Oi (Pi, Vi, Di) avec Oi, Objet Mobile i, Pi position de l’objet mobile i, Vi Vitesse de l’objet mobile i, Di direction de l’objet mobile i.
Définition 4 (Point requête-Pr) : un Point requête (Pr) désigne chaque Objet mobile « Oi » qui lance une requête (r). « Pr » est caractérisé par une Position, une Vitesse et une Direction. Pr (P, V, D), avec Pr point requête, P position, V vitesse et D direction (East, Weast, North, South).
Définition 5 {Point d’intérêt (Pi) avec 0< i ≤ n} : un Point d’intérêt (Pi) désigne chaque objet mobile sur un réseau routier qui satisfait les critères d’une requête donnée. Pi est Caractérisé par une Position, une Vitesse et une Direction. Pi (Pi, Vi, Di), avec Pi point d’intérêt i, Vi vitesse de l’objet mobile i et Di direction de l’objet mobile.
Définition 6 Statut (O1, O2) : Chaque objet mobile (O1) admet un Statut par rapport à un autre objet mobile (O2). Généralement, O1 est un point requête alors qu’O2 est un point d’intérêt. Statut (O1, O2) est une fonction qui retourne soit « loin » soit « prés ». Statut (Pr, Pi) = Loin. Statut (Pr, Pi) = Prés.
Illustration 1 Statut (Pr, Pi) = {Loin || Prés}. Déterminer le statut d’un objet mobile revient à étudier les caractéristiques suivantes : la direction de l’objet mobile « Pr » ainsi que celle de l’objet mobile « Pi » (même direction ou direction inverse) ; les vitesses de l’objet mobile « Pr » ainsi que celle de l’objet mobile « Pi » (Vr estelle supérieure ou inférieure à Vi ?)
Algorithme 1. Statut (in (Pr, Pi, Vr, Vi, D1, D2), out (Near, Far)) Input: Pr (Xpr, Ypr), Pi(Xpi, Ypi), Vr, Vi, Dr, Di Output: “Near”, “Far” 1: si ((Vi <Vr) et (Dr= Di)) ou ((Vi >= Vr) et (Dr != Di)) alors 2: return “Near” 3: fin condition
Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. 4: 5: 6: 7: si ((Vi >Vr) et (Dr= Di)) Ou ((Vi <Vr) et (Dr != Di)) alors
return “Far” fin condition fin
Statut (Pr, Pi) = {Prés} dans le cas ou les deux objets mobiles Pr et Pi admettent une même direction alors que Statut (Pr, Pi) = {Loin} dans tout les autres cas.
Soit l’ensemble d’objet mobile : Oi = {O1, O2, O3,.., On} tel que 0< i ≤n. À un instant « T » donné, chaque Objet mobile « Oi » est caractérisé par :
Position : On désigne par « P » la position d’un point d’intérêt et par « Pi » l’ensemble des positions des points d’intérêts Pi = {P1, P2, P3, …, Pn} tel que 0< i ≤n. L’objet 1 (i=1) est situé alors à la position P1, l’objet 2 (i=2) est situé à la position P2, l’objet n (i=n) est situé à la position Pn. Alors que le point requête « Pr » est situé à la position P-Pr. Position Pi est étroitement liée à l’arc sur lequel est situé l’Objet en question. - Vitesse : les vitesses des objets mobiles étudiés vont être classées selon trois intervalles [0 km-50 km], [51 km-90 km] et [91 km-110 km]. On désigne par Vi la vitesse de l’objet i. - Direction : On désigne par « W » la direction West, par « E » la direction East, par « N » la direction North, et par « S » la direction South. Au moment d’interrogation le système doit indiquer si l’objet en question suit la même direction (Same Direction =SD) ou une direction inverse (Reverse Direction =RD) par rapport au point requête. - Facteur de perturbation : On définit un facteur de perturbation par, tout genre d’obstacle qui pourrait ralentir ou empêcher l’avancement des objets mobiles sur un réseau routier (un embouteillage, des travaux routiers, un mauvais temps, un accident routier …..). Un facteur de perturbation est une caractéristique propre à un arc.
Exemple. L’objet O2 se trouve à une position P2. La position P2 appartient à un arc porteur du caractéristique facteur de perturbation. On admettra que l’objet O2 possédera cette caractéristique. Autrement dit si O2 sera l’un des NN cherchés par le point requête il sera automatiquement éliminé à cause de cette caractéristique qui pourrait empêcher le point requête de l’atteindre.
Statut (X, Y) : Un point d’intérêt admet un statut par rapport à un point requête. Le résultat attendu est déterminé en étudiant la direction et la vitesse de l’objet mobile dont on veut déterminer son statut.
Citons par exemple le cas d'un usager (dans sa voiture) qui recherche les centres d’urgence mobile les plus proches de lui, tout au long de son trajet. La réponse à ce type de requête doit être valide au moment de sa réception par le client. Un point requête commencera son trajet à partir du noeud « N1 » pour atteindre le noeud « N12 » (Figure 1). On suppose que tous les objets mobiles présents sont des réponses candidates à la requête en question. Figure 1 présente un graphe de réseau routier formé de 12 noeuds, et considéré comme notre espace de recherche. Les propriétés des objets mobiles changent avec le temps.
Etape 1 : Modélisation de Réseau routier : Graphe {noeuds « N » + arcs « E »} / données statiques (les noeuds et les arcs) + données dynamiques (ensemble d’objets mobiles = points requêtes et points d’intérêts).
Etape 2 : À partir d'un ensemble de capteurs, associés au réseau routier étudié, les caractéristiques des objets mobiles seront livrées en temps réel à notre système. A partir du graphe et des capteurs dédiés on vise à générer les concepts formels associés, binairisation des caractéristiques des objets mobiles et la génération de la matrice des concepts formels. Soient Oi ⊆ O et Ai ⊆ A, on définit « f » et « g » comme suit: Intension. f: P (O) → P (A) f(Oi) = { a ∈ A / (o,a) ∈ I, ∀ o ∈ Oi }, Extension. g: P (A) → P (O) g(Ai) = { o ∈O / (o,a) ∈I, ∀a ∈Ai }
Etape 3 : Extraction des concepts formels : Les points d’intérêt candidats qui vont satisfaire la requête de l’utilisateur. Soient Oi ⊆ O et Ai ⊆ A, (Oi, Ai) est un concept si et seulement si Oi est l’extension de Ai et Ai est l’intension de Oi. Soit l’ensemble des concepts L = {(Oi, Ai) ∈ P(O) x P(A) / Oi = g(Ai) et Ai = h(Oi)}. Relation d’ordre (≤) sur L: Sous-concept / Sur-concept (spécialisation / généralisation). (O1, A1) ≤ (O2, A2) si et seulement si O1 ⊆O2 (ou A1 ⊇A2).
Algorithme 2. FCA-CKNN (in (T = (L, ≤), i), out (TAB-Res [])) Input: T = (L, ≤), int i = 0 Output: TAB-Res [] 1: pour tout Concept Ci ∈T = (L, ≤) faire
3: si (Statut () = “Near”) alors 4: Add Concept Ci to TAB-Res [i] 5: i = i+1 6: fin condition 7: fin boucle 8: fin boucle 9: Return TAB-Res [] 10: fin
Etape 4 : Génération de treillis (technique de regroupement). Treillis de Galois : Chaque couple d’éléments possède son « supremum » et son « infinimum ». T = (L, ≤), ensemble des concepts muni de la relation d’ordre.
Algorithme 3. Level (in (T = (L, ≤)), out (T-Level [])) Input: T = (L, ≤) Output: T-Level [] 1: pour tout Concept Ci ∈ T = (L, ≤) faire 2: N size of (Ci .Intension) 3: Add Ci to T-Level [N] 4: 5: 6: fin boucle Return T-Level[] fin
Etape 6 : Indexation des résultats avec R-Tree concepts).
Au moment du lancement de la requête, on suppose que tous les arcs du graphe ne présentent aucun facteur de perturbation, qui pourrait ralentir l’avancement des objets mobiles. Les valeurs de cette caractéristique sont négligeables (Fp = 0) à l’instant « T=0 ».
Input du système (voir Figure 1) - O1= Pr (PPr, Vr=60, E) - A déterminer si les objets en question sont aux portés du point requête Pr ou non. Résultats de la fonction Statut (): Statut (Pr, O2) = « Far», Statut (Pr, O3) = « Near», Statut (Pr, O4) = « Near». - Les points d’intérêt O2, O3 et O4 : O2 (P2, V1=80, SD, Far), O3 (P3,
V2=40, SD, Near), O4 (P4, V3=30, SD, Near)
Définition 7 (Relation Binaire) : Soit E un ensemble. Une relation binaire R sur E est un sous-ensemble de E× E. On note xRy pour signifier que (x, y) ∈ R
Soit le contexte formel K=(S, P, I). « S » désigne l'ensemble des objets mobiles, « P » désigne l'ensemble des propriétés de ces objets (Position, Vitesse, Direction, Statut et Facteur de perturbation) et « I » est une relation binaire entre « S » et « P » vérifiant : I ⊆ S x P et (s, p) ∈ I avec s ∈ S et p ∈P. La relation (s, p) ∈ I signifie que l’objet s possède l’attribut ou la propriété p. Le contexte formel « K » sera présenté par un tableau de sources « Objets Mobile X Propriétés » où toute case de la matrice contiendra une relation binaire : « 1 » si l’évènement est présent « 0 » sinon. Selon que le couple (S, P) de S x P appartient à I ou non. L'ensemble « S » contient tous les objets mobiles figurant dans le graphe étudié et on retiendra dans l'ensemble « P » les propriétés pouvant servir comme critères pour livrer des réponses valides aux requêtes des utilisateurs. Le Tableau1 présente la matrice des concepts formels « Objets Mobile X Propriétés ». Soient les vitesses V = {V1= 60, V2= 80, V3=30, V4 = 40}, Position P = {P1= [N1, N2], P2= [N2, N5], P3= [N3, N6], P4= [N1, N8]}, les directions N: North, S: South, E: East, W: West. Au moment de l’envoie d’une requête, le système détermine les résultants des différentes fonctions par rapport au point requête (Pr).
Définition 8 N-Direction (Pr, Pi) : Une fonction qui permet de comparer les directions entre le point d’intérêt (Pi) et le point requête (Pr). N-Direction retourne « SD » si les deux objets mobiles Pi et Pr ont les mêmes directions, et retourne « RD » dans le cas contraire.
Algorithme 4. N-Direction (in (Pi, Pr, D (Pi), D (Pr)), out (“SD”, “RD”)) Input: Pi, Pr, D (Pi), D (Pr)) Output: “SD”, “RD” 1: pour tout Concept Ci ∈T = (L, ≤) faire 2: si (D (Pi) == D (Pr)) alors 3: return “SD” 4: si non 5: 6: 7: 8:
return “RD” fin condition fin boucle fin
A ce stade, notre système doit assurer la génération du Treillis après l’intégration des propriétés calculables à savoir N-Direction () et Statut (). Ensuite il faut étudier pour chaque point d’intérêt suivant la position de l’objet mobile en question s’il est disposé à un facteur de perturbation ou non.
La dernière colonne du contexte formel généré Fp[P(OM)] détermine tout d’abord P(OM) qui présente la position de l’objet mobile en question. OM est situé éventuellement sur un arc bien déterminé. Si l’arc P(OM) présente au moment de l’interrogation l’un des facteurs qui peuvent freiner l’avancement de l’objet, Fp[P(OM)] est évaluée à « vraie » (« faux » dans le cas échéant). Dans cette version Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. du papier, nous ne tenons pas compte des facteurs de perturbation et nous laissons ce critère à des travaux futurs.
On pourrait bien remarquer que les objets qui ont plus de chance à satisfaire les besoins de l’usager sont ceux qui ont le Statut « Prés » par rapport au point requête. Les deux objets O3 et O4 peuvent garantir cette condition avec les deux caractéristiques « SD» et « Near » pour dire même direction que le point requête et prés du point requête.
Dans notre contexte, on cherche à maximiser le gain par rapport à un point requête c’est à dires que les points d’intérêt doivent garantir certaines caractéristiques pour satisfaire la requête de l’usager.
A l’instant « T=0 », une réponse valide = {O3, O4}, ce qui est bien exprimé par la matrice des concepts formels :
L’objet O2 admet un Statut () = « Far » car sa vitesse (V2) est plus grande que la vitesse du point requête (V1) (la propriété SD = 1 pourrait être interprétée dans ce cas comme suit : le point Pr ne pourrait jamais atteindre le point Pi =O2).
L’objet O3 admet un Statut () = « Near » car sa vitesse est inférieure à la vitesse du point requête (la propriété SD = 1 pourrait être interprétée dans ce cas comme suit : le point Pr pourrait atteindre le point Pi =O3).
L’objet O4 admet un Statut () = « Near » sa vitesse est inférieure à la vitesse du point requête (la propriété SD = 1 pourrait être interprétée dans ce cas comme suit : le point Pr pourrait atteindre le point Pi =O4).
Les noeuds du treillis sont structurés sous forme de concepts. Un concept peut être vu comme un ensemble d’objets (l’extension) caractérisé par un ensemble de propriétés (l’intension). Pour la recherche des K plus proches voisins, les concepts du treillis fournissent un regroupement des objets mobiles dans des noeuds homogènes qui ont chacun un ensemble de propriétés en commun. Connaissant les critères que doit satisfaire les objets mobiles cherchés, on pourrait facilement identifier le ou les noeuds qui vérifient ces critères et avoir donc des réponses valides. Dans un treillis de Galois, les concepts sont ordonnés selon des critères liés au nombre des objets mobiles figurant dans l’extension de chaque concept et au nombre des propriétés communes entre ces objets présents dans les intensions des concepts. Les concepts les plus généraux sont situés en haut du treillis alors que les concepts les plus spécifiques sont situés en bas du treillis. Les liens entre les différents niveaux du treillis peuvent être interprétés comme des généralisations ou des spécialisations entre les niveaux représentés par les concepts. En effet, un parcours ascendant des niveaux d’un treillis se traduit à chaque niveau par la diminution progressive du nombre des propriétés dans les intensions des concepts et l’augmentation progressive du nombre d’objets mobiles dans leurs extensions. Cela correspond au passage d’un niveau plus spécifique, qui contient peu d’objets mobiles qui vérifient plusieurs critères, à un niveau plus général, qui contient plus d’objets mobiles qui ne vérifient qu’une partie des propriétés en commun d’un niveau spécifique. Un parcours descendant des niveaux d’un treillis correspond au passage d’un niveau général à un niveau plus spécifique. Le diagramme de Hasse (Figure 2), facilite la compréhension et l’interprétation de la relation entre les objets mobiles et leurs propriétés. L’avantage de cette représentation est qu’à partir d’un treillis de concepts il est toujours possible de retrouver le contexte formel correspondant et inversement.
Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015.
Le treillis de Galois correspondant aux points d’intérêts candidats, présente 9 noeuds classifié selon 4 niveaux (Figure 3). On cherche à indexer les niveaux qui peuvent contenir éventuellement des réponses valides, en fonction des noeuds de chaque niveau. Synthèse : « Un usager dans sa voiture cherche les centres d’urgence mobile les plus proches de sa position tout au long de son trajet ».
Usager Pr (P, V, D) (Pr= O1). Centres d’urgence mobile Pi (Pi, Vi, Di, Si) (Pi = {O2, O3, O4}). Les Pi doivent tenir compte du contexte de Pr et doivent satisfaire deux conditions primordiales.
- Les Vitesses de Pr et des Pi doivent être plus au moins proches l’une de l’autre : - Si les objets ont les mêmes directions, pour que l’objet mobile Pr puisse atteindre les objets mobiles Pi, il faut que la vitesse de Pr soit supérieure aux vitesses des Pi. - Si la direction de l’objet mobile Pr est opposée aux directions des objets mobiles Pi, il y aura éventuellement un point d’intersection entre ces derniers s’ils vont passer par un même chemin. Pas de contrainte dans ce cas sur les vitesses de Pr et des Pi.
Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015.
On s’intéresse aux différents noeuds du Treillis de Galois qui présentent dans leurs intensions « I » la propriété «Near». Le tableau d’indexe accélère la recherche et donne satisfaction à l’usager en un temps optimale. Dans notre cas les réponses valides appartiennent au Niveau 5 et au Niveau 3.
Noeud 1(Niveau 3 les trois objets O1=Pr, O3 et O4 ont les caractéristiques Near, SD et East en communs) : I = {East, SD, Near}, E = {O4, O1=Pr, O3} // Réponses valides. Noeud 3 (Niveau 5, l’objet O1 admet tout seul les cinq caractéristiques mentionnées) : I = {East, Near, P1, SD, V1}, E = {O1=Pr} // Réponses valides. Noeud 4 (Niveau 5, l’objet O3 admet tout seul les cinq caractéristiques mentionnées) : I = {East, Near, P3, SD, V3}, E = {O3} // Réponses valides. Noeud 5 (Niveau 5, l’objet O4 admet tout seul les caractéristiques mentionnées) : I = {East, Near, P4, SD, V4}, E = {O4} // Réponses valides. Finalement, les réponses valides après élimination des doublant sont : {O1=Pr, O3, O4}.
Préserver la pertinence des résultats revient en premier lieu à réduire le temps de réponse puisque les résultats doivent être valides au moment de leur réception. Afin d’atteindre nos objectifs, l’approche proposée vise à réduire l’espace de recherche. L’utilisation de l’FCA pour la recherche des k plus proches voisins est motivée par deux principales caractéristiques : la structuration conceptuelle des données du treillis et l’ordre hiérarchique entre les concepts. En plus du temps de calcul pris par la génération de treillis, la complexité de construction du treillis de points d’intérêts dépend du nombre d'objets mobiles ainsi que de leurs propriétés. La construction des concepts est d'ordre O(k.m), ou k est le nombre de propriétés que peut avoir un point d'intérêt, m est le nombre de points d'intérêts. Le parcours du treillis généré prend un temps d'ordre O(L) ou L est le nombre de concepts d'objets mobiles.
Dans ce papier, nous avons proposé une approche de recherche des k-plus proches voisin en continu en appliquant l’analyse formelle de concepts pour le regroupement des objets mobiles. Cette méthode consiste à créer, à partir d'un graphe, un contexte formel qui servira à la construction du Treillis de Galois représentant la hiérarchie des caractéristiques des objets mobiles. Une fois le treillis construit, l'étape de recherche de points d’intérêt peut être effectuée grâce au mode de classification offert par les treillis de Galois. La méthode permet d’avoir que des points d’intérêt valides ayant au moins l'une des propriétés demandées par l'utilisateur. Le fondement mathématique de l’FCA permet de garantir l’exactitude des réponses délivrées. Dans les futurs travaux, nous comptons prendre en Copyright © by the paper’s authors. Copying permitted for private and academic purposes. Proceedings of the Spatial Analysis and GEOmatics conference, SAGEO 2015. considération la nature dynamique du réseau routier et les requêtes en présence de facteurs de perturbation dans le réseau.