Paper 2
Computing Skyline Incrementally in Response to Online Preference ModificationAuthors: Tassadit Bouadi, Marie-Odile Cordier, René Quiniou |
AbstractSkyline 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 dicult task, especially when the dataset is large. EC2Sky, our proposal, focuses on how to answer eciently skyline queries in the presence of dynamic user preferences and despite large volumes of data. In 2008-2009, Wong et al. showed that the skyline associated with any preference on a particular dimension can be computed, without domination tests, from the skyline points associated with rst order preferences on that same dimension. Consequently, they propose to materialize skyline points associated with the most preferred values in a speci c data structure called IPO-tree (Implicit Preference Order Tree). However, the size of the IPO-tree is exponential with respect to the number of dimensions. While reusing the merging property proposed byWong et al. to deal with the re nements of preferences on a single dimension, 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 exibility for dimension preference updates is de ned. This contribution improves notably the execution time and storage size of queries. Experiments on synthetic data highlight the relevance of EC2Sky compared to IPO-Tree. |
|
|