Browsing by Author "Kheddouci, Hamamache"

Now showing 1 - 10 of 10
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    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.
  • Thumbnail Image
    Item
    TopCoF: A Topology Control Framework for Wireless Ad hoc Networks
    (IEEE, 2010-12) Yahiaoui, Saïd; Belhoul, Yacine; Faoudi, Farid; Kheddouci, Hamamache
    Topology Control (TC) is a well known technique used in wireless ad hoc and sensor networks to reduce energy consumption. This technique coordinates the decisions of network nodes about their transmission power to save energy, prolong network lifetime, and mitigate MAC-level medium contention, while maintaining network connectivity. In order to ease the implementation and the study in systematic way of proposed TC protocols, in terms of energy usage and network graph properties, we propose a new framework based on NS-2 simulator. The framework is named TopCoF and composed of two main parts. The first one consists of a set of NS-2 extensions to support TC, while the second is a graphical user interface for statistical analysis and visualization of simulation results traced by the first part. TopCoF is modular and generic since it implements a set of basic components used by TC protocols.
  • Thumbnail Image
    Item
    TopCoF: NS2-based Topology Control Framework for Wireless Ad hoc Networks
    (CERIST, 2010-02) Yahiaoui, Saïd; Belhoul, Yacine; Faoudi, Farid; Kheddouci, Hamamache
    Topology Control (TC) is the most well known technique used in wireless ad hoc and sensor networks to reduce energy consumption and radio interferences. This technique coordinates the decisions of network nodes about their transmission power to save energy, prolong network lifetime, and mitigate MAC-level medium contention, while maintaining network connectivity. In order to ease the implementation and the study in systematic way of proposed TC protocols and algorithms, in terms of energy usage and network graph properties, we propose a new framework based on NS-2 simulator. The framework is named TopCoF and composed of two main parts. The first one consists of a set of NS-2 extensions to support TC, while the second is a graphical user interface for statistical analysis and visualization of simulation results traced by the first part. TopCoF is modular and generic since it implements a set of basic components used by TC protocols. We illustrate, by an example, how TopCoF facilitates the implementation and performance evaluation of TC