=Paper=
{{Paper
|id=Vol-2326/short3
|storemode=property
|title=Using G-skyline to improve Decision-Making
|pdfUrl=https://ceur-ws.org/Vol-2326/short3.pdf
|volume=Vol-2326
|authors=Sana Nadouri,Zaidi Sahnoun,Allel Hadjali
|dblpUrl=https://dblp.org/rec/conf/icaase/NadouriSH18
}}
==Using G-skyline to improve Decision-Making==
<pdf width="1500px">https://ceur-ws.org/Vol-2326/short3.pdf</pdf>
<pre>
                             Using G-skyline to improve Decision-Making

           Sana Nadouri                                       Zaidi Sahnoun                                  Allel Hadjali
       LIRE/LIAS laboratories.                             LIRE Laboratory UC2.                        LIAS Laboratory ENSMA.
  Constantine-Futuroscope, 25000-86360                          Constantine, 25000                            Futuroscope, 86360
  sana.nadouri@univ-constantine2.dz/ensma.fr            zaidi.sahnoun@univ-constantine2.dz                    Allel.hadjali@ensma.fr




                                                                         queries requiring the analysis of not only individual
                                                                         tuples but also their combinations, for that reason,
                                                                         Groups skyline was introduced.
                            Abstract                                        In this paper, we propose a method to reinforce our
                                                                         Multi-agent distributed decision support system using
      Skyline is an operator that can help users
                                                                         groups skyline [Nadouri18].
      making decisions using a multidimensional data
                                                                            The remainder of the paper is organized as follows.
      and conflicting criteria. Skyline is based on
                                                                         Section 2, introduces the Skyline operator, Groups
      Pareto dominance relationship, it returns
                                                                         Skyline, Decision support systems and Distributed
      objects that are not dominated by any other
                                                                         decision support systems. Section 3, provides an initial
      object in the database. Recently, the skyline
                                                                         description of the approach using a sequence diagram.
      definition was expanded to group decision
                                                                         Finally, Section 4 concludes the paper and draws some
      making to meet complex real life needs
                                                                         future research directions.
      encountered in many modern domain
      applications. We used the groups skyline in our
      architecture to reinforce the Multi-agent                          2. Background and state of art
      distributed decision support system by                             2.1. The Skyline operator
      integrating the process to the comparison                              The skyline operator returns records in dataset that
      agent. In this paper, we introduce the Skyline                     provide optimal trade-offs of multiple dimensions, since
      operator, Groups skyline and we propose to                         its introduction to the database community in
      integrate groups skyline to our internal                           [Borzsony01], the skyline operator had a real interest
      distributed     decision    support     system                     [Hose16],[Tiakas15],[Paolo18], which allows it to
      architecture.                                                      stand out of many other types of query preferences.
 Keywords - Skyline, Groups skyline, Decision                            Skyline is based on Paredo dominance concept that can
 support system, Distributed decision support                            be defined as follows:
 system                                                                  Definition (Dominance or Pareto), noted:≺, When
                                                                         having two tuples: p and q, if p is as good as q in all
 1. Introduction                                                         dimensions and better than q in at least one, then p
                                                                         dominate q (p≺q), if p≺q and simultaneously q≺p,
     The Skyline operator (Maxima or Pareto dominance                    then they are incomparable.
 relationship) is a multi-criteria analysis operator that                Formally (assuming that the smallest value is better):
 manages query complexity. Skyline extracts tuples from
 database using user preferences and returns the best                        p≺q ⇒ ∀ i∈[1,d] : pi ≤i qi and ∃j∈[1,d] : pj <j qj
 response. The skyline is very successful in the database
 filed since its introduction by Borzsony in 2001                        A set of algorithms were proposed, the most used are
 [Borzsony01], many algorithms were proposed to                          indexed or not indexed algorithms:
 retrieve objects that present the optimal combination of                     Indexed: Index - proposed in 2001 [Berrouigat15], [Tan01],
 the dataset characteristics in a local and distributed                        Bitmap - proposed in 2001 [Berrouigat15], [Tan01] NN -
 environment.                                                                  proposed in 2002 [Kossmann02], [Nguyen18], BBS - proposed
     Recently, the skyline definition and the local                            in 2003 [Papadias03], [Papadias05], [Nguyen18].
 algorithms become inadequate to answer various                               Not indexed: BNL - proposed in 2001 [Borzsony01],
                                                                               [Nguyen18], D&C – proposed in 2001 [Borzsony01], SFS –
Copyright © by the paper’s authors. Copying permitted only for private         proposed in 2005 [Chomicki03], LESS – proposed in 2005
and academic purposes.                                                         [Godfrey05].
In: Proceedings of the 3rd Edition of the International Conference on
Advanced Aspects of Software Engineering (ICAASE18), Constantine,
Algeria, 1,2-December-2018, published at http://ceur-ws.org

International Conference on Advanced Aspects of Software Engineering                                                            Page 141
ICAASE, December, 01-02, 2018
 Using G-skyline to improve Decision-Making                                                                         ICAASE'2018




 2.2. Group Skyline                                                             groups. It generates candidate groups in a
     Real-world applications require choosing groups of                         progressive manner and updates the resultant
 objects rather than individual objects, sport is one of                        groups skyline dynamically.
 them, selecting the best team based on a list of athletes
 requires comparing teams players by performance.                      2.   G-Skyline using stream data
 Another example is choosing a group of experts to                           Finding Group-Based Skyline over a Data
 review and evaluate papers based on the experts                               Stream in the Sensor Network: [Dong18]
 collective strength on multiple desired skills. Group                         they invoke the problem of Computing G-
 Skyline is also important in other domains e.g. group                         Skyline when a new point p arrives. First, they
 recommendation, investments selection, detection of                           check which layer the point p belongs to, and
 most dangerous places when fire or a crime is made,                           then update the graph to construct the new
 etc. The combination points or Groups Skyline is                              relationships between all the points, finally,
 defined as follows [Liu15]:                                                   they compute the G-Skyline based on the
                                                                               sharing strategy.
 Definition 1: Based on Skyline (called: G-Skyline).                         Efficient Processing of Skyline Group
 Given a dataset P of n points. p and p’ are two different                     Queries over a Data Stream: [guo16]
 points in P, p dominates p’ (p≺p’), if for all i, p[i]≤p’[i],                 authors store dominance information that
 and for at least one i, p[i]<p’[i] in 1≤i≤d.                                  could be reused. For each active object p, they
 Definition 2: Based on Group dominance (called G-                             maintain (1) the number of dominators,
                                                                               denoted by p:num and (2) objects that could
 Dominance). When having 2 groups: G=p1,p2,...,pk
                                                                               be dominated by p, denoted by p:dominatee.
 and G’=p’1,p’2,...,p’k, we say group G g-dominates                            When an object is added or removed, they
 group G’, denoted by G≺gG’, if we can find two                                update p:num and p:dominatee of each object
 permutations of the k points for G and G’,                                    influenced by p. Objects having fewer than k
 G=pu1,pu2,...,puk and G’=p’v1,p’v2,...,p’vk, such that                        dominators are reported as candidates.
 pui≤p’vi for all i (1≤i≤k) and pui≺p’vi for at least one i.
                                                                       2.3. Distributed decision support system (DDSS)
 We divide Groups Skyline algorithms intro two classes:                    DSS is defined in different ways, it is a system that
                                                                       assist decision makers when making their decisions, in
 1.   G-Skyline using static data                                      order to confirm or correct the decision [Poleto15]. In
       Top-k Skyline Groups Queries: [Zhu17]                          the same way that definitions vary by authors, there is
         returns k skyline groups, it combines skyline
                                                                       no standard architecture to define these systems, DSS
         groups and top-k queries using Bit vector to
                                                                       contains several parts and sub-parts that are listed
         store the dominated number of each point.
       Finding Pareto Optimal Groups: [Liu15]                         below. We have 5 basic components [Simon60],
         two algorithms were proposed: the point-wise                  [Otero18], [Chandiok16]: The database management
         and the unit group-wise algorithm. The                        system, The model management system, The knowledge
         authors present a structure that represents the               engine, The user interface and the user. The DSS
         points in a directed skyline graph and captures               process has 4 essential phases: Intelligence, Design,
         all the dominance relationship among the                      Choice, Implementation.
         points based on the notion of skyline layers.                     The system complexity and the distribution of
       On skyline groups: [Zhang14] they identified                   environments and systems require the distribution of the
         two anti-monotonic properties with varying                    decision. Currently, there is no definition to illustrate
         degrees of applicability: order-specific as well              DDSS structure since existing architectures depend on
         as weak candidate-generation property. The                    the problem to be solved. We define a DDSS as a set of
         authors propose three techniques, namely                      Decision support systems that communicate in a
         output compression, input pruning, and search                 distributed environment and share a common goal in
         space pruning.
                                                                       different sites, in other words, it is an extended version
       Group skyline computation: [im12] they
                                                                       of a DSS.
         proposed GDynamic an equivalent to a
         dynamic algorithm that fills a table of skyline




