Browsing by Author "Mehdi, Malika"

Now showing 1 - 11 of 11
  • Thumbnail Image
    Item
    An Efficient Measure for Evaluating Association Rules
    (CERIST, 2014-06-24) Djenouri, Youcef; Gheraibai, Youcef; Mehdi, Malika; Bendjoudi, Ahcène; Nouali-Taboudjemat, Nadia
    Association rules mining (ARM) has attracted a lot of attention in the last decade. It aims to extract a set of relevant rules from a given database. In order to evaluate the quality of the resulting rules, existing measures, such as support and confidence, allow to evaluate the resulted rules of ARM process separately, missing the different dependencies between the rules. This paper addresses the problem of evaluating rules by taking into account two aspects : (1) The accuracy of the returned rules on the input data and (2) the distance between the returned rules. The rules set that covers the maximum of rules space is considered. To analyze the behavior of the proposed measure, it has been tested on two recent ARM algorithms BSO-ARM and HBSO-TS.
  • Thumbnail Image
    Item
    An Efficient Measure for Evaluating Association Rules
    (2014-08) Djenouri, Youcef; Gheraibai, Youcef; Mehdi, Malika; Bendjoudi, Ahcène
    Association rules mining (ARM) has attracted a lot of attention in the last decade. It aims to extract a set of relevant rules from a given database. In order to evaluate the quality of the resulting rules, existing measures, such as support and confidence, allow to evaluate the resulted rules of ARM process separately, missing the different dependencies between the rules. This paper addresses the problem of evaluating rules by taking into account two aspects: (1) The accuracy of the returned rules on the input data and (2) the distance between the returned rules. The rules set that covers the maximum of rules space is considered. To analyze the behavior of the proposed measure, it has been tested on two recent ARM algorithms BSO-ARM and HBSO-TS.
  • Thumbnail Image
    Item
    Data reordering for minimizing threads divergence in GPU-based evaluating association rules
    (CERIST, 2015-03-26) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Habbas, Zineb; Nouali-Taboudjemat, Nadia
    This last decade, the success of Graphics Processor Units (GPUs) has led researchers to launch a lot of works on solving large complex problems by using these cheap and powerful architecture. Association Rules Mining (ARM) is one of these hard problems requiring a lot of computational resources. Due to the exponential increase of data bases size, existing algorithms for ARM problem become more and more inefficient. Thus, research has been focusing on parallelizing these algorithms. Recently, GPUs are starting to be used to this task. However, their major drawback is the threads divergence problem. To deal with this issue, we propose in this paper an intelligent strategy called Transactions- based Reordering "TR" allowing an efficient evaluation of association rules on GPU by minimizing threads divergence. This strategy is based on data base re-organization. To validate our proposition, theoretical and experimental studies have been carried out using well-known synthetic data sets. The results are very promising in terms of minimizing the number of threads divergence.
  • Thumbnail Image
    Item
    Data reordering for minimizing threads divergence in GPU-based evaluating association rules
    (2015-06) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Habbas, Zineb; Nouali-Taboudjemat, Nadia
    This last decade, the success of Graphics Processor Units (GPUs) has led researchers to launch a lot of works on solving large complex problems by using these cheap and powerful architecture. Association Rules Mining (ARM) is one of these hard problems requiring a lot of computational resources. Due to the exponential increase of data bases size, existing algorithms for ARM problem become more and more inefficient.Thus, research has been focusing on parallelizing these algorithms. Recently, GPUs are starting to be used to this task. However, their major drawback is the threads divergence problem. To deal with this issue, we propose in this paper an intelligent strategy called transactions-based Reordering ”TR” allowing an efficient evaluation of association rules on GPU by minimizing threads divergence. This strategy is based on data base re-organization. To validate our proposition, theoretical and experimental studies have been carried out using well-known synthetic datasets. The results are very promising in terms of minimizing the number of threads divergence.
  • Thumbnail Image
    Item
    GPU-based Bees Swarm Optimization for Association Rules Mining
    (Springer, 2014) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, Zineb
    Association Rules Mining (ARM) is a well-known combinatorial optimization problem aiming at extracting relevant rules from given large scale data sets. According to the state of the art, the bio-inspired methods proved their efficiency by generating acceptable solutions in a reasonable time when dealing with small and medium size instances. Unfortunately, to cope with large instances such as the webdocs benchmark, these methods require more and more powerful processors and are time expensive. Nowadays, computing power is no longer a real issue. It can be provided by the power of emerging technologies such as GPUs that are massively multi-threaded processors. In this paper, we investigate the use of GPUs to speed up the computation. We propose two GPU-based bees swarm algorithms for association rules mining (SE-GPU and ME-GPU). SE-GPU aims at evaluating one rule at a time where each thread is associated with one transaction, whereas ME-GPU evaluates multiple rules in parallel on GPU where each thread is associated with several transactions. To validate our approaches, the two algorithms have been executed to solve well-known large ARM instances. Real experiments have been carried out on an Intel Xeon 64 bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our approaches improve the execution time up to x100 over the sequential mono-core BSO-ARM algorithm. Moreover, the proposed approaches have been compared with CPU multi-core ones (1 to 8 cores). The results show that they are faster than the multi-core versions what ever the number of used cores.
  • Thumbnail Image
    Item
    Parallel Association Rules Mining Using GPUs and Bees Behaviors
    (CERIST, 2014-06-24) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, Zineb
    This paper addresses the problem of association rules mining with large data sets using bees behaviors. The bees swarm optimization method have been successfully applied on small and medium data size. Nevertheless, when dealing Webdocs benchmark (the largest benchmark on the web), it is bluntly blocked after more than 15 days. Additionally, Graphic processor Units are massively threaded providing highly intensive computing and very usable by the optimization research community. The parallelization of such method on GPU architecture can be deal large data sets as the case of WebDocs in real time. In this paper, the evaluation process of the solutions is parallelized. Experimental results reveal that the suggested method outperforms the sequential version at the order of ×100 in most data sets, furthermore, the WebDocs benchmark is handled with less than ten hours.
  • Thumbnail Image
    Item
    Parallel B&B Algorithm for Hybrid Multi-core/GPU Architectures
    (CERIST, 2013) Bendjoudi, Ahcène; Mehdi, Malika
    B&B algorithms are well known techniques for exact solving of combinatorial optimization problems. They perform an implicit enumeration of the search space instead of exhaustive one. Based on a pruning technique, they reduce considerably the computation time required to explore the whole search space. Nevertheless, these algorithms remain inefficient when dealing with large combinatorial optimization instances. They are time-intensive and they require a huge computing power to be solved optimally. Nowadays, multi-core-based processors and GPU accelerators are often coupled together to achieve impressive performances. However, classical B&B algorithms must be rethought to deal with their two divergent architectures. In this paper, we propose a new B&B approach exploiting both the multi-core aspect of actual processors and GPU accelerators. The proposed approaches have been executed to solve FSP instances that are well-known combinatorial optimization benchmarks. Real experiments have been carried out on an Intel Xeon 64-bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our hybrid B&B approach speeds up the execution time up to x123 over the sequential mono-core B&B algorithm.
  • Thumbnail Image
    Item
    Parallel B&B Algorithm on Hybrid Multicore/GPU Architecture
    (IEEE, 2013-11-15) Bendjoudi, Ahcène; Chekini, Mehdi; Gharbi, Makhlouf; Mehdi, Malika; Benatchba, Karima; Sitayeb-Benbouzid, Fatima; Melab, Nouredine
    B&B algorithms are well known techniques for exact solving of combinatorial optimization problems (COP). They perform an implicit enumeration of the search space instead of exhaustive one. Based on a pruning technique, they reduce considerably the computation time required to explore the whole search space. Nevertheless, these algorithms remain inefficient when dealing with large combinatorial optimization instances. They are time-intensive and they require a huge computing power to be solved optimally. Nowadays, multi-core-based processors and GPU accelerators are often coupled together to achieve impressive performances. However, classical B&B algorithms must be rethought to deal with their two divergent architectures. In this paper, we propose a new B&B approach exploiting both the multi-core aspect of actual processors and GPU accelerators. The proposed approaches have been executed to solve FSP instances that are well-known combinatorial optimization benchmarks. Real experiments have been carried out on an Intel Xeon 64-bit quad-core processor E5520 coupled to an Nvidia Tesla C2075 GPU device. The results show that our hybrid B&B approach speeds up the execution time up to x123 over the sequential mono-core B&B algorithm.
  • Thumbnail Image
    Item
    Parallel Rules Mining Using GPUs and Bees Behaviors
    (2014-08) Djenouri, Youcef; Bendjoudi, Ahcène; Mehdi, Malika; Nouali-Taboudjemat, Nadia; Habbas, Zineb
    This paper addresses the problem of association rules mining with large data sets using bees behaviors. The bees swarm optimization method have been successfully applied on small and medium data size. Nevertheless, when dealing Webdocs benchmark (the largest benchmark on the web), it is bluntly blocked after more than 15 days. Additionally, Graphic processor Units are massively threaded providing highly intensive computing and very usable by the optimization research community. The parallelization of such method on GPU architecture can be deal large data sets as the case of WebDocs in real time. In this paper, the evaluation process of the solutions is parallelized. Experimental results reveal that the suggested method outperforms the sequential version at the order of ×100 in most data sets, furthermore, the WebDocs benchmark is handled with less than ten hours.
  • Thumbnail Image
    Item
    Reducing thread divergence in GPU-based bees swarm optimization applied to association rule mining
    (John Wiley & Sons, Ltd., 2016) Bendjoudi, Ahcène; Djenouri, Youcef; Habbas, Zineb; Mehdi, Malika; Djenouri, Djamel
    The association rules mining (ARM) problem is one of the most important problems in the area of data mining. It aims at finding all relevant association rules from transactional databases. It is CPU time intensive and requires a huge computing power when dealing with large transactional databases. To deal with this issue, Graphics Processing Units (GPUs) are a powerful tool to speed up the search process. However, their performance is closely subject to thread/branch divergence resulting from the single instruction multiple data parallel model of GPUs. In this paper, we propose three approaches based on database reorganization, aiming to reduce thread divergence in GPU-based bees swarm optimization metaheuristic for ARM, respectively, named block-based reordering, transactions-based reordering, and transactions-based reordering with median value. Theoretical and experimental studies have been carried out using well-known large ARM instances. The experiments have been performed on an Intel Xeon 64 bit quad-core processor E5520 coupled to Nvidia Tesla C2075 448 cores. The results show that the proposed approaches minimize considerably the number of thread divergence and improve the overall execution time. Indeed, the number of thread divergence occurrences has been reduced by up to eight times making the execution much faster.
  • Thumbnail Image
    Item
    Solving the three dimensional quadratic assignment problem on a computational grid
    (Springer US, 2013-10) Mezmaz, Mohand; Mehdi, Malika; Bouvry, P.
    The exact resolution of large instances of combinatorial optimization problems, such as three dimensional quadratic assignment problem (Q3AP), is a real challenge for grid computing. Indeed, it is necessary to reconsider the resolution algorithms and take into account the characteristics of such environments, especially large scale and dynamic availability of resources, and their multi-domain administration. In this paper, we revisit the design and implementation of the branch and bound algorithm for solving large combinatorial optimization problems such as Q3AP on the computational grids. Such gridification is based on new ways to efficiently deal with some crucial issues, mainly dynamic adaptive load balancing and fault tolerance. Our new approach allowed the exact resolution on a nation-wide grid of a difficult Q3AP instance. To solve this instance, an average of 1,123 computing cores were used for less than 12 days with a peak of around 3,427 computing cores.