AFC-CkNN: Indexation basée sur l’Analyse des Concepts Formels pour la Recherche en continu des K Plus Proches Voisins dans des Réseaux Routiers

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.