Artificial IntelligenceNo Access

Identifying Most Preferential Skyline Product Combinations

Zhibang Yang

Department of Mathematics and Computer Science, Changsha University Changsha, Hunan 410082, P. R. China

E-mail Address: yangzhibang2006@126.com

Search for more papers by this author

Xu Zhou

College of Information Science and Engineering, Hunan University Changsha, Hunan 410082, P. R. China

E-mail Address: zhouxu2006@126.com

Search for more papers by this author

Jin Mei

College of Mathematics and Computer Science, Hunan Normal University Changsha, Hunan 410082, P. R. China

Search for more papers by this author

Yifu Zeng

College of Information Science and Engineering, Hunan University Changsha, Hunan 410082, P. R. China

E-mail Address: zengyifu@hnu.edu.cn

Search for more papers by this author

Guoqing Xiao

College of Information Science and Engineering, Hunan University Changsha, Hunan 410082, P. R. China

E-mail Address: xiaoguoqing@hnu.edu.cn

Search for more papers by this author

, and

Guo Pan

College of Information Science and Engineering, Hunan University Changsha, Hunan 410082, P. R. China

E-mail Address: panguo@hnu.edu.cn

Search for more papers by this author

https://doi.org/10.1142/S0218001417590224Cited by:2 (Source: Crossref)

Abstract

Nowadays, department stores and online merchants usually develop some price promotion strategies to attract customers and increase their purchase intention. Therefore, it is significant for customers to pick out attractive products and obtain the maximum discount rate. Admittedly, the skyline query is a most useful tool to find out attractive products. However, it does little to help select the product combinations with the maximum discount rate. Motivated by this, we identify an interesting problem, a most preferential skyline product (MPSP) combination discovering problem, which is NP-hard, for the first time in the literature. This problem aims to report all skyline product combinations having the maximum discount rate. Since the exact algorithm for the MPSP is not scalable to large or high-dimensional datasets, we design an approximate algorithm that guarantees the accuracy of the results. The experiment results demonstrate the efficiency and effectiveness of our proposed algorithms.

Keywords:

References

