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 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. However, the fast increasing number of moving objects adn the high dynamic nature of the road network pose a big challenge to the ck-NN search of moving objects. In this paper, we present a parallel search method to improve the efficiency by upgrading the MapReduce paradigm. A density-based road network partitioning approach is employed in our MapReduce based ckNN search. Finally, implementation based on the Storm parallel programming model is discussed to show the effectiveness of our FCA-based solution.