Browsing by Author "Bendjoudi, Ahcene"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Efficient parallel branch-and-bound approaches for exact graph edit distance problem
    (Elsevier, 2022-12) Dabah, Adel; Chegrane, Ibrahim; Yahiaoui, Saïd; Bendjoudi, Ahcene
    Graph Edit Distance (GED) is a well-known measure used in the graph matching to measure the similarity/dissimilarity between two graphs by computing the minimum cost of edit operations needed to transform one graph into another. This process, Which appears to be simple, is known NP-hard and time consuming since the search space is increasing exponentially. One way to optimally solve this problem is by using Branch and Bound (B&B) algorithms, Which reduce the computation time required to explore the whole search space by performing an implicit enumeration of the search space instead of an exhaustive one based on a pruning technique. nevertheless, They remain inefficient when dealing with large problem instances due to the impractical running time needed to explore the whole search space. To overcome this issue, We propose in this paper three parallel B&B approaches based on shared memory to exploit the multi-core CPU processors: First, a work-stealing approach where several instances of the B&B algorithm explore a single search tree concurrently achieving speedups up to 24 faster than the sequential version. Second, a tree-based approach where multiple parts of the search tree are explored simultaneously by independent B&B instances achieving speedups up to 28. Finally, Due to the irregular nature of the GED problem, two load-balancing strategies are proposed to ensure a fair workload between parallel processes achieving impressive speedups up to 300. all experiments have been carried out on well-known datasets
  • Thumbnail Image
    Item
    Graph Edit Distance Compacted Search Tree
    (Springer, Cham, 2022) Chegrane, Ibrahim; Hocine, Imane; Yahiaoui, Saïd; Bendjoudi, Ahcene; Nouali_Taboudjemat, Nadia
    We propose two methods to compact the used search tree during the graph edit distance (GED) computation. The first maps the node information and encodes the different edit operations by numbers and the needed remaining vertices and edges by BitSets. The second represents the tree succinctly by bit-vectors. The proposed methods require 24 to 250 times less memory than traditional versions without negatively influencing the running time.
  • Thumbnail Image
    Item
    Multi-objective offline and online path planning for UAVs under dynamic urban environment
    (2022-03) Sadallah, Nassim; Yahiaoui, Saïd; Bendjoudi, Ahcene; Nouali-Taboudjemat, Nadia
    This paper presents a multi-objective hybrid path planning method MOHPP for unmanned aerial vehicles (UAVs) in urban dynamic environments. Several works have been proposed to find optimal or near-optimal paths for UAVs. However, most of them did not consider multiple decision criteria and/or dynamic obstacles. In this paper, we propose a multi-objective offline/online path planning method to compute an optimal collision-free path in dynamic urban environment, where two objectives are considered: the safety level and the travel time. First, we construct two models of obstacles; static and dynamic. The static obstacles model is based on Fast Marching Square (FM2) method to deal with the uncertainty of the geography map, and the unexpected dynamic obstacles model is constructed using the perception range and the safety distance of the UAV. Then, we develope a jointly offline and online search mechanism to retrieve the optimal path. The offline search is applied to find an optimal path vis-a-vis the static obstacles, while the online search is applied to quickly avoid unexpected dynamic obstacles. Several experiments have been performed to prove the efficiency of the proposed method. In addition, a Pareto front is extracted to be used as a tool for decision making.
  • Thumbnail Image
    Item
    Reachability in big graphs : A distributed indexing and querying approach
    (Elsevier, 2021-09) Hocine, Imane; Yahiaoui, Saïd; Bendjoudi, Ahcene; Nouali-Taboudjemat, Nadia
    The advent of Big graphs characterized by their enormous number of nodes, with multiple edges between them makes the existing reachability query indexing approaches unable to guarantee a reasonable time for both the index construction and query steps. Therefore a novel approach that takes into account these new characteristics during the graph processing is needed. In this paper, we propose an Overlay Graph-based Distributed Reachability Indexing approach (ODRI), an indexing scheme through which the index construction and reachability query are processed in a parallel and distributed manner. The key idea of ODRI is to process a Big graph as a set of smaller subgraphs (partitions) interconnected to each other through an overlay graph. In this way, the partitions can be indexed in parallel and, at the same time, the reachability information can also be extracted. Hence, the index construction and query processing time will be reduced significantly. Therefore, ODRI ensures the scalability of Big graphs, which is a challenge for the existing reachability approaches. Besides, we formally prove that this strategy preserves the reachability properties. Using real-life data, we experimentally verify that our approach outperforms the state-of-the-art methods, and is scalable in terms of the number of partitions, regardless of how graphs are distributed.