Recherche des objets mobiles dans les réseaux routiers

Une approche basée sur l’analyse formelle de concepts

¹ ISET de Jendouba, Laboratoire BESTMOD, Campus Universitaire 8189 Jendouba Nord, Tunisie
² ISG de Tunis, Laboratoire BESTMOD, 41, av. de la Liberté, Cité Bouchoucha, Le Bardo 2000, Tunis ferchichi.hafedh@gmail.com ; j.akaichi@gmail.com

Résumé

Ce papier présente une nouvelle approche de recherche en continu des K plus proches voisins (C-KNN). Notre approche, qui s’applique aux réseaux routiers, adopte l’analyse formelle de concepts (AFC) qui est un paradigme à base de fondement mathématique. AFC permettra de présenter une abstraction du réseau qui se base sur les voisinages. L’approche proposée consiste à construire le treillis de Galois à partir des relations binaires entre les points d’intérêts candidats et leurs propriétés. Ces dernières sont extraites à partir d’un ensemble de capteurs associés au réseau routier en question. Une phase d’indexation permet d’accélérer le processus de recherche afin de réduire le temps de traitement. Une étude de cas et une expérimentation sont aussi proposées afin de montrer la faisabilité de notre approche de recherche en continu des k-NN à base d’AFC.

Abstract

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 their properties. The latters 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 and experiments are presented to show the effectiveness of our FCA-based solution.