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 dataset is large. EC 2 Sky, our proposal, focuses on how to answer efficiently 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 first order preferences on that same dimension. Consequently, they propose to materialize skyline points associated with the most preferred values in a specific 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 by Wong et al. to deal with the refinements 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 flexibility for dimension preference updates is defined. This contribution improves notably the execution time and storage size of queries. Experiments on synthetic data highlight the relevance of EC 2 Sky compared to IPO-Tree.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Balke, W.T., Guntzer, U., Siberski, W.: Exploiting indifference for customization of partial order skylines. In: Proceedings of the 10th International Database Engineering and Applications Symposium, pp. 80–88. IEEE Computer Society (2006)
Bentley, J.L., Kung, H.T., Schkolnick, M., Thompson, C.D.: On the average number of maxima in a set of vectors and applications. J. ACM 25(4), 536–543 (1978)
Bitran, G.R., Magnanti, T.L.: The structure of admissible points with respect to cone dominance. Optimization Theory and Applications 29(4), 573–614 (1979)
Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proc. of the 17th International Conference on Data Engineering, pp. 421–430. IEEE Computer Society (2001)
Bouadi, T., Cordier, M.-O., Quiniou, R.: Incremental computation of skyline queries with dynamic preferences. In: Liddle, S.W., Schewe, K.-D., Tjoa, A.M., Zhou, X. (eds.) DEXA 2012, Part I. LNCS, vol. 7446, pp. 219–233. Springer, Heidelberg (2012)
Brando, C., Goncalves, M., González, V.: Evaluating top-k skyline queries over relational databases. In: Wagner, R., Revell, N., Pernul, G. (eds.) DEXA 2007. LNCS, vol. 4653, pp. 254–263. Springer, Heidelberg (2007)
Chen, L., Lian, X.: Efficient processing of metric skyline queries. IEEE Trans. on Knowl. and Data Eng. 21(3), 351–365 (2009)
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with presorting: Theory and optimizations. In: Proc. of Intelligent Information Systems, pp. 595–604. Springer, Heidelberg (2005)
Godfrey, P., Shipley, R., Gryz, J.: Algorithms and analyses for maximal vector computation. The VLDB Journal 16(1), 5–28 (2007)
Huang, Z., Guo, J., Sun, S.L., Wang, W.: Efficient optimization of multiple subspace skyline queries. J. Comput. Sci. Technol. 23(1), 103–111 (2008)
Jin, W., Tung, A.K.H., Ester, M., Han, J.: On efficient processing of subspace skyline queries on high dimensional data. In: Proc. of the 19th International Conference on Scientific and Statistical Database Management. IEEE Computer Society (2007)
Mindolin, D., Chomicki, J.: Preference elicitation in prioritized skyline queries. The VLDB Journal 20(2), 157–182 (2011)
Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Trans. Database Syst. 30(1), 41–82 (2005)
Pei, J., Jin, W., Ester, M., Tao, Y.: Catching the best views of skyline: a semantic approach based on decisive subspaces. In: Proc of the 31st International Conference on Very Large Data Bases, pp. 253–264, VLDB Endowment (2005)
Raïssi, C., Pei, J., Kister, T.: Computing closed skycubes. Proc. VLDB Endow. 3(1), 838–847 (2010)
Sawaragi, Y., Nakayama, H., Tanino, T.: Theory of Multiobjective Optimization. Academic Press, Orlando (1985)
Tan, K.L., Eng, P.K., Ooi, B.C.: Efficient progressive skyline computation. In: Proceedings of the 27th International Conference on Very Large Data Bases, pp. 301–310. Morgan Kaufmann Publishers Inc. (2001)
Tao, Y., Xiao, X., Pei, J.: Efficient skyline and top-k retrieval in subspaces. IEEE Trans. on Knowl. and Data Eng. 19(8), 1072–1088 (2008)
Trenkler, G.: In: Johnson, N.l., Kotz, S., kemp, A.W. (eds.) Univariate Discrete Distributions, 2nd edn. John wiley (1994) ISBN 0-471-54897-9; Computational Statistics & Data Analysis, 17(2), 240–241 (1994)
Wong, R.C.W., Fu, A.W.C., Pei, J., Ho, Y.S., Wong, T., Liu, Y.: Efficient skyline querying with variable user preferences on nominal attributes. Proc. VLDB Endow. 1(1), 1032–1043 (2008)
Wong, R.C.W., Pei, J., Fu, A.W.C., Wang, K.: An erratum on “online skyline analysis with dynamic preferences on nominal attributes”. IEEE Trans. on Knowl. and Data Eng. (to be published)
Wong, R.C.W., Pei, J., Fu, A.W.C., Wang, K.: Online skyline analysis with dynamic preferences on nominal attributes. IEEE Trans. on Knowl. and Data Eng. 21(1), 35–49 (2009)
Xia, T., Zhang, D., Tao, Y.: On skylining with flexible dominance relation. In: Proc. of the 2008 IEEE 24th International Conference on Data Engineering, pp. 1397–1399. IEEE Computer Society (2008)
Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J.X., Zhang, Q.: Efficient computation of the skyline cube. In: Proc. of the 31st International Conference on Very Large Data Bases, pp. 241–252, VLDB Endowment (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Bouadi, T., Cordier, MO., Quiniou, R. (2013). Computing Skyline Incrementally in Response to Online Preference Modification. In: Hameurlain, A., Küng, J., Wagner, R., Liddle, S.W., Schewe, KD., Zhou, X. (eds) Transactions on Large-Scale Data- and Knowledge-Centered Systems X. Lecture Notes in Computer Science, vol 8220. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41221-9_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-41221-9_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41220-2
Online ISBN: 978-3-642-41221-9
eBook Packages: Computer ScienceComputer Science (R0)