Academic & Scientific Articles

Permanent URI for this communityhttp://dl.cerist.dz/handle/CERIST/3

Browse

Has files: YesSubject: search.filters.subject.Big graphs

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Distributed Partial Simulation for Graph Pattern Matching
    (The Computer Journal, 2022-11-21) Aissam Aouar; Saı̈d Yahiaoui; Lamia Sadeg; Nadia Nouali-Taboudjemat; Kadda Beghdad Bey
    Pattern matching in big graphs is important for different modern applications. Recently, this problem was defined in terms of multiple extensions of graph simulation, to reduce complexity and capture more meaningful results. These results were achieved through the relaxation of commonly used constraint in subgraph isomorphism pattern matching. Nevertheless, these graph simulation variant models are still too strict to provide results in many cases, especially when analyzed graphs contain anomalies and incomplete information. To deal with this issue, we introduce a new graph pattern matching (GPM) method, called partial simulation, capable of retrieving matches despite missing parts of the pattern graph, such as vertices and/or edges. Furthermore, considering the number and inequality of the outputs, we define a relevance function to compute a value expressing how each match vertex respects the pattern graph. Similarly, we define partial dual simulation GPM that returns vertices that satisfy a part of the dual simulation constraints and assigns a relevance value to them. Additionally, we provide distributed scalable algorithms to evaluate the proposed partial simulation methods based on the distributed vertex-centric programming paradigm. Finally, our experiments on real-world data graphs demonstrate the effectiveness of the proposed models and the efficiency of their associated algorithms.
  • 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.