International Conference on Advanced Aspects of Software Engineering                                                     Page 142
ICAASE, December, 01-02, 2018
 Using G-skyline to improve Decision-Making                                                                         ICAASE'2018




 3. The proposition                                                    groups skyline concept to our Multi-agent Distributed
                                                                       decision support systems.
      We proposed a new approach called ADS2, which                        We are still developing the method. For validation,
 is based on the definition of the distributed decision                we will implement the GSM method, we will also
 support system modeled in the article [Nadouri18].                    improve the groups skyline algorithm, many challenges
      The internal architecture is modeled using Multi-                need to be considered, we can cite the issue of different
 Agent approach and contains mainly 6 components, one                  group size, groups are not extracted progressively, the
 of these components is the comparison Agent, the                      large number of possible points combination and the
 internal behavior of the comparison Agent is based on                 large number of output groups. Some of these issues
 the Groups Skyline process because each external DSS                  can be solved using relaxation methods and progressive
 will give a partial decision or a decision based on its               algorithms used in individual skyline algorithms. Finally,
 internal knowledge.                                                   we think about revisiting the dominance relationship for
 Using the same process of Groups Skyline we propose                   groups skyline definition.
 to integrate it to obtain a better decisions in time.
      As shown in Figure.1. the Agent compares the                     References
 different Decisions received from other DSSs (in this
                                                                       [Berrouigat15] Khadidja Berrouigat, Fatima Bensaha.
 example, we have 2 DSSs) using a G-Skyline algorithm,                          Recherche des skyline à base de l'algorithme
 the system returns the best combination of the proposed                        bitmap - Skyline search based on the bitmap
 decisions, the decisions are then sent to the DSSs to                          algorithm. Algeria: Abou Bekr Belkaid University,
 confirm or reinforce the process, the algorithm returns                        2015.
 the final decision if and only if the different DSSs agree            [Borzsony01] S. Borzsony, D. Kossmann, and K. Stocker.
 and the predefined decision time is not achieved.                              «The skyline operator.» 17th International
                                                                                Conference on Data Engineering. 2001.
                                                                       [Chandiok16] A. Chandiok and D. K. Chaturvedi. «Cognitive
                                                                                Decision Support System for medical diagnosis.»
                                                                                International Conference on Computational
                                                                                Techniques in Information and Communication
                                                                                Technologies (ICCTICT). 2016. 337-342.
                                                                       [Chomicki03] J. Chomicki and P. Godfrey and J. Gryz and
                                                                               D.Liang. «Skyline with presorting.» 19th
                                                                               International Conference on Data Engineering.
                                                                               2003. 717-719.
                                                                       [Dong18] Dong, Leigang and Liu, Guohua and Cui, Xiaowei
                                                                               and Li, Tianyu,. «Finding Group-Based Skyline over
                                                                               a Data Stream in the Sensor Network.» Information,
                                                                               2018: 33.
                                                                       [Godfrey05] Godfrey, Parke and Shipley, Ryan and Gryz,
                                                                                Jarek,. «Maximal Vector Computation in Large
                                                                                Data Sets.» the 31st International Conference on
                                                                                Very Large Data Bases. Trondheim, Norway:
                                                                                VLDB Endowment, 2005. 229-240.
                                                                       [guo16] guo. «Efficient processing of skyline group queries
                 Figure 1: The approach behavior                                over a data stream.» Tsinghua Science and
                                                                                Technology, 2016: 29-39.
 4. Conclusion and future work                                         [Hose16] Hose, Katja. «Skyline Queries.» Datenbank-
                                                                               Spektrum, 2016: 247-251.
     In this paper, we introduced the skyline and groups
                                                                       [im12] im. «Group skyline computation.» Information
 skyline concepts. We also proposed to integrate the                           Sciences, 2012: 151-169.