1. Y.-C. Chung, I.-F. Su and C. Lee , Efficient computation of combinatorial skyline queries, Inf. Syst. 38 (3) (2013) 369–387. Crossref, Web of Science, Google Scholar
2. T. H. Cormen , Introduction to Algorithms (MIT Press, 2009). Google Scholar
3. E. Dellis and B. Seeger , Efficient computation of reverse skyline queries, in Proc. 33rd Int. Conf. Very large Data Bases, VLDB Endowment, 2007, pp. 291–302. Google Scholar
4. X. Ding and H. Jin , Efficient and progressive algorithms for distributed skyline queries over uncertain data, IEEE Trans. Knowl. Data Eng. 24 (8) (2012) 1448–1462. Crossref, Web of Science, Google Scholar
5. Z. Fu, X. Sun, N. Linge and L. Zhou , Achieving effective cloud search services: Multi-keyword ranked search over encrypted cloud data supporting synonym query, IEEE Trans. Consum. Electron. 60 (1) (2014) 164–172. Crossref, Web of Science, Google Scholar
6. Y. Gao, Q. Liu, B. Zheng and G. Chen , On efficient reverse skyline query processing, Expert Syst. Appl. 41 (7) (2014) 3237–3249. Crossref, Web of Science, Google Scholar
7. Y. Gao, Q. Liu, B. Zheng, L. Mou, G. Chen and Q. Li , On processing reverse k-skyband and ranked reverse skyline queries, Inf. Sci. 293 (2015) 11–34. Crossref, Web of Science, Google Scholar
8. H. Im and S. Park , Group skyline computation, Inf. Sci. 188 (2012) 151–169. Crossref, Web of Science, Google Scholar
9. M. S. Islam, R. Zhou and C. Liu , On answering why-not questions in reverse skyline queries, in 2013 IEEE 29th Int. Conf. Data Engineering (IEEE, 2013), pp. 973–984. Google Scholar
10. T. Jiang, B. Zhang, D. Lin, Y. Gao and Q. Li , Incremental evaluation of top-k combinatorial metric skyline query, Knowl.-Based Syst. 74 (2015) 89–105. Crossref, Web of Science, Google Scholar
11. J. Liu, L. Xiong, J. Pei, J. Luo and H. Zhang , Finding pareto optimal groups: Group-based skyline, Proc. VLDB Endowment 8 (13) 2015. Google Scholar
12. M. Magnani and I. Assent , From stars to galaxies: Skyline queries on aggregate data, in Proc. 16th Int. Conf. Extending Database Technology (ACM, 2013), pp. 477–488. Google Scholar
13. D. Papadias, Y. Tao, G. Fu and B. Seeger , Progressive skyline computation in database systems, ACM Trans. Database Syst. 30 (1) (2005) 41–82. Crossref, Web of Science, Google Scholar
14. Y. Park, J.-K. Min and K. Shim , Parallel computation of skyline and reverse skyline queries using mapreduce, Proc. VLDB Endowment 6 (14) (2013) 2002–2013. Crossref, Google Scholar
15. J. Pei, B. Jiang, X. Lin and Y. Yuan , Probabilistic skylines on uncertain data, in Proc. 33rd Int. Conf. Very Large Data Bases (VLDB Endowment, 2007), pp. 15–26. Google Scholar
16. I.-F. Su, Y.-C. Chung and C. Lee , Top-k combinatorial skyline queries, in Database Systems for Advanced Applications (Springer, 2010), pp. 79–93. Crossref, Google Scholar
17. Y. Tao, X. Xiao and J. Pei , Efficient skyline and top-k retrieval in subspaces, IEEE Trans. Knowl. Data Eng. 19 (8) (2007) 1072–1088. Crossref, Web of Science, Google Scholar
18. Q. Wan, R. Chi-Wing Wong, I. F. Ilyas, M. Tamer Özsu and Y. Peng , Creating competitive products, Proc. VLDB Endowment 2 (1) (2009) 898–909. Crossref, Google Scholar
19. Q. Wan, RC-W Wong and Y. Peng , Finding top-k profitable products, in 2011 IEEE 27th Int. Conf. Data Engineering (ICDE) (IEEE, 2011), pp. 1055–1066. Google Scholar
20. Z. Xia, X. Wang, X. Sun and Q. Wang , A secure and dynamic multi-keyword ranked search scheme over encrypted cloud data, IEEE Trans. Parallel Distrib. Syst. 27 (2) (2015) 1–1. Web of Science, Google Scholar
21. G. Xiao, K. Li, K. Li and X. Zhou , Efficient top-(k, l) range query processing for uncertain data based on multicore architectures, Distrib. Parallel Databases 33 (3) (2015) 381–413. Crossref, Web of Science, Google Scholar
22. G. Xiao, K. Li, X. Zhou and K. Li , Efficient monochromatic and bichromatic probabilistic reverse top-k query processing for uncertain big data, J. Comp. Syst. Sci. 2016. Crossref, Web of Science, Google Scholar
23. N. Zhang, C. Li, N. Hassan, S. Rajasekaran and G. Das , On skyline groups, IEEE Trans. Knowl. Data Eng. 26 (4) (2014) 942–956. Crossref, Web of Science, Google Scholar
24. S. Zhang, N. Mamoulis and D. W Cheung , Scalable skyline computation using object-based space partitioning, in Proc. 2009 ACM SIGMOD Int. Conf. Management of Data (ACM, 2009), pp. 483–494. Google Scholar
25. X. Zhou, K. Li, Y. Zhou and K. Li , Adaptive processing for distributed skyline queries over uncertain data, IEEE Trans. Knowl. Data Eng. (2016), pp. 371–384. Crossref, Web of Science, Google Scholar
26. X. Zhou, K. Li, G. Xiao, Y. Zhou and K. Li , Top k favorite probabilistic products queries, IEEE Trans. Knowl. Data Eng. (2016) 2808–2821. Crossref, Web of Science, Google Scholar
27. L. Zhu, Y. Tao and S. Zhou , Distributed skyline retrieval with low bandwidth consumption, IEEE Trans. Knowl. Data Eng. 21 (3) (2009) 384–400. Crossref, Web of Science, Google Scholar