CERIST DL :: Browsing by Author "Yahiaoui, Saïd"

Browsing by Author "Yahiaoui, Saïd"

Now showing 1 - 20 of 27

A Graph Approach for Enhancing Process Models Matchmaking
(CERIST, 2015-04) Belhoul, Yacine; Yahiaoui, Saïd
Recent attempts have been done to measure similarity of process models based on graph-edit distance. This problem is known to be difficult and computational complexity of exact algorithms for graph matching is exponential. Thus, heuristics should be proposed to obtain approximations. Spectral graph matching methods, in particular eigenvalue-based projections, are know to be fast but they lost some quality in the obtained matchmaking. In this paper, we propose a graph approach for the problem of inexact matching of process models. Our approach combines a spectral graph matching method and a string comparator based algorithm in order to improve the quality of process model matchmaking. The proposed method performs the matchmaking at both structural and semantic levels. Experimentation is provided to show the performance of our method, compared to previous work, to rank a collection of process model according to a particular query.
A Graph Approach for Enhancing Process Models Matchmaking
(IEEE, 2015-06-27) Belhoul, Yacine; Yahiaoui, Saïd; Haddad, Mohammed; Gater, Ahmed; Kheddouci, Hamamache; Bouzeghoub, Mokrane
Recent attempts have been done to measure similarity of process models based on graph matching. This problem is known to be difficult and its computational complexity is exponential. Thus, heuristics should be proposed to obtain approximations. Spectral graph matching methods, in particular eigenvalue-based projections, are know to be fast but they lost some quality in the obtained matchmaking. In this paper, we propose a graph approach for the problem of inexact matching of process models. Our approach combines a spectral graph matching method and a string comparator based algorithm in order to improve the quality of process models matchmaking. The proposed method performs the matchmaking at both structural and semantic levels. Experimentation is provided to show the performance of our method to rank a collection of process models according to a particular user query, compared to previous work.
A Survey on Distributed Graph Pattern Matching in Massive Graphs
(ACM, 2021-02) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Kheddouci, Hamamache
Besides its NP-completeness, the strict constraints of subgraph isomorphism are making it impractical for graph pattern matching (GPM) in the context of big data. As a result, relaxed GPM models have emerged as they yield interesting results in a polynomial time. However, massive graphs generated by mostly social networks require a distributed storing and processing of the data over multiple machines, thus, requiring GPM to be revised by adopting new paradigms of big graphs processing, e.g., Think-Like-A-Vertex and its derivatives. This article discusses and proposes a classification of distributed GPM approaches with a narrow focus on the relaxed models.
AdSIP: Decentralized SIP for Mobile Ad Hoc Networks
(IEEE, 2012-03) Yahiaoui, Saïd; Belhoul, Yacine; Nouali-Taboudjemat, Nadia; Kheddouci, Hamamache
SIP signaling protocol relies on centralized SIP servers deployed on the infrastructure of the network to route SIP messages in order to enable user endpoints to discover each other. However, the lack of the infrastructure in ad hoc networks requires that the network nodes support the tasks of participants discovery and SIP messages routing. In this paper, we propose AdSIP protocol which is a completely distributed architecture for SIP that implements SIP servers in selected nodes. The SIP servers are selected using a distributed algorithm constructing a connected minimal global offensive alliance. AdSIP is implemented and compared under NS-2 with TCA protocol which uses a cluster based approach. The simulation results show the advantages of AdSIP and confirm that it is adapted to mobile ad hoc networks by giving low session establishment time, low control overhead and high service availability.
AdSIP: Decentralized SIP for Mobile Ad hoc Networks
(CERIST, 2011-12) Nouali-Taboudjemat, Nadia; Belhoul, Yacine; Yahiaoui, Saïd
SIP (Session Initiation Protocol) is an IETF signaling protocol designed to create, modify and terminate sessions between two or many users in multimedia applications. The implementation of SIP needs the use of proxy servers which are centralized entities to route SIP requests and responses to enable user endpoints to discover each other. However, the infrastructureless of ad hoc networks requires that the network nodes support the tasks of participants’ discovery and SIP routing messages. In this paper, we propose the AdSIP protocol which is a completely distributed architecture for SIP that implements the proxy servers in selected nodes. The proxy servers are selected using a distributed algorithm constructing a connected minimal global offensive alliance. AdSIP is implemented and compared under NS-2 with another protocol which uses a cluster based approach. The simulation results show the advantages of AdSIP and demonstrate that it is adapted to mobile ad hoc networks by giving low session establishment time, low control overhead and high service availability.
Coloring based approach for matching unrooted and/or unordered trees
(Elsevier, 2013-04) Yahiaoui, Saïd; Haddad, Mohammed; Effantin, Brice; Kheddouci, Hamamache
We consider the problem of matching unrooted unordered labeled trees, which refers to the task of evaluating the distance between trees. One of the most famous formalizations of this problem is the computation of the edit distance defined as the minimum-cost sequence of edit operations that transform one tree into another. Unfortunately, this problem has been proved to be NP-complete. In this paper, we propose a new algorithm to measure distance between unrooted unordered labeled trees. This algorithm uses a specific graph coloring to decompose the trees into small components (stars and bistars). Then, it determines a distance between two trees by computing the edit distance between their components. We prove that the proposed distance is a pseudo-metric and we analyze its time complexity. Our experimental evaluations on large synthetic and real world datasets confirm our analytical results and suggest that the distance we propose is accurate and its algorithm is scalable.
DIAG a diagnostic web application based on lung CT Scan images and deep learning
(IOS Press Ebooks, 2021-05-29) Hadj Bouzid, Amel Imene; Yahiaoui, Saïd; Lounis, Anis; Berrani, Sid-Ahmed; Belbachir, Hacène; Naili, Qaid; Abdi, Mohamed El Hafedh; Bensalah, Kawthar; Belazzougui, Djamal
Coronavirus disease is a pandemic that has infected millions of people around the world. Lung CT-scans are effective diagnostic tools, but radiologists can quickly become overwhelmed by the flow of infected patients. Therefore, automated image interpretation needs to be achieved. Deep learning (DL) can support critical medical tasks including diagnostics, and DL algorithms have successfully been applied to the classification and detection of many diseases. This work aims to use deep learning methods that can classify patients between Covid-19 positive and healthy patient. We collected 4 available datasets, and tested our convolutional neural networks (CNNs) on different distributions to investigate the generalizability of our models. In order to clearly explain the predictions, Grad-CAM and Fast-CAM visualization methods were used. Our approach reaches more than 92% accuracy on 2 different distributions. In addition, we propose a computer aided diagnosis web application for Covid-19 diagnosis. The results suggest that our proposed deep learning tool can be integrated to the Covid-19 detection process and be useful for a rapid patient management.
Distributed graph pattern matching via bounded dual simulation
(Elsevier, 2022-09) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia; Kheddouci, Hamamache
Graph Pattern Matching (GPM) finds subgraphs of a large data graph that are similar to an input query graph. It has many applications, such as pattern recognition, detecting plagiarism, and finding communities in social networks. Current real-world applications generate massive amounts of data that cannot be stored on the memory of a single machine, which raises the need for distributed storage and processing. Recent relaxed GPM models, although of polynomial time complexity, are nevertheless not distributed by nature. Moreover, the existing relaxed GPM algorithms are limited in terms of scalability. In this paper, we propose Bounded Dual Simulation (BDSim) as a new relaxed model for a scalable evaluation of GPM in massive graphs. BDSim captures more semantic similarities compared to graph simulation, dual simulation, and even strong simulation. It preserves the vertices’ proximity by eliminating cycles of unbounded length from the resulting match graph. Furthermore, we propose distributed vertex-centric algorithms to evaluate BDSim. We prove their effectiveness and efficiency through detailed theoretical validation and extensive experiments conducted on real-world and synthetic datasets. To the best of our knowledge, BDSim is the first relaxed GPM model that captures the cyclic structure of the query graph while being feasible in cubic time.
Efficient approximate approach for graph edit distance problem
(Elsevier, 2021-11) Dabah, Adel; Chegrane, Ibrahim; Yahiaoui, Saïd
Graph Edit Distance (GED) problem is a well-known tool used to measure the similarity/dissimilarity between two graphs. It searches for the best set of edit operations (in terms of cost) that transforms one graph into another. Due to the NP-hardness nature of the problem, the search space increases exponentially making exact approaches impossible to use for large graphs. In this context, there is a huge need for approaches that give near-optimal results in reasonable time. In this paper, we propose a tree-based approximate approach for dealing with GED problem. It operates on a search tree that models all possible solutions of the problem. Since exploring the whole tree is impractical; this approach keeps only the best nodes at each level of the tree for further exploration. This reduces enormously the execution time without scarifying the solution quality. Experiments using small and medium size data-sets show the low deviation of our results as compared to the optimal results of a Depth First Search algorithm. Moreover, our approach show a strong scalability potential by dealing with large data-sets in low execution time.
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
Efficient parallel edge-centric approach for relaxed graph pattern matching
(Springer, 2022-02) Bouhenni, Sarra; Yahiaoui, Saïd; Nouali-Taboudjemat, Nadia
Prior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude.
Efficient self-stabilizing algorithms for minimal total k-dominating sets in graphs
(Elsevier, 2014-07) Belhoul, Yacine; Yahiaoui, Saïd; Kheddouci, Hamamache
We propose the first polynomial self-stabilizing distributed algorithm for the minimal total dominating set problem in an arbitrary graph. Then, we generalize the proposed algorithm for the minimal total k -dominating set problem. Under an unfair distributed scheduler, the proposed algorithms converge in O(mn) moves starting from any arbitrary state, and require O(log n) storage per node.
Fast parallel algorithms for finding elementary circuits of a directed graph: a GPU-based approach
(Springer Science+Business Media, 2023-03) Benachour, Amira; Yahiaoui, Saïd; El Baz, Didier; Nouali‑Taboudjemat, Nadia; Kheddouci, Hamamache
Circuits in a graph are interesting structures and identifying them is of an important relevance for many applications. However, enumerating circuits is known to be a difficult problem, since their number can grow exponentially. In this paper, we propose fast parallel approaches for enumerating elementary circuits of directed graphs based on graphics processing unit (GPU). Our algorithms are based on a massive exploration of the graph in a breadth-first search strategy. Algorithm V-FEC explores the graph starting from different vertices simultaneously. To further reduce the search space, we present T-FEC, another algorithm that uses triplets as an initial set to start exploring. To the best of our knowledge, those are the first parallel GPU-based algorithms for finding all circuits of a given graph. In addition, they find circuits of a given length and circuits with a specific vertex or edge. The evaluation results show that the proposed approaches achieve up to 190x speed-up over Johnson’s algorithm, one of the most efficient sequential algorithms for finding circuits.
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.
ICTs Integration for Disaster Management
(CERIST, 2014-03-24) Yahiaoui, Saïd; Benkhelifa, Imane; Saadi, Hocine; Bencherif, Tinhinane; Bouchama, Nadir; Seba, Abderazek; Nouali-Taboudjemat, Nadia
Information technology for Enhancing Disaster Management
(CERIST, 2009-04) Nouali-Taboudjemat, Nadia; Bouchama, Nadir; Bendjoudi, Ahcène; Babakhouya, Abdelaziz; Yahiaoui, Saïd; Belhoul, Yacine; Saadi, Hocine
Responding to natural or man-made disasters, in a timely and effective manner, can reduce deaths and injuries as well as economic losses. Predicated on the assumption that better information leads to efficient decision-making and more effective performance of crisis response, research projects applying advanced information technology solutions to the crisis management field have emerged. This paper provides an overview of most recent projects, in this area, all over the world. Furthermore, the study highlights that using scalable and robust IT solutions can drastically facilitate access to the right information, by the right individuals and organizations, at the right time.
Information technology for Enhancing Disaster Management
(2009-05-23) Nouali-Taboudjemat, Nadia; Bouchama, Nadir; Bendjoudi, Ahcène; Babakhouya, Abdelaziz; Yahiaoui, Saïd; Belhoul, Yacine; Zeghilet, Houda; Guellati, Nabil
Responding to natural or man-made disasters, in a timely and effective manner, can reduce deaths and injuries as well as economic losses. Predicated on the assumption that better information leads to efficient decision-making and more effective performance of crisis response, research projects applying advanced information technology solutions to the crisis management field have emerged. This paper provides an overview of most recent projects, in this area, all over the world. Furthermore, the study highlights that using scalable and robust IT solutions can drastically facilitate access to theright information, by the right individuals and organizations,at the right time.
Lifetime-Aware Backpressure : A New Delay-Enhanced Backpressure-Based Routing Protocol
(IEEE, 2019-03) Kabou, Abdelbaset; Nouali-Taboudjemat, Nadia; Djahel, Soufiene; Yahiaoui, Saïd; Nouali, Omar
Dynamic backpressure is a highly desirable family of routing protocols known for their attractive mathematical properties. However, these protocols suffer from a high end-to-end delay making them inefficient for real-time traffic with strict end-to-end delay requirements. In this paper, we address this issue by proposing a new adjustable and fully distributed backpressure-based scheme with low queue management complexity, named Lifetime-Aware Backpressure (LTA-BP). The novelty in the proposed scheme consists in introducing the urgency level as a new metric for service differentiation among the competing traffic flows in the network. Our scheme not just significantly improves the quality of service provided for real-time traffic with stringent end-to-end delay constraints, but interestingly protects also the flows with softer delay requirements from being totally starved. The proposed scheme has been evaluated and compared against other state-of-the-art routing protocol, using computer simulation, and the obtained results show its superiority in terms of the achieved end-to-end delay and throughput.
Mobility and Performance of Routing Protocols in Wireless Mobile Ad hoc Networks
(CERIST, 2010-02) Belhoul, Yacine; Yahiaoui, Saïd; Kheddouci, Hamamache
Among routing protocols designed for wireless mobile ad hoc networks, DSDV from the proactive class and AODV from the reactive one, are well known. In this paper, we evaluate the performance of these protocols using NS-2 simulator. We use three mobility models, namely: the RWP entity model, as well as the RPGM and Column group models. Scenarios considered in simulations take into account several factors that affect the performance of routing protocols. We compare them in term of average end-to-end delay, normalized routing load, and packet delivery fraction. The results we obtain show that the performance of routing protocols in mobile ad hoc networks strongly depends on the used mobility models and the considered scenarios.
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.

Browsing by Author "Yahiaoui, Saïd"

Results Per Page

Sort Options