Incremental Computation of Skyline Queries with Dynamic Preferences

Tassadit Bouadi 1 Marie-Odile Cordier 1 René Quiniou 1
1 DREAM - Diagnosing, Recommending Actions and Modelling
Inria Rennes – Bretagne Atlantique , IRISA-D7 - GESTION DES DONNÉES ET DE LA CONNAISSANCE
Abstract : Skyline queries retrieve the most interesting objects from a database with respect to multi-dimensional preferences. Identifying and extracting the relevant data corresponding to multiple criteria provided by users remains a difficult task, especially when the data are large. In 2008-2009, Wong et al. showed how to avoid costly skyline query computations by deriving the skyline points associated with any preference from the skyline points associated with the most preferred values. They propose to materialize these points in a structure called IPO-tree (Implicit Preference Order Tree). However, its size is exponential with respect to the number of dimensions. We propose an incremental method for calculating the skyline points related to several dimensions associated with dynamic preferences. For this purpose, a materialization of linear size which allows a great flexibility for dimension preference updates is defined. This contribution improves notably the computation cost of queries. Experiments on synthetic data highlight the relevance of EC2Sky compared to IPO-Tree.
Type de document :
Communication dans un congrès
Stephen W. Liddle and Klaus-Dieter Schewe and A Min Tjoa and Xiaofang Zhou. Database and Expert Systems Applications (DEXA), Sep 2012, Vienne, Austria. Springer, 1, pp.219-233, 2012, 7446. <http://link.springer.com/chapter/10.1007%2F978-3-642-32600-4_17>. <10.1007/978-3-642-32600-4_17>
Liste complète des métadonnées

https://hal.inria.fr/hal-00757838
Contributeur : Tassadit Bouadi <>
Soumis le : mardi 27 novembre 2012 - 16:31:43
Dernière modification le : jeudi 9 février 2017 - 16:02:58

Identifiants

Citation

Tassadit Bouadi, Marie-Odile Cordier, René Quiniou. Incremental Computation of Skyline Queries with Dynamic Preferences. Stephen W. Liddle and Klaus-Dieter Schewe and A Min Tjoa and Xiaofang Zhou. Database and Expert Systems Applications (DEXA), Sep 2012, Vienne, Austria. Springer, 1, pp.219-233, 2012, 7446. <http://link.springer.com/chapter/10.1007%2F978-3-642-32600-4_17>. <10.1007/978-3-642-32600-4_17>. <hal-00757838>

Partager

Métriques

Consultations de la notice

289