Recommendations for two-way selections using skyline view queries
Tóm tắt
We study a practical and novel problem of making recommendations between two parties such as applicants and job positions. We model the competent choices of each party using skylines. In order to make recommendations in various scenarios, we propose a series of skyline view queries. To make recommendations, we often need to answer skyline view queries for many entries in one or two parties in batch, such as for many applicants versus many jobs. However, the existing skyline computation algorithms focus on answering a single skyline query at a time and do not consider sharing computation when answering skyline view queries for many members in one party or both parties. To tackle the batch recommendation problem, we develop several efficient algorithms to process skyline view queries in batch. The experiment results demonstrate that our algorithms significantly outperform the state-of-the-art methods.
Tài liệu tham khảo
Börzsönyi S, Kossmann D, Stocker K (2001) The skyline operator. In: Proceedings of the 17th international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 421–430
Chomicki J, Godfrey P, Gryz J, Liang D (March 2003) Skyline with pre-sorting. In: Proceedings 2003 international conference data engineering (ICDE’03). Bangalore, India, p 717
Godfrey P, Shipley R, Gryz J (2005) Maximal vector computation in large data sets. In: VLDB ’05: proceedings of the 31st international conference on very large data bases, pp 229–240. VLDB Endowment
Tan K-L, Eng P-K, Ooi BC (2001) Efficient progressive skyline computation. In: VLDB ’01: proceedings of the 27th international conference on very large data bases. Morgan Kaufmann Publishers, San Francisco, CA, USA, pp 301–310
Kossmann D, Ramsak F, Rost S (2002) Shooting stars in the sky: an online algorithm for skyline queries. In: VLDB ’02: proceedings of the 28th international conference on very large data Bases, pp 275–286. VLDB Endowment
Papadias D, Tao Y, Fu G, Seeger B (2003) An optimal and progressive algorithm for skyline queries. In: SIGMOD ’03: proceedings of the 2003 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 467–478
Papadias D, Tao Y, Fu G, Seeger B (2005) Progressive skyline computation in database systems. ACM Trans Database Syst 30(1): 41–82
Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: SIGMOD ’84: proceedings of the 1984 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 47–57
Chen H, Liu J, Furuse K, Yu JX, Ohbo N (2011) Indexing expensive functions for efficient multi-dimensional similarity search. Knowl Inf Syst 27(2): 165–192
Pei J, Jin W, Ester M, Tao Y (August 2005) Catching the best views in skyline: a semantic approach. In: Proceedings of the 31th international conference on very large data bases (VLDB’05). Trondheim, Norway
Pei J, Fu AWC, Lin X, Wang H (April 2007) Computing compressed skyline cubes efficiently. In: Proceedings of the 23nd international conference on data engineering (ICDE’07). IEEE, Istanbul, Turkey
Yuan Y, Lin X, Liu Q, Wang W, Yu JX, Zhang Q (2005) Efficient computation of the skyline cube. In: VLDB ’05: proceedings of the 31st international conference on very large data bases, pp 241–252. VLDB Endowment
Xia Tian, Zhang Donghui (2006) Refreshing the sky: the compressed skycube with efficient support for frequent updates. In: SIGMOD ’06: proceedings of the 2006 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 491–502
Tao Y, Xiao X, Pei J (2006) Subsky: efficient computation of skylines in subspaces. In: ICDE ’06: proceedings of the 22nd international conference on data engineering. IEEE Computer Society, Washington, DC, USA, p 65
Chan C-Y, Jagadish HV, Tan K-L, Tung AKH, Zhenjie Z (2006) Finding k-dominant skylines in high dimensional space. In: SIGMOD ’06: proceedings of the 2006 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 503–514
Lin X, Yuan Y, Wang W, Lu H (2005) Stabbing the sky: efficient skyline computation over sliding windows. In ICDE ’05: proceedings of the 21st international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 502–513
Tao Y, Papadias D (2006) Maintaining sliding window skylines on data streams. IEEE Trans Knowl Data Eng 18(3): 377–391
Michael M, Patel JM, Grosky WI (2006) Efficient continuous skyline computation. In: ICDE ’06: proceedings of the 22nd international conference on data engineering. IEEE Computer Society, Washington, DC, USA, p 108
Sun S, Huang Z, Zhong H, Dai D, Liu H, Li J (2010) Efficient monitoring of skyline queries over distributed data streams. Knowl Inf Syst 25(3): 575–606
Huang Z, Sun S-L, Wang W (2010) Efficient mining of skyline objects in subspaces over data streams. Knowl Inf Syst 22(2): 159–183
Jiang B, Pei J (2009) Online interval skyline queries on time series. In: ICDE ’09: proceedings of the 2009 IEEE international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 1036–1047
Balke W-T, Gntzer U, Zheng JX (2004) Efficient distributed skylining for web information systems. In: IN EDBT, pp 256–273
Wu P, Zhang C, Feng Y, Zhao BY, Agrawal D, Abbadi AEl (2006) Parallelizing skyline queries for scalable distribution. In: In EDBT06, pp 112–130
Huang Z, Jensen CS, Lu H, Ooi BC (2006) Skyline queries against mobile lightweight devices in manets. In: ICDE ’06: proceedings of the 22nd international conference on data engineering, IEEE Computer Society, Washington, DC, USA, p 66
Sharifzadeh M, Shahabi C (2006) The spatial skyline queries. In: VLDB ’06: proceedings of the 32nd international conference on very large data bases, pp 751–762. VLDB Endowment
Chan C-Y, Eng P-K, Tan K-L (2005) Stratified computation of skylines with partially-ordered domains. In: SIGMOD ’05: proceedings of the 2005 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 203–214
Chen L, Lian X (2008) Dynamic skyline queries in metric spaces. In: EDBT ’08: proceedings of the 11th international conference on extending database technology. ACM, New York, NY, USA, pp 333–343
Pei J, Jiang B, Lin X, Yuan Y (2007) Probabilistic skylines on uncertain data. In: VLDB ’07: proceedings of the 33rd international conference on very large data bases, pp 15–26. VLDB Endowment
Lian X, Chen L (2008) Monochromatic and bichromatic reverse skyline search over uncertain databases. In: SIGMOD ’08: proceedings of the 2008 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 213–226
Wong RC-W, Pei J, Fu AW-C, Wang K (2007) Mining favorable facets. In: KDD ’07: proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, New York, NY, USA, pp 804–813
Jiang B, Pei J, Lin X, Cheung DW, Han J (2008) Mining preferences from superior and inferior examples. In: KDD ’08: proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, New York, NY, USA, pp 390–398
Dellis E, Seeger B (2007) Efficient computation of reverse skyline queries. In: VLDB ’07: proceedings of the 33rd international conference on very large data bases, pp 291–302. VLDB Endowment
Wu X, Tao Y, Wong RC-W, Ding L, Yu JX (2009) Finding the influence set through skylines. In: EDBT ’09: proceedings of the 12th international conference on extending database technology. ACM, New York, NY, USA, pp 1030–1041
Gale D, Shapley LS (1962) College admissions and the stability of marriage. In: American Mathematical Monthly, pp 9–14
Gusfield D (1988) The structure of the stable roommate problem: efficient representation and enumeration of all stable assignments. SIAM J Comput 17(4): 742–769
Iwama K, Miyazaki S, Manlove D, Morita Y (1999) Stable marriage with incomplete lists and ties. In: ICAL ’99: proceedings of the 26th international colloquium on automata, languages and programming. Springer, London, UK, pp 443–452
Manlove DF (2002) The structure of stable marriage with indifference. Discret Appl Math 122(1-3): 167–181
Manlove DF, Irving RW, Iwama K, Miyazaki S, Morita Y (2002) Hard variants of stable marriage. Theor Comput Sci 276(1-2): 261–279
Brinkhoff T, Kriegel H-P, Seeger B (1993) Efficient processing of spatial joins using r-trees. In: SIGMOD ’93: proceedings of the 1993 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 237–246
Pei J, Jiang B, Lin X, Yuan Y (2007) Probabilistic skylines on uncertain data. In: Proceedings of the 33rd international conference on very large data bases, VLDB ’07, pp 15–26. VLDB Endowment
Zou L, Chen L (2008) Dominant graph: an efficient indexing structure to answer top-k queries. In: ICDE ’08: proceedings of the 2008 IEEE 24th international conference on data engineering. IEEE Computer Society, Washington, DC, USA, pp 536–545
Li C, Ooi BC, Tung AKH, Wang S (2006) Dada: a data cube for dominant relationship analysis. In: SIGMOD ’06: proceedings of the 2006 ACM SIGMOD international conference on management of data. ACM, New York, NY, USA, pp 659–670