International Conference on Advanced Aspects of Software Engineering                                                      Page 143
ICAASE, December, 01-02, 2018
 Using G-skyline to improve Decision-Making                                                                         ICAASE'2018




 [Kossmann02] Kossmann, Donald and Ramsak, Frank and                   [Tiakas15] Tiakas, Eleftherios and Papadopoulos, Apostolos
         Rost, Steffen. «Shooting Stars in the Sky: An Online                   N and Manolopoulos, Yannis. «Skyline queries: An
         Algorithm for Skyline Queries.» 28th International                     introduction.» 6th International Conference on
         Conference on Very Large Data Bases. Hong                              Information,      Intelligence,   Systems    and
         Kong, China: VLDB Endowment, 2002. 275-286.                            Applications (IISA). IEEE, 2015. 1-6.
 [Liu15] Liu, Jinfei and Xiong, Li and Pei, Jian and Luo, Jun          [Zhang14] Zhang, Nan and Li, Chengkai and Hassan,
          and Zhang, Haoyu,. «Finding pareto optimal groups:                   Naeemul and Rajasekaran, Sundaresan and Das,
          Group-based skyline.» Proceedings of the VLDB                        Gautam,. «On Skyline Groups.» IEEE Transactions
          Endowment, 2015: 2086-2097.                                          on Knowledge and Data Engineering, 2014: 942-
 [Nadouri18] Sana Nadouri, Yassine Ouhammou, Zaidi                             956.
          Sahnoun and Allel Hadjali. «Towards a multi-agent            [Zhu17] Zhu, Haoyang and Zhu, Peidong and Li, Xiaoyong
          approach for distributed decision support systems.»                   and Liu, Qiang,. «Top-k Skyline Groups Queries.»
          27th IEEE International Conference on Enabling                        EDBT, 2017: 442-445.
          Technologies: Infrastructure for Collaborative
          Enterprises. Paris: IEEE, 2018. 6.
 [Nguyen18] Nguyen Ngoc Vinh. Spatial Skyline Query
         Algorithms. 13 04 2018. viblo.asia/p/spatial-
         skyline-query-algorithms.
 [Otero18] Abraham Otero. https://pdfs.semanticscholar.org.
          13 04 2018. https://pdfs.semanticscholar.org.
 [Paolo18]            Paolo          Ciaccia.       http://www-
             db.deis.unibo.it/courses/SI-
             M/slides/02.1.Skyline.pdf. 13 04 2018. http://www-
             db.deis.unibo.it/courses/SI-
             M/slides/02.1.Skyline.pdf.
 [Papadias03] Papadias, Dimitris and Tao, Yufei and Fu, Greg
          and Seeger, Bernhard. «An Optimal and Progressive
          Algorithm for Skyline Queries.» ACM SIGMOD
          International Conference on Management of Data.
          San Diego, California: ACM, 2003. 467-478.
 [Papadias05] Papadias, Dimitris and Tao, Yufei and Fu, Greg
          and Seeger, Bernhard. «Progressive Skyline
          Computation in Database Systems.» ACM Trans.
          Database Syst., 2005: 41-82.
 [Poleto15] Poleto, Thiagoand de Carvalho, Victor Diogho
          Heuerand Costa, Ana Paula Cabral Seixas,. «The
          Roles of Big Data in the Decision-Support Process:
          An Empirical Investigation.» Decision Support
          Systems V - Big Data Analytics for Decision
          Making, 2015: 10-21.
 [Simon60] Simon, H.A,. The New Science of Management
         Decision. Harper & Row, 1960.
 [Tan01] Tan, Kian-Lee and Eng, Pin-Kwang and Ooi, Beng
          Chin. «Efficient Progressive Skyline Computation.»
          27th International Conference on Very Large Data
          Bases. San Francisco, CA, USA: Morgan Kaufmann
          Publishers Inc., 2001. 301-310.




International Conference on Advanced Aspects of Software Engineering                                                     Page 144
ICAASE, December, 01-02, 2018

</pre>