Top

Published in:

2019 | OriginalPaper | Chapter

Reducing Skyline Query Results: An Approach Based on Fuzzy Satisfaction of Concepts

Authors : Mohamed Haddache, Allel Hadjali, Hamid Azzoune

Published in: Flexible Query Answering Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Querying databases to search for the best objects matching user’s preferences is a fundamental problem in multi-criteria databases. The skyline queries are an important tool for solving such problems. Based on the concept of Pareto dominance, the skyline process extracts the most interesting (not dominated in Pareto sense) objects from a set of data. However, this process may lead to a huge skyline problem as the size of the results of skyline grows with the number of criteria (dimensions). In this case, the skyline is less informative for the end-users. In this paper, we propose an efficient approach to refine the skyline and reduce its size, using some advanced techniques borrowed from the formal concepts analysis. The basic idea is to build the fuzzy lattice of skyline objects based on the satisfaction rate of concepts. Then, the refined skyline is given by the concept that contains k objects (where k is a user-defined parameter) and has the great satisfaction rate w.r.t. the target concept. Experimental study shows the efficiency and the effectiveness of our approach compared to the naive approach.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Data Exploration in the HIFUN Language

next chapter Quantify the Variability of Time Series of Imprecise Data

Abbaci, K., Hadjali, A., Lietard, L., Rocacher, D.: A linguistic quantifier-based approach for skyline refinement. In: Joint IFSA World Congress and NAFIPS Annual Meeting, IFSA/NAFIPS, Edmonton, Alberta, Canada, 24–28 June, pp. 321–326 (2013)

Balke, W., Güntzer, U., Lofi, C.: User interaction support for incremental refinement of preference-based queries. In: Proceedings of the First International Conference on Research Challenges in Information Science (RCIS), Ouarzazate, Morocco, 23–26 April, pp. 209–220 (2007)

Belohlávek, R.: Fuzzy Galois connections. Math. Log. Q. 45, 497–504 (1999)MathSciNetCrossRef

Börzsönyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany, 2–6 April, pp. 421–430 (2001)

Chan, C.Y., Jagadish, H.V., Tan, K., Tung, A.K.H., Zhang, Z.: Finding k-dominant skylines in high dimensional space. In: Proceedings of the International Conference on Management of Data (ACM SIGMOD), Chicago, Illinois, USA, 27–29 June, pp. 503–514 (2006)

Chomicki, J., Ciaccia, P., Meneghetti, N.: Skyline queries, front and back. SIGMOD Rec. 42(3), 6–18 (2013)CrossRef

Endres, M., Kießling, W.: Parallel skyline computation exploiting the lattice structure. J. Database Manag. 26(4), 18–43 (2015)CrossRef

Goncalves, M., Tineo, L.: Fuzzy dominance skyline queries. In: Wagner, R., Revell, N., Pernul, G. (eds.) DEXA 2007. LNCS, vol. 4653, pp. 469–478. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74469-6_46CrossRef

Gulzar, Y., Alwan, A.A., Salleh, N., Shaikhli, I.F.A.: Processing skyline queries in incomplete database: issues, challenges and future trends. JCS 13(11), 647–658 (2017)

10.

Haddache, M., Belkasmi, D., Hadjali, A., Azzoune, H.: An outranking-based approach for skyline refinement. In: 8th IEEE International Conference on Intelligent Systems, IS 2016, Sofia, Bulgaria, 4–6 September 2016, pp. 333–344 (2016)

11.

Hadjali, A., Pivert, O., Prade, H.: Possibilistic contextual skylines with incomplete preferences. In: Second International Conference of Soft Computing and Pattern Recognition, (SoCPaR), Cergy Pontoise/Paris, France, 7–10 December, pp. 57–62 (2010)

12.

Hadjali, A., Pivert, O., Prade, H.: On different types of fuzzy skylines. In: Kryszkiewicz, M., Rybinski, H., Skowron, A., Raś, Z.W. (eds.) ISMIS 2011. LNCS (LNAI), vol. 6804, pp. 581–591. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21916-0_62CrossRef

13.

Mahmoud, H., Habiba, D., Hadjali, A.: A strong-dominance-based approach for refining the skyline. In: Proceedings of the 12th International Symposium on Programming and Systems (ISPS), Algiers, Algeria, 28–30 April, pp. 1–8 (2015)

14.

Koltun, V., Papadimitriou, C.H.: Approximately dominating representatives. In: Eiter, T., Libkin, L. (eds.) ICDT 2005. LNCS, vol. 3363, pp. 204–214. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-30570-5_14CrossRef

15.

Lee, J., Hwang, S.: Scalable skyline computation using a balanced pivot selection technique. Inf. Syst. 39, 1–21 (2014)CrossRef

16.

Lee, J., You, G., Hwang, S.: Telescope: zooming to interesting skylines. In: Kotagiri, R., Krishna, P.R., Mohania, M., Nantajeewarawat, E. (eds.) DASFAA 2007. LNCS, vol. 4443, pp. 539–550. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71703-4_46CrossRef

17.

Loyer, Y., Sadoun, I., Zeitouni, K.: Personalized progressive filtering of skyline queries in high dimensional spaces. In: Proceedings of the 17th International Conference on Database Engineering & Applications Symposium (IDEAS), Barcelona, Spain, 9–11 October, pp. 186–191 (2013)

18.

Papadias, D., Tao, Y., Fu, G., Seeger, B.: An optimal and progressive algorithm for skyline queries. In Proceedings of the International Conference on Management of Data (ACM SIGMOD), San Diego, California, USA, 9–12 June, pp. 467–478 (2003)

19.

Raja, H., Djouadi, Y.: Projection extensionnelle pour la reduction d’un treillis de concepts formels flous. In: 22emes rencontres francophones sur la Logique Floue et ses Applications, LFA 2013, Reims, France, 10–11 octobre 2013 (2013)

20.

Sarma, A.D., Lall, A., Nanongkai, D., Lipton, R.J., Xu, J.: Representative skylines using threshold-based preference distributions. In: Proceedings of the 27th International Conference on Data Engineering (ICDE), Hannover, Germany, 11–16 April, pp. 387–398 (2011)

21.

Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts. In: Rival, I. (ed.) Ordered Sets. AISC, vol. 83, pp. 445–470. Springer, Dordrecht (1982). https://doi.org/10.1007/978-94-009-7798-3_15CrossRef

22.

Yin, B., Wei, X., Liu, Y.: Finding the informative and concise set through approximate skyline queries. Expert Syst. Appl. 119, 289–310 (2019) CrossRef

23.

Yiu, M.L., Mamoulis, N.: Efficient processing of top-k dominating queries on multi-dimensional data. In: Proceedings of the 33rd International Conference on Very Large Data Bases (VLDB), University of Vienna, Austria, 23–27 September, pp. 483–494 (2007)

Title: Reducing Skyline Query Results: An Approach Based on Fuzzy Satisfaction of Concepts
Authors: Mohamed Haddache
Allel Hadjali
Hamid Azzoune
Publisher: Springer International Publishing
Book: Flexible Query Answering Systems
Print ISBN: 978-3-030-27628-7

Electronic ISBN: 978-3-030-27629-4

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-27629-4_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner