Skyline Groups Are Ideals. An Efficient Algorithm for Enumerating Skyline Groups - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Skyline Groups Are Ideals. An Efficient Algorithm for Enumerating Skyline Groups

Résumé

Skyline queries are multicriteria queries that are of great interest for decision applications. Skyline Groups extend the idea of skyline to groups of objects. In the recent years, several algorithms have been proposed to extract, in an efficient way, the complete set of skyline groups. Due to the novelty of the skyline group concept, these algorithms use custom enumeration strategies. The first contribution of this paper is the observation that a skyline group corresponds to the notion of ideal of a partially ordered set. From this observation, our second contribution consists in proposing a novel and efficient algorithm for the enumeration of all ideals of a given size k (i.e. all skyline groups of size k) of a poset. This algorithm, called GenIdeals, has a time delay complexity of O(w2), where w is the width of the poset, which improves the best known time output complexity for this problem: O(n3) where n is the number of elements in the poset. This work present new theoretical results and applications on skyline queries.
Fichier non déposé

Dates et versions

hal-03519794 , version 1 (10-01-2022)

Identifiants

Citer

Simon Coumes, Tassadit Bouadi, Lhouari Nourine, Alexandre Termier. Skyline Groups Are Ideals. An Efficient Algorithm for Enumerating Skyline Groups. IWOCA 2021 - 32nd International Workshop on Combinatorial Algorithms, Jul 2021, Ottawa, Canada. pp.223-236, ⟨10.1007/978-3-030-79987-8_16⟩. ⟨hal-03519794⟩
66 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More